Maximal pair

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computer science, a maximal pair is a tuple , such that, given a string of length , , 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,[1] if there are such structures.


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

and are maximal pairs as the referenced substrings do not share identical characters to the left or the right.

is not, as the character y follows both substrings.

abc and abcy are maximal repeats, but only abcy is a supermaximal repeat.


  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. 

External links[edit]