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, but is not, as
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.|