Streaming Periodicity with Mismatches

Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer +1

We study the problem of finding all $k$-periods of a length-$n$ string $S$, presented as a data stream. $S$ is said to have $k$-period $p$ if its prefix of length $n-p$ differs fro…