Average-Case Optimal Approximate Circular String Matching

Research output: Chapter in Book/Report/Conference proceedingOther chapter contributionpeer-review

16 Citations (Scopus)


Approximate string matching is the problem of finding all factors of a text t of length n that are at a distance at most k from a pattern x of length m. Approximate circular string matching is the problem of finding all factors of t that are at a distance at most k from x or from any of its rotations. In this article, we present a new algorithm for approximate circular string matching under the edit distance model with optimal average-case search time O(n(k+logm)/m). Optimal average-case search time can also be achieved by the algorithms for multiple approximate string matching (Fredriksson and Navarro, 2004) using x and its rotations as the set of multiple patterns. Here we reduce the preprocessing time and space requirements compared to that approach
Original languageUndefined/Unknown
Title of host publicationLanguage and Automata Theory and Applications
Subtitle of host publication9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings
EditorsA.-H. Dediu, E. Formenti, C. Martín-Vide, B Truthe
PublisherSpringer International Publishing
Number of pages12
ISBN (Electronic)978-3-319-15579-1
ISBN (Print)978-3-319-15578-4
Publication statusPublished - 24 Feb 2015
Event9th international conference, LATA 2015 - France, Nice, United Kingdom
Duration: 2 Mar 20156 Mar 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Conference9th international conference, LATA 2015
Country/TerritoryUnited Kingdom

Cite this