# Maximal pair

In computer science, a maximal pair is a tuple ${\displaystyle (p_{1},p_{2},l)}$, such that, given a string ${\displaystyle S}$ of length ${\displaystyle n}$, ${\displaystyle S[p_{1}..p_{1}+l-1]=S[p_{2}..p_{2}+l-1]}$, but ${\displaystyle S[p_{1}-1]\neq S[p_{2}-1]}$ and ${\displaystyle 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 ${\displaystyle \Theta (n+z)}$ time using a suffix tree,[1] if there are ${\displaystyle z}$ such structures.

## Example

 Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Character x a b c y a b c w a b c y z

${\displaystyle (2,6,3)}$ and ${\displaystyle (6,10,3)}$ are maximal pairs as the referenced substrings do not share identical characters to the left or the right.

${\displaystyle (2,10,3)}$ is not, as the character `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.