Finding approximate repetitions under hamming distance

Roman Kolpakov, Gregory Kucherov

Research output: Contribution to journalConference articlepeer-review

45 Citations (Scopus)


The problem of computing periodicities with K possible mismatches is studied. Two main definitions are considered, and for both of them an O(nKlogK + S) algorithm is proposed (n the word length and S the size of the output). This improves, in particular, the bound obtained by G. Landan and J. Schmidt in 1993 (Proceedings of the Fourth Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 684, Springer, Berlin, Padova, Italy, pp. 120-133). Finally, other possible definitions are briefly analyzed.

Original languageEnglish
Pages (from-to)135-156
Number of pages22
JournalTheoretical Computer Science
Issue number1
Publication statusPublished - 28 Jun 2003
Externally publishedYes
EventLogic and Complexity in Computer Science - Creteil, France
Duration: 3 Sep 20015 Sep 2001


Dive into the research topics of 'Finding approximate repetitions under hamming distance'. Together they form a unique fingerprint.

Cite this