Given a string of length , a maximal pair is a tuple

Tuple

In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...

 , such that , but and . 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 time using a suffix tree

Suffix tree

In computer science, a suffix tree is a data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many important string operations.The suffix tree for a string S is a tree whose edges are labeled with strings, such that each suffix...

, if there are such structures.

Example

12345678901234
xabcyabcwabcyz

and are maximal pairs, but is not, as y follows both substrings. abc and abcy are maximal repeats, but only abcy is a supermaximal repeat.