Approximate periodicity (Q2343134)

The paper is the full version of the authors' conference paper [Lect. Notes Comput. Sci. 6506, 25--36 (2010; Zbl 1310.68264)]. In the paper, the authors propose an algorithm to determine the approximate period of a string using Hamming and swap distances. Namely, the algorithm computes the minimum number of mismatches between the input string and a periodic substring. The authors claim that the proposed algorithm has \(O(n\log n)\) complexity for finite alphabets and \(O(n\log^3 n)\) complexity for infinite alphabets. The paper is worthy reading as it clearly states two open problems on string matching problems.