Maximal pair
In computer science, a maximal pair within a string is a pair of matching substrings that are maximal, where "maximal" means that it is not possible to make a longer matching pair by extending the range of both substrings to the left or right.
Example
For example, in this table, the substrings at indices 2 to 4 and indices 6 to 8 are a maximal pair, because they contain identical characters, and they have different characters to the left and different characters to the right. Similarly, the substrings at indices 6 to 8 and indices 10 to 12 are a maximal pair.However, the substrings at indices 2 to 4 and indices 10 to 12 are not a maximal pair, as the character
y follows both substrings, and so they can be extended to the right to make a longer pair.Formal definition
Formally, a maximal pair of substrings with starting positions and respectively, and both of length, is specified by a triple, such that, given a string of length,, but and . Thus, in the example above, the maximal pairs are and, and is not a maximal pair.Related concepts and time complexity
A maximal repeat is the string represented by a maximal pair. A supermaximal repeat is a maximal repeat never occurring as a proper substring of another maximal repeat. In the above example,abc and abcy are both maximal repeats, but only abcy is a supermaximal repeat.Maximal pairs, maximal repeats and supermaximal repeats can each be found in time using a suffix tree, if there are such structures.