Glossary

A maximal repeat of a string $s$ is a repeated substring $t$ having two occurrences $t_1$ and $t_2$ in $s$ such that $t_1$ and $t_2$ cannot be extended by one symbol in either direction in $s$ and still agree.

For example, "AG" is a maximal repeat in "TAGTTAGCGAGA" because even though the first two occurrences of "AG" can be extended left into "TAG", the first and third occurrences differ on both sides of the repeat; thus, we conclude that "AG" is a maximal repeat. Note that "TAG" is also a maximal repeat of "TAGTTAGCGAGA", since its only two occurrences do not still match if we extend them in either direction.