  The approximate period recovery problem asks to compute all
$\textit{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 $\tau_p$ from $S$, where $\tau_p = \lfloor
\frac{n}{(3.75+\epsilon)\cdot p} \rfloor$ for some $\epsilon>0$. Here, the set
of periodic extensions of $P$ consists of all finite prefixes of $P^\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/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.
