Approximate periodicity

Finding an approximate period in a given string S of length n is defined as follows. Let S ′ be a periodic string closest to S under some distance metric, find the smallest period of S ′. This period is called an approximate period of S under the given metric. Let the distance between the input string S and a closest periodic string under the Hamming distance S ′ be k. We develop algorithms that construct an approximate period of S under the Hamming distance in time O ( n k log ⁡ log ⁡ n ) and under the swap distance in time O ( n 2 ). Finally, we show an O ( n log ⁡ n ) algorithm for finite alphabets, and an O ( n log 3 ⁡ n ) algorithm for infinite alphabets, that approximate the minimum number of mismatches between the input string and a closest periodic string under the Hamming distance.

Authors

• Amihood Amir
• Estrella Eisenberg
• A. Levy

Keywords

• String algorithms
• Periodicity
• Approximate periodicity
• Approximate matching
• Hamming distance
• Swap distance