Average-case optimal approximate circular string matching

Carl Barton, Costas S. Iliopoulos, Solon P. Pissis

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 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.

Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications - 9th International Conference, LATA 2015, Proceedings
EditorsAdrian-Horia Dediu, Carlos Martín-Vide, Enrico Formenti, Bianca Truthe
PublisherSpringer Verlag
Pages85-96
Number of pages12
ISBN (Electronic)9783319155784
DOIs
Publication statusPublished - 1 Jan 2015
Externally publishedYes
Event9th International Conference on Language and Automata Theory and Applications, LATA 2015 - Nice, France
Duration: 2 Mar 20156 Mar 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8977
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Conference on Language and Automata Theory and Applications, LATA 2015
Country/TerritoryFrance
CityNice
Period2/03/156/03/15

Keywords

  • Algorithms on automata and words
  • Approximate string matching
  • Average-case complexity
  • Average-case optimal

Fingerprint

Dive into the research topics of 'Average-case optimal approximate circular string matching'. Together they form a unique fingerprint.

Cite this