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.
