@inbook{28d1adc6d84b49ba91a2fc9ef734403b,

title = "Average-Case Optimal Approximate Circular String Matching",

abstract = "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",

author = "Carl Barton and Iliopoulos, {Costas S.} and Pissis, {Solon P.}",

year = "2015",

month = feb,

day = "24",

doi = "10.1007/978-3-319-15579-1_6",

language = "Undefined/Unknown",

isbn = "978-3-319-15578-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer International Publishing",

pages = "85--96",

editor = "A.-H. Dediu and E. Formenti and C. Mart{\'i}n-Vide and B Truthe",

booktitle = "Language and Automata Theory and Applications",

note = "9th international conference, LATA 2015 ; Conference date: 02-03-2015 Through 06-03-2015",

}