In computer science, a maximal pair is a tuple ( p 1 , p 2 , l ) , such that, given a string S of length n , S [ p 1 . . p 1 + l − 1 ] = S [ p 2 . . p 2 + l − 1 ] , but S [ p 1 − 1 ] ≠ S [ p 2 − 1 ] and S [ p 1 + l ] ≠ S [ p 2 + l ] . 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 Θ ( n + z ) time using a suffix tree, if there are z such structures.
( 2 , 6 , 3 ) and ( 6 , 10 , 3 ) are maximal pairs as the referenced substrings do not share identical characters to the left or the right.
( 2 , 10 , 3 ) is not, as the character y follows both substrings.
abc and abcy are maximal repeats, but only abcy is a supermaximal repeat.
