Maximal pair

In computer science, a maximal pair is a tuple $(p_1, p_2, l)$, such that, given a string $S$ of length $n$, $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,^[1] 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

1. Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. p. 143. ISBN 0-521-58519-8.

External links

• Project for the computation of all maximal repeats in one ore more strings in Python, using suffix array.