Given a string $S$ of length $n$, a maximal pair is a tuple $(p\_1,\; p\_2,\; l)$, such that $S[p\_1..p\_1+l-1]=S[p\_2..p\_2+l-1]$, but $S[p\_1-1]\; neq\; S[p\_2-1]$ and $S[p\_1+l]\; neq\; S[p\_2+l]$. A maximal repeat is a string represented by such tuple. A supermaximal repeat is a maximal repeat never occurring as a proper substring of another maximal repeat. Both maximal pairs, maximal repeats and supermaximal repeats can be found in $Theta(n+z)$ time using a suffix tree , if there are $z$ such structures.

Example

12345678901234

xabcyabcwabcyz

$(2,6,3)$ and $(6,10,3)$ are maximal pairs, but $(2,10,3)$ is not, as y follows both substrings. abc and abcy are maximal repeats, but only abcy is a supermaximal repeat.

References