Faster Recovery of Approximate Periods over Edit Distance

The approximate period recovery problem asks to compute all $\mathit{\text{approximate}}\mathit{\text{word-periods}}$ of a given word $S$ of length $n$: all primitive words $P$ ($\mathrm{\mid }P\mathrm{\mid }=p$) which have a periodic extension at edit distance smaller than ${\tau }_p$ from $S$, where $\tau_p = \lfloor \frac{n}{(3.75+\epsilon)\cdot p} \rfloor$forsome$\epsilon>0$. Here, the set of periodic extensions of $P$ consists of all finite prefixes of $P^{\mathrm{\infty }}$. 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\mathrm{/}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.