Maximal pair

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]\neq S[p_{2}-1]$ and $S[p_{1}+l]\neq 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 $\Theta (n+z)$ time using a suffix tree,^[1] if there are $z$ such structures.

Example

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

$(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.

References

^ 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

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.

[Gus97-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.

[1]