Period recovery of strings over the Hamming and edit distances

A string T of length m is periodic in P of length p if P is a substring of T and T[i]=T[i+p] for all 0≤i≤m−p−1 and m≥2p. The shortest such prefix, P, is called the period of T (i.e., P=T[0..p−1]). In this paper we investigate the period recovery problem. Given a string S of length n, find the primitive period(s) P such that the distance between S and a string T that is periodic in P is below a threshold τ. We consider the period recovery problem over both the Hamming distance and the edit distance. For the Hamming distance case, we present an O(nlog⁡n)-time algorithm, where τ is given as ⌊n(2+ϵ)p⌋, for ϵ>0. For the edit distance case, τ=⌊n(3.75+ϵ)p⌋ and ϵ>0, we provide an O(n4/3)-time algorithm.