Maximal pair
From Wikipedia, the free encyclopedia
Given a string S of length n, a maximal pair is a tuple (p1,p2,l), such that S[p1..p1 + l − 1] = S[p2..p2 + l − 1], 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 Θ(n + z) time using a suffix tree [1], if there are z such structures.
[edit] Example
12345678901234 xabcyabcwabcyz
(2,6,3) and (6,10,3) are maximal pairs, but (2,10,3) is not, as y
follows both substrings. abc
and abcy
are maximal repeats, but only abcy
is a supermaximal repeat.
[edit] References
- ^ Gusfield, Dan [1997] (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press, 143. ISBN 0-521-58519-8.