King's College London

Research portal

Average-Case Optimal Approximate Circular String Matching

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

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
Pages85-96
Number of pages12
ISBN (Electronic)978-3-319-15579-1
ISBN (Print)978-3-319-15578-4
DOIs
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
Volume8977
ISSN (Print)0302-9743

Conference

Conference9th international conference, LATA 2015
CountryUnited Kingdom
CityNice
Period2/03/20156/03/2015

King's Authors

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

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454