Finding approximate repetitions under Hamming distance

AbstractThe 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