Locating maximal approximate runs in a string (Q2410363)

The authors show how, given a string \(T\) of \(n\) characters and a bound \(k\), we can find in \(O (n k^2 \log k + \mathrm{occ})\) time all the \(\mathrm{occ}\) triples \((i, j, p)\) such that, first, the substring \(T [i, j]\) is within Hamming distance \(k\) of a string with period \(p \leq (j-i+1)/2\) and, second, \(T [i, j]\) is not contained within a longer substring also within Hamming distance \(k\) of a string with period \(p\). Their algorithm reuses several ideas from Kolpakov and Kucherov's \(O (n k \log k + \mathrm{occ})\)-time algorithm [\textit{R. Kolpakov} and \textit{G. Kucherov}, Theor. Comput. Sci. 303, No. 1, 135--156 (2003; Zbl 1051.68119)] for the variant of the problem in which the restriction on \(T [i, j]\) is that \(T [i..j - p]\) and \(T [i + p..j]\) are at Hamming distance at most \(k\) from each other.