The approximate period recovery problem asks to compute all approximate word-periods of a given word S of length n: all primitive words P (|P| = p) which have a periodic extension at edit distance smaller than τ_p from S, where τ_p = [n/((3.75+ε)·p)] for some ε >0. Here, the set of periodic extensions of P consists of all finite prefixes of P~∞. We improve the time complexity of the fastest known algorithm for this problem of Amir et. al. [Theor. Comput. Sci., 2018] from O(n~(4/3)) to O(n log n). Our tool is a fast algorithm for Approximate Pattern Matching in Periodic Text. We consider only verification for the period recovery problem when the candidate approximate word-period P is explicitly given up to cyclic rotation; the algorithm of Amir et al. reduces the general problem in O(n) time to a logarithmic number of such more specific instances.
展开▼
