TY - GEN
T1 - Average-case optimal approximate circular string matching
AU - Barton, Carl
AU - Iliopoulos, Costas S.
AU - Pissis, Solon P.
PY - 2015/1/1
Y1 - 2015/1/1
N2 - 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 averagecase 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.
AB - 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 averagecase 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.
KW - Algorithms on automata and words
KW - Approximate string matching
KW - Average-case complexity
KW - Average-case optimal
UR - http://www.scopus.com/inward/record.url?scp=84928784983&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84928784983&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-15579-1_6
DO - 10.1007/978-3-319-15579-1_6
M3 - Conference contribution
AN - SCOPUS:84928784983
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 85
EP - 96
BT - Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Proceedings
A2 - Dediu, Adrian-Horia
A2 - Martín-Vide, Carlos
A2 - Formenti, Enrico
A2 - Truthe, Bianca
PB - Springer Verlag
T2 - 9th International Conference on Language and Automata Theory and Applications, LATA 2015
Y2 - 2 March 2015 through 6 March 2015
ER -