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

edit
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

For example, in this table, the substrings at indices 2 to 4 (in red) and indices 6 to 8 (in blue) are a maximal pair, because they contain identical characters (abc), and they have different characters to the left (x at index 1 and y at index 5) and different characters to the right (y at index 5 and w at index 9). Similarly, the substrings at indices 6 to 8 (in blue) and indices 10 to 12 (in green) are a maximal pair.

However, the substrings at indices 2 to 4 (in red) and indices 10 to 12 (in green) 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

edit

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  ,   (meaning that the substrings have identical contents), but   (they have different characters to their left) and   (they also have different characters to their right; together, these two inequalities are the condition for being maximal). Thus, in the example above, the maximal pairs are   (the red and blue substrings) and   (the green and blue substrings), and   is not a maximal pair.

edit

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,[1] if there are   such structures.

References

edit
  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.
edit