Definitions
Nearby Words

# Maximal pair

Given a string $S$ of length $n$, a maximal pair is a tuple $\left(p_1, p_2, l\right)$, such that $S\left[p_1..p_1+l-1\right]=S\left[p_2..p_2+l-1\right]$, but $S\left[p_1-1\right] neq S\left[p_2-1\right]$ and $S\left[p_1+l\right] neq S\left[p_2+l\right]$. 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\left(n+z\right)$ time using a suffix tree , if there are $z$ such structures.

## Example

`12345678901234`
`xabcyabcwabcyz`

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

## References

Search another word or see Maximal pairon Dictionary | Thesaurus |Spanish