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, if there are such structures.
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.
abcy are maximal repeats, but only
abcy is a supermaximal repeat.
- Gusfield, Dan (1999) . Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. p. 143. ISBN 0-521-58519-8.
- Project for the computation of all maximal repeats in one ore more strings in Python, using suffix array.
|This computer science article is a stub. You can help Wikipedia by expanding it.|