Efficiently Finding All Maximal α-gapped Repeats
Paweł Gawrychowski1 , Tomohiro I2 , Shunsuke Inenaga3 , Dominik
Köppl2 , and Florin Manea4
1
2
3

arXiv:1509.09237v1 [] 30 Sep 2015

4

Institute of Informatics, University of Warsaw, Poland,
gawry@mimuw.edu.pl
Department of Computer Science, TU Dortmund, Germany
{tomohiro.i,dominik.koeppl}@cs.tu-dortmund.de
Department of Informatics, Kyushu University, Japan
inenaga@inf.kyushu-u.ac.jp
Department of Computer Science, Kiel University, Germany
flm@informatik.uni-kiel.de

Abstract
For α ≥ 1, an α-gapped repeat in a word w is a factor uvu of w such that |uv| ≤ α|u|; the
two factors u in such a repeat are called arms, while the factor v is called gap. Such a repeat
is called maximal if its arms cannot be extended simultaneously with the same symbol to the
right or, respectively, to the left. In this paper we show that the number of maximal α-gapped
repeats that may occur in a word is upper bounded by 18αn. This allows us to construct an
algorithm finding all the maximal α-gapped repeats of a word in O(αn); this is optimal, in the
worst case, as there are words that have Θ(αn) maximal α-gapped repeats. Our techniques can
be extended to get comparable results in the case of α-gapped palindromes, i.e., factors uvu|
with |uv| ≤ α|u|.

1

Introduction

Gapped repeats and palindromes are repetitive structures occurring in words that were
investigated extensively within theoretical computer science (see, e.g., [9, 2, 12, 13, 14, 3, 5,
4, 8, 6, 15] and the references therein) with motivation coming especially from the analysis
of DNA and RNA structures, where they were used to model different types of tandem and
interspersed repeats as well as hairpin structures; such structures are important in analyzing
the structural and functional information of the genetic sequences (see, e.g., [9, 2, 13]).
Following [13, 14], we study gapped repeats (palindromes) uvu (respectively, uvu| ) where
the length of the gap v is upper bounded by the length of the arm u multiplied by some
factor, also known as α-gapped repeats and α-gapped palindromes occurring in a word.
The work on α-gapped palindromes was focused so far on combinatorial and algorithmic
problems that extend the classical results obtained for squares and palindromes. Namely,
problems like how many maximal α-gapped repeats or palindromes does a word of length
n contain (here maximal means that the arms of the repeat cannot be both extended to
the right or left with the same symbol), how efficiently can we compute the set of maximal
α-gapped repeats or palindromes of a word, how efficiently can we compute the longest
α-gapped repeat or palindrome, were investigated (see, for instance, [13, 2, 14, 8, 15, 4], and
the references therein). In this paper we obtain the following results:
The number of maximal α-gapped repeats in a word of length n is at most 18αn.
We can compute the list of all α-gapped repeats in O(αn) time for integer alphabets.
Our techniques can be extended to show that the number of maximal α-gapped palindromes
in a word of length n is upper bounded by 28αn + 7n; they can be found in O(αn) time. As
licensed under Creative Commons License CC-BY
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

2

Efficiently Finding All Maximal α-gapped Repeats

there are words of length n that contain Θ(αn) maximal α-gapped repeats or palindromes (see
[14]), it follows that the bounds on the number of maximal α-gapped repeats or palindromes
we obtained are asymptotically tight, and that we cannot hope for algorithms finding all
α-gapped repeats or palindromes faster in the worst case.
Our results improve those of [14] (as well as those existing in the literature before [14]),
where the size of the set of maximal α-gapped repeats with non-empty gap is shown to be
O(α2 n), and can be computed in O(α2 n) time for integer alphabets. An alternative proof of
the fact that the number of maximal α-gapped repeats in a word of length n is O(αn) was
given in the very recent [4]; however, compared to the respective paper, we give a more direct
proof of the O(αn) upper bound as well as a concrete evaluation of the constant hidden by
the O-denotation. In [4, 15] algorithms producing all the maximal α-gapped repeats of a
word were given; in the light of the upper bound O(αn) on the number of maximal α-gapped
repeats that may occur in a word of length n, it follows that these algorithms work in O(αn)
time, but only for constant alphabets. Extending the approach in [8], we show here that, in
fact, such algorithms can be also designed for integer alphabets; our algorithm requires a
deeper analysis than the one developed in [8] for finding the longest α-gapped repeat, and
uses essentially different techniques and data structures than the ones in [4, 15].

2

Combinatorics on words preliminaries

Let Σ be a finite alphabet; Σ∗ denotes the set of all finite words over Σ. The length of a
word w ∈ Σ∗ is denoted by |w|. The empty word is denoted by ε. A word u ∈ Σ∗ is a
factor of v ∈ Σ∗ if v = xuy, for some x, y ∈ Σ∗ ; we say that u is a prefix of v, if x = ε,
and a suffix of v, if y = ε. We denote by w[i] the symbol occurring at position i in w, and
by w[i, j] the factor of w starting at position i and ending at position j, consisting of the
catenation of the symbols w[i], . . . , w[j], where 1 ≤ i ≤ j ≤ n; we define w[i, j] = ε if i > j.
By w| we denote the mirror image of w. A period of a word w over Σ is a positive integer
p such that w[i] = w[j] for all i and j with i ≡ j (mod p); a word that has period p is also
called p-periodic. Let per(w) be the smallest period of w. A word w with per(w) ≤ |w|
2 is
called periodic; otherwise, w is called aperiodic. It is worth noting that the length of the
overlap between two consecutive occurrences of an aperiodic factor v in w is upper bounded
by |v|
2 .
By I = [b, e] we represent the set of consecutive integers from b to e, for b ≤ e, and
call I an interval. For an interval I, we use the notations b(I) and e(I) to denote the
beginning and end of I; i.e., I = [b(I), e(I)]. We write |I| to denote the length of I; i.e.,
|I| = e(I) − b(I) + 1. A subword u of a word w is a pair (s, [b, e]) consisting of a factor
s of w and an interval [b, e] in w such that s = w[b, e]. While a factor is identified only by
a sequence of letters, a subword is also identified by its position in the word. So subwords
are always unique, while a word may contain multiple occurrences of the same factor. For
two subwords u and u of a word w, we write u = u if they start at the same position in w
and have the same length. We write u ≡ u if the factors identifying these subwords are the
same. We implicitly use subwords both like factors of w and as intervals contained in [1, |w|],
e.g., we write u ⊆ u if two subwords u = (s, [b, e]), u = (s, [b, e]) of w satisfy [b, e] ⊆ [b, e],
i.e., b(u) ≤ b(u) ≤ e(u) ≤ e(u). Two subwords u and u of the same word w are called
consecutive, iff e(u) + 1 = b(u).
For a word w, we call a triple of consecutive subwords uλ , v, uρ a gapped repeat with
period |uλ v| and gap |v| iff uρ ≡ uλ . A triple of consecutive subwords uλ , v, uρ is called
a gapped palindrome with gap |v| iff uρ ≡ uλ | . The subwords uλ and uρ are called left

Gawrychowski et al.

3

and right arm, respectively. For α ≥ 1, the gapped repeat (palindrome) uλ , v, uρ is called
α-gapped iff |uλ | + |v| ≤ α |uλ |. Further, it is called maximal iff that w[b(uλ ) − 1] 6=
w[b(uρ ) − 1] and w[e(uλ ) + 1] 6= w[e(uρ ) + 1], and for a gapped palindrome uλ , v, uρ that
w[b(uλ ) − 1] 6= w[e(uρ ) + 1] and w[e(uλ ) + 1] 6= w[b(uρ ) − 1]. Let Gα (w) (respectively, Gα| (w))
denote the set of maximal α-gapped repeats (palindromes) in w. The representation of a
maximal gapped repeat (palindrome) by the subword z := w[uλ ]w[v]w[uρ ] is not unique —
the same subword z can be composed of gapped repeats (palindromes) with different periods
(different gaps). Instead, a maximal gapped repeat (palindrome) is uniquely determined by
its left arm uλ and its period (gap). By fixing w, we therefore can map uλ , v, uρ injectively
to the pair of integers (e(uλ ), |uλ v|) in case of a gapped repeat, or to (e(uλ ), |v|) in case of a
gapped palindrome.
A run in a word w is a maximal periodic factor; the exponent of a run is the number of
times the period fits in that run. For a word w, let R(w) and E(w) denote the number of
runs and the sum of the exponents of runs in w, respectively. The exponent of a run r is
denoted by exp(r). We use the following results from literature:
I Lemma 1 ([1]). For a word w, E(w) < 3 |w|.
I Lemma 2 ([14]). Two distinct maximal repetitions with the same minimal period p cannot
have an overlap of length greater than or equal to p.
I Corollary 3 ([14]). If a square uu is primitive, any word v contains no more than |v|/|u|
occurrences of uu.
I Lemma 4. Inverting a gapped repeat (palindrome) results in a gapped repeat (palindrome)
with the same period. Hence there exist the bijections Gα (w) ∼ Gα (w| ) and Gα| (w) ∼ Gα| (w| ).

3

Point analysis

A pair of positive integers is called a point. We use points to bound the cardinality of a
subset of gapped repeats and gapped palindromes by injectively mapping a gapped repeat
(palindrome) to a point as stated above. To this end, we show that some vicinity of any
point generated by a member of this subset does not contain any point that is generated by
another member. This vicinity is given by
I Definition 5. For any γ ∈ (0, 1], we say that a point (x, y) γ-covers a point (x0 , y 0 ) iff
x − γy ≤ x0 ≤ x and y − γy ≤ y 0 ≤ y.
It is crucial that the γ factor is always multiplied with the y-coordinates. In other words, the
number of γ-covers of a point (·, y) correlates with γ and the value y. The main property of
this definition is given by
2

I Lemma 6. For any γ ∈ (0, 1], let S ⊂ [1, n] be a set of points such that no two distinct
points in S γ-cover the same point. Then |S| < 3n/γ.
2

Proof. We estimate the maximal number of points that can be placed in [1, n] such that
2
their covered points are disjoint. First, the number of points (·, y) ∈ [1, n] with y < 1/γ is
less than n/γ. Second, if a point (·, y) satisfies 2l /γ ≤ y < 2l+1 /γ for some integer l ≥ 0, the
point (·, y) γ-covers at least 2l × 2l points, or to put it differently, this point γ-covers at least
2l points (·, y 0 ) with y − 2l ≤ y 0 ≤ y. In other words, there are at most n/(2l γ) points in S
P∞
with 2l /γ ≤ y < 2l+1 /γ. Hence, |S| < n/γ + l=0 n/(2l γ) = 3n/γ.
J

4

Efficiently Finding All Maximal α-gapped Repeats

Kolpakov et al. [14] split the set of maximal α-gapped repeats into three subsets, and
studied the maximal size of each subset. They analyzed maximal α-gapped repeats by
partitioning them into three subsets: those contained in some repetition, those having arms
containing a periodic prefix or suffix that is larger than half of the size of the arms, and
those not belonging to both former subsets.
They showed that the first two subsets contain at most O(αn) elements. The point
analysis is used as a tool for studying the last subset. By mapping a gapped repeat to a
point consisting of the end position of its left arm and its period, they showed that the points
1
created by two different maximal α-gapped repeats cannot 4α
-cover
the same point. By

this property, they bounded the size of the last subset by O α2 n . Lemma 6 immediately
improves this bound of O α2 n to O(αn). Consequently, it shows that the number of
maximal α-gapped repeats of a word of length n is O(αn).

4

Gapped repeats

We optimize the proof technique from [14] and improve the upper bound of the number
of maximal α-gapped repeats in a word of length n from O(αn) to 18αn. Unlike [14, 4],
we partition the maximal α-gapped repeats differently. We categorize a gapped repeat
(palindrome) depending on whether their left arm contains a periodic prefix or not. Both
subsets are treated differently. For the ones having an periodic prefix, we think about the
number of runs covering this prefix. The other category is analyzed by using the results of
Section 3. We begin with a formal definition of both subsets and analyze the former subset.
Let 0 < β < 1. A gapped repeat (palindrome) σ = uλ , v, uρ belongs to βPα (w) (βP |α (w))
iff uλ contains a periodic prefix of length at least β |uλ |. We call σ periodic. Otherwise σ ∈
|
|
βP α (w) (σ ∈ βP α (w)), where βP α (w) := Gα (w) \ βPα (w) and βP α (w) := Gα| (w) \ βP |α (w);
we call σ aperiodic.
I Lemma 7. Let w be a word, α > 1 and 0 < β < 1 two real numbers. Then |βPα (w)| is at
most 2αE(w)/β.
Proof. Let σ = (uλ , v, uρ ) ∈ βPα (w). By definition, the left arm uλ has a periodic prefix sλ
of length at least β |uλ |. Let rλ denote the run that generates sλ , i.e., sλ ⊆ rλ and they both
have the common shortest period p. By the definition of gapped repeats, there is a right
copy sρ of sλ contained in uρ with sρ = w[b(sλ ) + |uλ v| , e(sλ ) + |uλ v|] ≡ sλ .
Let rρ be a run generating sρ (it is possible that rρ and rλ are identical). By definition,
rρ has the same period p as rλ . In the following, we will see that σ is uniquely determined
by rλ and the period q := |uλ v|, if σ is a periodic gapped repeat. We will fix rλ and pose
the question how many maximal periodic gapped repeats can be generated by rλ .
Since σ is maximal, b(uλ ) = b(rλ ) or b(uρ ) = b(rρ ) must hold; otherwise we could extend
σ to the left. We analyze the case b(sλ ) = b(rλ ), the other is treated exactly in the same
way by symmetry. The gapped repeat σ is identified by rλ and the period q. We fix rλ and
count the number of possible values for the period q. Given two different gapped repeats σ1
and σ2 with respective periods q1 and q2 such that the left arms of both are generated by rλ ,
the difference δ between q1 and q2 must be at least p.
Since |uλ | ≤ |sλ | /β and σ is α-gapped, 1 ≤ q ≤ |sλ | α/β ≤ |rλ | α/β. Then the number
of possible periods q is bounded by |rλ | α/(βp) = exp(rλ )α/β. Therefore the number of
maximal α-gapped repeats is bounded by αE(w)/β for the case b(uλ ) = b(rλ ). Summing up
we get the bound 2αE(w)/β.
J

Gawrychowski et al.

5

Remembering the results of Section 3, we map gapped repeats to their respective points.
By using the period as the y-coordinate, one can show Lemma 8.
I Lemma 8. Given a word w, and two real numbers α > 1 and 2/3 ≤ β < 1. The points
mapped by two different maximal gapped repeats in βP α (w) cannot 1−β
α -cover the same point.
Proof. Let σ = uλ , v, uρ and σ = uλ , v, uρ be two different maximal gapped repeats
in βP α (w). Set u := |uλ | = |uρ |, u := |uλ | = |uρ |, q := |uλ v| and q := |uλ v|. We
map the maximal gapped repeats σ and σ to the points (e(uλ ), q) and (e(uλ ), q), respectively.
Assume, for the sake of contradiction, that both points 1−β
α -cover the same point (x, y).
Let z := |e(uλ ) − e(uλ )| be the difference of the endings of both left arms, and sλ :=
w[[b(uλ ), e(uλ )] ∩ [b(uλ ), e(uλ )]] be the overlap of uλ and uλ . Let s := |sλ |, and let sρ (resp.
sρ ) be the right copy of sλ based on σ (resp. σ).
Sub-Claim: The overlap sλ is not empty, and sρ 6= sρ
Sub-Proof. Assume for this sub-proof that e(uλ ) < e(uλ ) (otherwise exchange σ with σ,
or yield the contradiction σ = σ). By combining the (1 − β)/α-cover property with the
fact that σ is α-gapped, we yield e(uλ ) − u ≤ e(uλ ) − q(1 − β)/α ≤ x ≤ e(uλ ) < e(uλ ). So
the subword w[e(uλ )] is contained in uλ . If sρ = sρ , then we get a contradiction to the
maximality of σ: By the above inequality, w[e(uλ ) + 1] is contained in uλ , too. Since σ is a
gapped repeat, the character w[e(uλ ) + 1] occurs in uρ , exactly at w[e(uρ ) + 1].
J
Without loss of generality let q ≤ q. Then
q(1 − β)
≤ y ≤ q ≤ q.
α
So the difference of both periods is 0 ≤ δ := q − q ≤ q(1 − β)/α ≤ u(1 − β).
1−β
q
Equation (1) also yields that u ≥ q/α ≥ (1 −
) ≥ qβ/α.
α
α
q−

(1)
(2)
(3)

Since sρ = [b(sλ ) + q, e(sλ ) + q] and sρ = [b(sλ ) + q, e(sλ ) + q], we have b(sρ ) − b(sρ ) = δ.
By case analysis, we show that uλ or uλ has a periodic prefix, which leads to the
contradiction that σ or σ are in βPα (w).
1. Case e(uλ ) ≤ e(uλ ). Since e(uλ ) − q(1 − β)/α ≤ x ≤ e(uλ ) ≤ e(uλ ),
z = e(uλ ) − e(uλ ) ≤ q(1 − β)/α ≤ u(1 − β).
uλ

uρ

v
uλ

sλ

(4)

uρ

v
sρ

z
δ

sρ

Figure 1 Sub-Case 1a

1a. Sub-Case b(uλ ) ≤ b(uλ ). By Equation (4), we get s = u − z ≥ uβ. It follows
from Equation (2) and 2/3 ≤ β < 1 that s/δ ≥ uβ/u(1 − β) = β/(1 − β) ≥ 2, which means
that sρ and sρ overlap at least half of their common length, so sλ is periodic. Since sλ is a
prefix of uλ of length s ≥ uβ, σ is in βPα (w), a contradiction.
1b. Sub-Case b(uλ ) > b(uλ ). We conclude that sλ = uλ . It follows from Equations (2)
and (3) and 2/3 ≤ β < 1 that s/δ ≥ qαβ/(qα(1 − β)) = β/(1 − β) ≥ 2, which means that
sλ = uλ is periodic. Hence σ is in βPα (w), a contradiction.
2. Case e(uλ ) > e(uλ ). Since e(uλ ) − q(1 − β)/α ≤ x ≤ e(uλ ) ≤ e(uλ ),
z = e(uλ ) − e(uλ ) ≤ q(1 − β)/α ≤ q(1 − β)/α ≤ u(1 − β).

(5)

6

Efficiently Finding All Maximal α-gapped Repeats

uλ
uλ
sλ

uρ

v

uρ

v
sρ

z

sρ

δ
Figure 2 Sub-Case 1b

uλ
uλ
sλ

uρ

v

uρ

v
sρ

z

sρ

δ
Figure 3 Sub-Case 2a

2a. Sub-Case b(uλ ) ≤ b(uλ ). We conclude that sλ = uλ . It follows from Equation (2)
and 2/3 ≤ β < 1 that s/δ ≥ u/(u(1 − β)) = 1/(1 − β) ≥ 3 > 2, which means that sλ = uλ is
periodic. Hence σ is in βPα (w), a contradiction.
uλ
uλ
sλ

uρ

v
v

uρ
sρ

z
δ

sρ

Figure 4 Sub-Case 2b

2b. Sub-Case b(uλ ) > b(uλ ). By Equation (5), we get s = u − z ≥ uβ. If δ ≤ s/2, sρ
and sρ overlap at least half of their common length, which leads to the contradiction that
uλ has a periodic prefix sλ of length at least uβ. Otherwise, let us assume that s/2 < δ.
By Equations (2) and (3) we get u/δ ≥ qαβ/(qα(1 − β)) = β/(1 − β) ≥ 2 with 2/3 ≤ β < 1.
Hence, δ is upper bounded by u/2; so uρ has a periodic prefix of length at least 2δ (since
2δ > s ≥ uβ), a contradiction.
J
The next lemma follows immediately from Lemmas 6 and 8.
I Lemma 9. For α > 1, 2/3 ≤ β < 1 and a word w of length n, βP α (w) < 3αn/(1 − β).
I Theorem 10. Given a word w of length n, and a real number α > 1. Then |Gα (w)| < 18αn.
Proof. Combining the results of Lemmas 7 and 9, |Gα (w)| = |βPα (w)| + βP α (w) <
2αE(w)/β + 3αn/(1 − β) for 2/3 ≤ β < 1. Applying Lemma 1, the term is upper bounded
by 6αn/β + 3αn/(1 − β). The number is minimal for β = 2/3, yielding the bound 18αn. J
We can bound the number of maximal α-gapped palindromes by similar proofs to
28αn + 7n. This bound solves an open problem in [13], where Kolpakov and Kucherov
conjectured that the number of α-gapped palindromes with α ≥ 2 in a string is linear. We
briefly explain the main differences and similarities needed to understand the relationship
between gapped repeats and palindromes. Let σ be a maximal α-gapped repeat (or α-gapped
palindrome). If the gapped repeat (palindrome) has a periodic prefix sλ generated by some
run, the right arm has a periodic prefix (suffix) sρ generated by a run of the same period.
Since σ is maximal, both runs have to obey constraints that are similar in both cases,
considering whether σ is a gapped repeat or a gapped palindrome. So it is easy to change the
proof of Lemma 7 in order to work with palindromes. Like with aperiodic gapped repeats, we

Gawrychowski et al.

can apply the point analysis to the aperiodic α-gapped palindromes, too. As main idea, we
map a gapped palindrome uλ , v, uρ injectively to the pair of integers (e(uλ ), |v|), exchanging
the period with the size of the gap. See appendix for proofs.

5

Algorithms

The computational model we use to design and analyze our algorithms is the standard unitcost RAM with logarithmic word size, which is generally used in the analysis of algorithms.
In the upcoming algorithmic problems, we assume that the words we process are sequences
of integers. In general, if the input word has length n then we assume its letters are in
{1, . . . , n}, so each letter fits in a single memory-word. This is a common assumption in
stringology (see, e.g., the discussion in [10]). For a word w, |w| = n, we build in O(n) time
the suffix array as well as data structures allowing us to retrieve in constant time the length
of the longest common prefix of any two suffixes w[i, n] and w[j, n] of w, denoted LCP w (i, j)
(the subscript w is omitted when there is no danger of confusion). Such structures are called
LCP data structures in the following (see, e.g., [10, 9]). We begin with a simple lemma.
I Lemma 11. Given a word w, |w| = n, we can process it in O(n) time such that, for each
i, p ≤ n, we can return in O(1) time the longest factor of period p starting at position i in w.
Let w be a word and v be a factor of w with per(v) = p. Further, let z be a subword
of length `|v| of w. An occurrence of v in z is a subword (v, [i, i + |v| − 1]) of z; we say
that v occurs at position i in z. For an easier presentation of our algorithm, we distinguish
between two types of occurrences of v in z. On the one hand, we have the so-called single
occurrences. If v is aperiodic, then all its occurrences in z are single occurrences; there are
O(`) such occurrences (see, e.g., [11]). If v is periodic, then a subword (v, [i, i + |v| − 1]) of
z starting on position i in z is a single occurrence if v occurs neither at position i − p nor
at position i + p in z. On the other hand, we have occurrences of v within a run of z,
whose period is p = per(v). That is, the subword (v, [i, i + |v| − 1]) starting on position i
in z is an occurrence of v within a run if v occurs either at i − p or at i + p. We say that
(v, [i, i + |v| − 1]) is the first occurrence of v in a run of period p of z if v does not occur
at i − p but occurs at i + p. Note that there are O(`) runs containing occurrences of v in z,
or, equivalently, O(`) first occurrences of v in a run of period p.
Consequently, the occurrences of v in z can be succinctly represented as follows. For
the single occurrences we just store their starting position. The occurrences of v in a run r
can be represented by the starting position of the first occurrence of v in r, together with
the period of v, since the starting positions of the occurrences of v in r form an arithmetic
progression of period p.
In our approach, basic factors (i.e., factors of length 2k , for k ≥ 1) of the input word are
important. For some integer c ≥ 2, the occurrences of the basic factor w[i, i + 2k − 1] in a
subword of length c2k can be represented in a compact manner: O(c) positions of the single
occurrences of w[i, i + 2k − 1] and O(c) first occurrences of w[i, i + 2k − 1] in runs, together
with the period of w[i, i + 2k − 1]. We recall the next lemma (see [8, 11], appendix).
I Lemma 12. Given a word w of length n and an integer c ≥ 2, we can process w in
time O(n log n) such that given any basic factor y = w[i, i + 2k − 1] and any subword of w
(z, [j, j + c2k − 1]), with k ≥ 0, we can compute in O(log log n + c) time the representation of
all the (single and within runs) occurrences of y in z.
We now focus on short basic factors of words. The constant 16 occurring in the following
considerations can be replaced by any other constant; we just use it here so that we can

7

8

Efficiently Finding All Maximal α-gapped Repeats

apply these results directly in the main proofs of this section.
Given a word v and some integer β ≥ 16 with |v| = β log n, as well as a basic factor
y = v[i2k + 1, (i + 1)2k ], with i, k ≥ 0 and i2k + 1 > (β − 16) log n (so occurring in the suffix
of length 16 log n of v), the occurrences of y in v can be represented as O(β) bit-sets, each
containing O(log n) bits, the 1-bits marking the starting positions of the occurrences of y in
v. The next result can be shown using tools developed in [7] (see also [8] and the appendix).
I Lemma 13. Given a word v and an integer β > 16, with |v| = β log n, we can process
v in time O(β log n) time such that given any basic factor y = v[i2k + 1, (i + 1)2k ] with
i, k ≥ 0 and i2k + 1 > (β − 16) log n, we can find in O(β) time the O(β) bit-sets, each storing
O(log n) bits, characterizing all the occurrences of y in v.
In the context of the previous lemma, once the occurrences of y in v are computed, given
a subword z of v of length |z| = c|y|, for some c ≥ 1, we can obtain in O(c) time both the
single occurrences of y in z and the occurrences of y within runs of z. We just have to select
(by bitwise operations on the bit-sets encoding the factors of v that overlap z) the positions
where y occurs (so the positions of the 1-bits in those bit-sets). For each two consecutive
such occurrences of y we detect whether they are part of a run in v and then skip over all the
occurrences of y from that run (and the corresponding parts of the bit-sets) before looking
again for 1-bits in the bit-sets; for the positions that form a run we store the first occurrence
of y and its period, while for the single occurrences we store the position of that occurrence.
Now we can begin the presentation of the algorithm finding all the maximal α-gapped
repeats of a word. We first show how to find maximal repeats with short arms.
I Lemma 14. Given a word w and α ≥ 1, we can find all the maximal α-gapped repeats
uλ , u0 , uρ occurring in w, with |uρ | ≤ 16 log n, in time O(αn).
Proof. If a maximal α-gapped repeat uλ , u0 , uρ (where we denote by u the underlying
factor of both arms), has |u| ≤ 16 log n, we get that uρ must be completely contained in
a subword (w0 , [m log n + 1, (m + 17) log n]), for some m with logn n − 17 ≥ m ≥ 0. By
fixing the interval where uρ may occur (that is, fix m), we also fix the place where uλ
may occur. Indeed, the entire subword uλ , u0 , uρ is completely contained in the factor
xm = (w00 , [(m − 16α) log n + 1, (m + 17) log n]) (or, in a factor xm = (w00 , [1, (m + 17) log n])
if (m − 16α) log n + 1 < 1).
Hence, we look for maximal α-gapped repeats uλ , u0 , uρ completely contained in xm with
uρ completely contained in the suffix of length 16 log n of xm ; then we repeat this process for
all m. To begin with, we process xm as in Lemma 13, and construct LCP-structures for it.
Now, once we fixed the subword xm of w where we search the maximal α-gapped repeats,
we try to fix also their length. That is, we find all maximal α-gapped repeats uλ , u0 , uρ with
2k+1 ≤ |u| ≤ 2k+2 completely contained in xm with uρ completely contained in the suffix of
length 16 log n of xm ; we execute this process for all 0 ≤ k ≤ log(16 log n). Note that all the
maximal α-gapped repeats with arms shorter than 2 (occurring anywhere in the word w)
can be trivially found in O(αn) time.
Since we can find occurrences of basic factors in xm efficiently, we try to build a maximal
gapped repeat by extending gapped repeats whose arms contain a basic factor (see Figure 12
in the appendix). To this end, we analyze some subwords of xm : If 2k+1 ≤ |u| ≤ 2k+2 then
uρ contains at least one subword (y, [j2k + 1, (j + 1)2k ]) starting within its first 2k positions.
A copy of the factor y occurs also within the first 2k positions of uλ (with the same offset
with respect to the starting position of uλ as the offset of the occurrence of y with respect to
the starting position of uρ ). So, finding the respective copy of y from uλ helps us discover

Gawrychowski et al.

the place where uλ actually occurs. Indeed, assume that we identified the copy of y from uλ ,
and assume that this copy is (y, [` + 1, ` + |y|]); we try to build uλ and uρ around these two
occurrences of y, respectively. Hence, in order to identify uλ and uρ we compute the longest
factor p of xm that ends both on j2k and on ` and the longest factor s that starts both on
(j + 1)2k + 1 and on ` + |y| + 1. Now, if ` + |y| + |s| ≤ j2k − |p| then uλ is obtained by
concatenating p and s around xm [` + 1, ` + |y|] while uρ is obtained by concatenating p and
s to the left and, respectively, right of xm [j2k + 1, (j + 1)2k ]; otherwise, the two occurrences
of y do not determine a maximal repeat. Moreover, the repeat we determined is a valid
solution of our problem only if its length is between 2k+1 and 2k+2 , and its right arm contains
position j2k + 1 of xm within its first 2k positions.
Now we explain how to determine efficiently the copy of y around which we try to build uλ .
As |u| < 2k+2 and |y| = 2k we get that the copy of y that corresponds to uλ should be
completely contained in the subword of xm of length α2k+2 ending on position j2k . As said
above, we already processed xm to construct the data structures from Lemma 13. Therefore,
we can obtain in O(α) time a representation of all the occurrences of y inside the factor
of length α2k+2 ending on position j2k . These occurrences can be single occurrences and
occurrences within runs. There are O(α) single occurrences, and we can process each of them
individually, as explained, to find the maximal α-gapped repeat they determine together with
the occurrence of y from uρ . However, it is not efficient to do the same for the occurrences
of y within runs. For these (which are also O(α) many) we proceed as follows.
Assume we have a run of occurrences of y inside the factor of xm of length α2k+2 ending
on position j2k . Let ` be the starting position of the first occurrence of y in this run and let p
be the period of y. Now, using Lemma 11 we can determine the maximal p-periodic subword
rλ of xm containing this run of y-occurrences. Similarly, we can determine the maximal
p-periodic subword rρ that contains the occurrence of y from uρ (i.e., xm [j2k + 1, (j + 1)2k ]).
To determine efficiently the α-gapped repeats that contain xm [j2k + 1, (j + 1)2k ] in the right
arm and a corresponding occurrence of y from rλ in the left arm we analyze several cases
(see Figure 13 in the appendix).
Assume uρ starts on a position of rρ , other than its first one. Then uλ should also start
on the first position of rλ (or we could extend both arms to the left, a contradiction to the
maximality of the repeat). If uρ ends on a position to the right of rρ , then uλ also ends
on a position to the right of rλ , and, moreover, the suffix of uλ occurring after the end of
rλ and the suffix of uρ occurring after the end of rρ are equal, and can be computed by a
longest common prefix query on xm . This means that uλ can be determined exactly (we
know where it starts and where it ends) so uρ can also be determined exactly (we know
where it ends), and we can check if the obtained repeat is indeed a maximal α-gapped repeat,
and the arms fulfill the required length conditions (i.e., length between 2k+1 and 2k+2 , the
right arm contains position j2k + 1 of xm within its first 2k positions). If uρ ends exactly on
the same position as rρ then uρ is periodic of period p; we just have to compute the longest
p-periodic factor that ends on the same position as rρ and starts at the same position as rλ ,
and this can also be determined in constant time just by taking the longest p-periodic prefix
of rλ which is also a suffix of rρ . So, again, we can determine exactly uλ and uρ , and we can
check if they form a maximal α-gapped repeat with the arms fulfilling the length restrictions.
The final, and more complicated case, is when uρ ends on a position of rρ , other than its last
position. In that case, we get that uλ = rλ (or, otherwise, we could extend both arms to the
right). Essentially, this means that we know exactly where uλ is located and its length (and
we continue only if this length is between 2k+1 and 2k+2 ); so uλ denotes a factor z h z 0 for
some z of length p. Now, looking at the run rρ , we can get easily the position of the first

9

10

Efficiently Finding All Maximal α-gapped Repeats

occurrence of z in that run, and the position of its last occurrence. If the first occurrence is
`0 , then the occurrences of z have their starting positions `0 , `0 + p, . . . , `0 + tp for some t.
As we know the length of uλ and the fact that uλ , u0 , uρ is α-gapped, we can determine in
constant time the values 0 ≤ i ≤ t such that uρ may start on position `0 + ip, the repeat we
obtain is α-gapped, and uρ contains position j2k + 1 of xm within its first 2k positions. If uρ
is a prefix of rρ we also have to check that we cannot extend simultaneously uρ and uλ to
the left; if uρ is a suffix of rλ we have to check that we cannot extend simultaneously uρ and
uλ to the right. Then we can return the maximal α-gapped repeats we constructed.
The cases when uρ starts on the first position of rρ or when it starts on a position to the
left of rρ can be treated similarly, and as efficiently (see Appendix).
This concludes our algorithm. Its correctness follows from the explanations above.
Moreover, we can ensure that our algorithm finds and outputs each maximal repeat exactly
once; this clearly holds when we analyze the repeats of xm for each m separately. However,
when moving from xm to xm+1 we must also check that the right arm of each repeat we find
is not completely contained in xm (so, already found). This condition can be easily imposed
in our search: when constructing the arms determined by a single occurrence of y, we check
the containment condition separately; when constructing a repeat determined by a run of
y-occurrences, we have to impose the condition that the right arm extends out of xm when
searching the starting positions of the possible arms.
Next, we compute the complexity of the algorithm. Once we fix m, k, and j, our
process takes O(α + Nj,m,k ) time, where Nj,m,k is the number of maximal α-gapped repeats
determined for the fixed m, j, k. So, the time complexity of the algorithm is:
P
P
P
O(n + 0≤m≤n/ log n (16α log n + 0≤k≤log(16 log n) ( j≤16 log n/2k (α + Nj,m,k )))) ⊆ O(αn),
as the total number of maximal α-gapped repeats is O(αn) and we need O(|xm |) preprocessing
time for each xm and O(n) preprocessing time for w.
J
Next, we find all maximal α-gapped repeats with longer arms.
I Lemma 15. Given a word w and α ≥ 1, we can find all the maximal α-gapped repeats
uλ , u0 , uρ occurring in w, with |uρ | > 16 log n, in time O(αn).
Proof. The general approach in proving this lemma is similar to that used in the proof of
the previous result. Essentially, when identifying a new maximal α-gapped repeat, we try to
fix the place and length of the right arm uρ of the respective repeat, which restricts the place
where the left arm uλ occurs. This allows us to fix some long enough subword of w as being
part of the right arm, detect its occurrences that are possibly contained in the left arm, and,
finally, to efficiently identify the actual repeat. The main difference is that we cannot use the
result of Lemma 13, as we have to deal with repeats with arms longer than 16 log n. Instead,
we will use the structures constructed in Lemma 12. However, to get the stated complexity,
we cannot apply this lemma directly on the word w, but rather on an encoded variant of w.
Thus, the first step of the algorithm is to construct a word w0 , of length logn n , whose
symbols, called blocks, encode log n consecutive symbols of w grouped together. That is, the
first block of the new word corresponds to w[1, log n], the second one to w[log n + 1, 2 log n],
and so on. Hence, we have two versions of the word w: the original one, and the one where it
is split in blocks. It is not hard to see that the blocks can be encoded into numbers between 1
and n in linear time. Indeed, we build the suffix array and LCP-data structures for w, and
then we cluster together the suffixes of the suffix array that share a common prefix of length
at least log n. Then, all the suffixes of a cluster are given the same number (between 1 and
n), and a block is given the number of the suffix starting with the respective block.

Gawrychowski et al.

We can now construct in O(n) time the suffix arrays and LCP-data structures for both
w and w0 , as well as the data structures of Lemma 12 for the word w0 .
Now, we guess the length of the arms of the repeat. We try to find the maximal α-gapped
repeats uλ , u0 , uρ of w with 2k+1 log n ≤ |uλ | ≤ 2k+2 log n, k ≤ log logn n − 2. We fix k and
split again the word w, this time in factors of length 2k log n, called k-blocks. Assume that
each split is exact (padding the word with some new symbols ensures this).
Now, if a maximal α-gapped repeat uλ , u0 , uρ with 2k+1 log n ≤ |uλ | ≤ 2k+2 log n exists,
then it contains an occurrence of a k-block within its first 2k log n positions. So, let z be a
k-block and assume that it is the first k-block occurring in uρ (in this way fixing a range
where uρ may occur). Obviously, if uρ contains z, then uλ also contains an occurrence of z;
however, this occurrence is not necessarily starting on a position j log n + 1 for some j ≥ 0
(so, it is not necessarily a sequence of blocks). But, at least one of the factors of length 2k−1
starting within the first log n positions of z (which are not necessarily sequences of blocks)
must correspond, in fact, to a sequence of blocks from the left arm uλ . So, let us fix now a
factor y of length 2k−1 that starts within the first log n positions of z (we try all of them in
the algorithm, one by one). As said, the respective occurrence of y from uρ is not necessarily
a sequence of blocks (so it cannot be mapped directly to a factor of w0 ). But, we look for an
occurrence of y starting on one of the α2k+2 log n positions to the left of z, corresponding to
a sequence of blocks, and assume that the respective occurrence is exactly the occurrence of
y from uλ .
By binary searching the suffix array of w0 (using LCP-queries on w to compare the factors
of log n symbols of y and the blocks of w0 , at each step of the search) we try to detect a
factor of w0 that encodes a word equal to y. Assume that we can find such a sequence y 0 of
2k−1 blocks of w0 (otherwise, y cannot correspond to a sequence of blocks from uλ , so we
should try other factors of z instead). Using Lemma 12 for w0 , we get in O(log log |w0 | + α)
time a representation of the occurrences of y 0 in the range of α2k+2 blocks of w0 occurring
before the blocks of z; this range corresponds to an interval of w with a length of α2k+2 log n.
Further, we process these occurrences of y 0 just like in the previous lemma. Namely,
the occurrences of y 0 in that range are either single occurrences or occurrences within runs.
Looking at their corresponding factors from w, we note that each of these factors fixes a
possible left arm uλ ; this arm, together with the corresponding arm uρ can be constructed
just like before. In the case of single occurrences (which are at most O(α), again), we try to
extend both the respective occurrence and the occurrence of y from uρ both to the left and,
respectively, to the right, simultaneously, and see if we can obtain in this way the arms of a
valid maximal α-gapped repeat. Note that we must check also that the length of the arm of
the repeat is between 2k+1 and 2k+2 , and that z is the first k-block of the right arm. As
before, complications occur when the occurrences of y 0 are within runs. In this case, the run
of occurrences of y 0 does not necessarily give us the period of y, but a multiple of this period
that can be expressed also as a multiple of log n (or, in other words, the minimum period
of y is a multiple of the block-length). This, however, does not cause any problems, as the
factor y from uρ should always correspond to a block sequence from uλ , so definitely to one
of the factors encoded in the run of occurrences of y 0 .
Therefore, by determining the maximal factor that contains y and has the same period as
the run of occurrences of y 0 (with the period measured in w), we can perform a very similar
analysis to the corresponding one from the case when we searched maximal α-gapped repeats
with arms shorter than 16 log n.
It remains to prove that each maximal gapped repeat is counted only once. Essentially,
the reason for this is that for two separate factors y1 and y2 (of length 2k−1 ) occurring in the

11

12

Efficiently Finding All Maximal α-gapped Repeats

first log n symbols of z we cannot get occurrences of the corresponding factors y10 and y20 that
define the same repeat; in that case, the distance between y10 and y20 should be at least one
block, so the distance between y1 and y2 should be at least log n, a contradiction. Similarly,
if we have a factor y occurring in the first log n symbols of some k-block z1 such that this
factor determines an α-gapped maximal repeat, then the same maximal repeat cannot be
determined by a factor of another k-block, since z1 is the first k-block of uρ .
The correctness of the algorithm described above follows easily from the explanations
given in the proofs of the last two lemmas. Let us evaluate its complexity. The preprocessing
phase (construction of w0 and of all the needed data structures) takes O(n) time. Further,
we can choose k (and implicitly an interval for the length of the arms of the repeats) such
n
that k ≤ log logn n − 2. After choosing k, we can choose a k-block z in 2k log
ways. Further,
n
k−1
we analyze each factor y of length 2
starting within the first log n positions of the chosen
k-block z. For each such factor y we find in O(log logn n + log log n + α) time the representation
of the occurrences of the block encoding the occurrence of y from uλ . From each of the O(α)
single occurrences we check whether it is possible to construct a maximal α-gapped repeat
in O(1) time. We also have O(α) occurrences of the block encoding y in runs, and each of
them is processed in O(Nz,y ) time, where Nz,y is the number of maximal α-gapped repeats
we find for some z and y. Overall, this adds up to a total time of O(n log n + αn), as the
total number of maximal α-gapped repeats in w is upper bounded by O(αn). If α ≥ log n,
the statement of the lemma follows. If α < log n we proceed as follows.
Initially, we run the algorithm only for k > log log n and find the maximal α-gapped
repeats uλ u0 uρ with 2log log n log n ≤ |uλ |, in O(αn) time. Further, we search maximal αgapped repeats with shorter arms. Now, |uλ | is upper bounded by 2log log n+1 log n = 2(log n)2 ,
so |uλ u0 uρ | ≤ `0 , for `0 = α · 2(log n)2 + 2(log n)2 = 2(α + 1)(log n)2 . Such an α-gapped
repeat uλ u0 uρ is, thus, contained in (at least) one factor of length 2`0 of w, starting on a
position of the form 1 + m`0 for m ≥ 0. So, we take the factors w[1 + m`0 , (m + 2)`0 ] of w, for
m ≥ 0, and apply for each such factor, separately, the same strategy as above to detect the
maximal α-gapped
repeats contained completely in each of them. The total time needed to

n
do that is O α`0 `0 + N`0 = O(αn), where N`0 is the number of repeats we find; moreover,
we can easily ensure that a maximal repeat is not output twice (that is, ensure always that
the gapped repeats we produce were not already contained in a previously processed interval).
Hence, we find all maximal α-gapped repeats uλ u0 uρ with 2log log(2`0 ) log(2`0 ) ≤ |u|. This
means we find all the maximal α-gapped repeats with |u| ≥ 2log log(2`0 )+1 log(2`0 ). Since
2log log(2`0 )+1 log(2`0 ) ≤ 16 log n (for n large enough, as α ≤ log n), we can apply Lemma 14
for gapped repeats with an arm-length smaller than 2log log(2`0 )+1 log(2`0 ).
J
Putting together the results of Lemmas 14 and 15 we get the following theorem.
I Theorem 16. Given a word w and α ≥ 1, we can compute Gα (w) in time O(αn).
By a completely similar approach we can compute Gα| (w), generalizing the algorithm
of [13]. To this end, we construct LCP-structures for ww| (allowing us to test efficiently
|
whether a factor w[i, j] occurs at some position in w). When we search the α-gapped
palindromes uλ , v, uρ (with uρ ≡ uλ | ), we split again w in blocks and k-blocks, for each
k ≤ log |w|, to check whether there exists such an uλ , v, uρ with 2k ≤ |uλ | ≤ 2k+1 . This
search is conducted pretty much as in the case of repeats, only that now when we fix some
factor y of uρ , we have to look for the occurrences of y | in the factor of length O(α|uρ |)
preceding it; the LCP-structures for ww| are useful for this, because, as explained above,
they allow us to efficiently search the mirror images of factors of w inside w. Thus, given a
word w and α ≥ 1, we can compute Gα| (w) in time O(αn).

REFERENCES

References
1 Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and
Kazuya Tsuruta. The Runs Theorem. CoRR, abs/1406.0263, 2014.
2 Gerth Stølting Brodal, Rune B. Lyngsø, Christian N. S. Pedersen, and Jens Stoye. Finding
maximal pairs with bounded gap. In Proc. 10th Annual Symposium on Combinatorial
Pattern Matching, volume 1645 of LNCS, pages 134–149. Springer, 1999.
3 Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Wojciech Rytter, and Tomasz
Walen. Efficient algorithms for two extensions of LPF table: The power of suffix arrays.
In Proc. SOFSEM 2010, volume 5901 of LNCS, pages 296–307, 2010.
4 Maxime Crochemore, Roman Kolpakov, and Gregory Kucherov. Optimal searching of
gapped repeats in a word. ArXiv e-prints 1309.4055, 2015.
5 Maxime Crochemore and German Tischler. Computing longest previous non-overlapping
factors. Inf. Process. Lett., 111(6):291–295, February 2011.
6 Marius Dumitran and Florin Manea. Longest gapped repeats and palindromes. In Proc.
MFCS 2015, volume 9234 of LNCS, pages 205–217. Springer, 2015.
7 Pawel Gawrychowski. Pattern matching in Lempel-Ziv compressed strings: Fast, simple,
and deterministic. In Proc. ESA, volume 6942 of LNCS, pages 421–432, 2011.
8 Pawel Gawrychowski and Florin Manea. Longest α-gapped repeat and palindrome. In
Proc. FCT 2015, volume 9210 of LNCS, pages 27–40. Springer, 2015.
9 Dan Gusfield. Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, New York, NY, USA, 1997.
10 Juha Kärkkäinen, Peter Sanders, and Stefan Burkhardt. Linear work suffix array
construction. J. ACM, 53:918–936, 2006.
11 Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. Efficient
data structures for the factor periodicity problem. In Proc. SPIRE, volume 7608 of LNCS,
pages 284–294, 2012.
12 Roman Kolpakov and Gregory Kucherov. Finding repeats with fixed gap. In Proc. SPIRE,
pages 162–168, 2000.
13 Roman Kolpakov and Gregory Kucherov. Searching for gapped palindromes. Theoretical
Computer Science, 410(51):5365 – 5373, 2009. Combinatorial Pattern Matching.
14 Roman Kolpakov, Mikhail Podolskiy, Mikhail Posypkin, and Nickolay Khrapov. Searching
of gapped repeats and subrepetitions in a word. In Proc. CPM, volume 8486 of LNCS,
pages 212–221, 2014.
15 Yuka Tanimura, Yuta Fujishige, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and
Masayuki Takeda. A faster algorithm for computing maximal α-gapped repeats in a
string. In Proc. SPIRE 2015, volume 9309 of LNCS, pages 124–136. Springer, 2015.
16 Peter van Emde Boas. Preserving order in a forest in less than logarithmic time. In Proc.
FOCS, pages 75–84, 1975.

13

Appendix
6

A short recent history of this problem

The problem of searching for gapped repeats and palindromes in words is not so new (see
[9, 2, 12]), and different solutions were proposed depending on the type of restrictions
imposed on the gap. In [13], Kolpakov and Kucherov introduced the notion of α-gapped
palindromes, and showed how to compute the set Gα| (w) of all maximal α-gapped palindromes
in O(α2 n + |Gα| (w)|) time for any input word w of length n over constant alphabets. In [14],
Kolpakov et al. introduced the notion of α-gapped repeats, and showed that the number of
maximal α-gapped repeats in a word w of length n is O(α2 n), and that this maximal set
Gα (w) can be computed in O(α2 n) time. They suggested two open problems concerning this:
closing the gap between the upper bound O(α2 n) and the lower bound Ω(αn) for the
number of maximal α-gapped repeats, and
developing a more efficient algorithm.
Their preliminary experiments suggested that the upper bound should be O(αn).
In February 2015, at the Stringmasters meeting in Warsaw, the third author of this paper
pointed that obtaining a bound on the number of α-gapped repeats seems to be an interesting
open problem, and also conjectured that this bound is O(αn). As a reaction, several connected
papers appeared: [8] shows how to compute the longest α-gapped repeat/palindrome in
O(αn) time, [6] shows how to compute a series of data structures that can give the longest
2-gapped repeat/palindrome that starts at each position (and the results generalize easily
to arbitrary α), [15] gives an O(αn + |Gα (w)|)-time solution to find all maximal α-gapped
repeats for an input word over constant alphabets.
Finally, in August 2015, the fourth author of this paper announced on the Stringmasters
web-page1 that the bound on the number of α-gapped repeats is indeed O(αn); together
with [15] this lead to an optimal algorithm for solving the problem of finding all α-gapped
repeats in the particular case of constant alphabets. This announcement was followed by the
paper [4] which basically confirmed the bound O(αn) and also gave an algorithm computing
efficiently all α-gapped maximal repeats for constant alphabets. Our paper concludes in
big measure this line of research: we give concrete bounds on the number of α-gapped
repeats and α-gapped palindromes, and, building on the approach from [8], we give optimal
algorithms for finding them in the usual case of integer alphabets.

7

Gapped repeats

The following figure might ease the understanding the proof of Lemma 7 regarding periodic
gapped repeats.
uλ
sλ
rλ

uρ
sρ
rρ

uλ
sλ
rλ

uρ
sρ
rρ

Figure 5 The equation b(uλ ) = b(rλ ) or b(uρ ) = b(rρ ) must hold in the setting of Lemma 7. By
the maximality property of runs, e(rλ ) = e(sλ ) and e(rρ ) = e(sρ ).

1

http://stringmasters.mimuw.edu.pl/open_problems.html

8

Gapped palindromes

I Lemma 17. Given a word w, and two real numbers α > 1 and 0 < β < 1. Then |βP |α (w)|
is at most 2(α + 1)E(w)/β.
Proof. Let σ ∈ βPα (w) (or σ ∈ βP |α (w)). The gapped palindrome σ consists of the triple
(uλ , v, uρ ) ∈ βPα (w). By definition, the left arm uλ has a periodic prefix sλ of length at
least β |uλ |. Let rλ denote the run that generates sλ , i.e., sλ ⊆ rλ and they both have the
common shortest period p. By the definition of gapped palindromes, there is a right copy sρ
of sλ contained in uρ with
sρ = w[b(uρ ) + (e(uλ ) − e(sλ )), b(uρ ) + (e(uλ ) − e(sλ )) + |sλ | − 1] ≡ sλ |
Let rρ be a run generating sρ (it is possible that rρ and rλ are identical). By definition, rρ
has the same period p as rλ . In the following, we will see that σ is uniquely determined by rλ
and the distance d := b(sρ ) − e(sλ ), if σ is a periodic gapped palindrome. We will fix rλ and
study how many maximal periodic gapped repeats (palindromes) can be generated by rλ .
uλ
sλ
rλ

uρ
sρ
rρ

uλ
sλ
rλ

uρ
sρ
rρ

Figure 6 The equation b(uλ ) = b(rλ ) or e(uρ ) = e(rρ ) must hold in the setting of Lemma 17. By
the maximality property of runs, e(rλ ) = e(sλ ) and b(rρ ) = b(sρ ).

Since σ is maximal, b(uλ ) = b(rλ ) or e(uρ ) = e(rρ ) must hold; otherwise we could extend
σ outwards. We analyze the case b(sλ ) = b(rλ ), the other is treated exactly in the same way
by symmetry. The gapped palindrome σ is identified by rλ and d. We fix rλ and count the
number of possible values for d. Given two different periodic α-gapped palindromes with the
distances d1 and d2 , the difference between d1 and d2 must be at least p, due to Lemma 2. It
follows from |uλ | ≤ |sλ | /β that d = |v| + 2(|uλ | − |sλ |) ≤ |v| + 2 |sλ | /β. Since σ is α-gapped,
|v| ≤ (α − 1) |uλ | ≤ (α − 1) |sλ | /β, and hence, 1 ≤ d ≤ |sλ | (α + 1)/β. Then the number
of possible values for the distance d is bounded by |sλ | (α + 1)/(βp) ≤ |rλ | (α + 1)/(βp) =
exp(rλ )(α + 1)/β. In total, the number of maximal α-gapped palindromes in this case is
bounded by (α + 1)E(w)/β for the case b(uλ ) = b(rλ ). Summing up we get the bound
2(α + 1)E(w)/β.
J
I Lemma 18. Given a word w, and two real numbers α > 1 and 6/7 ≤ β < 1. The points
|
mapped by two different maximal gapped palindromes in βP α (w) cannot 1−β
α -cover the same
point.
|

Proof. Let σ = uλ , v, uρ and σ = uλ , v, uρ be two different gapped palindromes in βP α (w).
Set u := |uλ | = |uρ |, u := |uλ | = |uρ |, g := |v| and g := |v|. We map the maximal gapped
palindromes σ and σ to the points (e(uλ ), g) and (e(uλ ), g), respectively. Assume, for the
sake of contradiction, that both points 1−β
α -cover the same point (x, y).
Let z := |e(uλ ) − e(uλ )| be the difference of the endings of both left arms, and sλ :=
w[[b(uλ ), e(uλ )] ∩ [b(uλ ), e(uλ )]] be the overlap of uλ and uλ . Let s = |sλ |, and let sρ (resp.
sρ ) be the reversed copy of sλ based on σ (resp. σ).
Sub-Claim: The overlap sλ is not empty, and sρ 6= sρ
Sub-Proof. Assume for this sub-proof that e(uλ ) < e(uλ ) (otherwise exchange σ with
σ, or yield the contradiction σ = σ). By combining the (1 − β)/α-cover property with the

fact that σ is α-gapped, we yield e(uλ ) − u ≤ e(uλ ) − g(1 − β)/α ≤ x ≤ e(uλ ) < e(uλ ).
So the subword w[e(uλ )] is contained in uλ . If sρ = sρ , then we get a contradiction to the
maximality of σ: By the above inequality, w[e(uλ ) + 1] is contained in uλ , too. Since σ is a
gapped palindrome, the character w[e(uλ ) + 1] occurs in uρ , exactly at w[b(uρ ) − 1].
J
Without loss of generality let g ≤ g. Then
g−

g(1 − β)
≤ y ≤ g ≤ g.
α

(6)

So the difference of both gaps is
0 ≤ δ := g − g ≤ g(1 − β)/α ≤ u(1 − β).

(7)

By case analysis, we show that sλ is periodic, which leads to the contradiction that σ or
σ are in βP |α (w).
1. Case e(uλ ) ≤ e(uλ ). Since e(uλ ) − g(1 − β)/α ≤ x ≤ e(uλ ) ≤ e(uλ ),
z = e(uλ ) − e(uλ ) ≤ g(1 − β)/α ≤ u(1 − β).

(8)

Since sλ is a prefix of uλ and a suffix of uλ , the reverse copy sρ is a suffix of uρ and a prefix of
uρ . The starting positions of both right copies sρ and sρ differ by b(sρ ) − b(sρ ) = 2z + δ > 0.
By Equations (7) and (8), we get 2z + δ ≤ 3g(1 − β)/α ≤ 3u(1 − β).
uλ

uρ

v

uλ
sλ

uρ

v
sρ

z

sρ

2z + δ
Figure 7 Sub-Case 1a

1a. Sub-Case b(uλ ) ≤ b(uλ ). By Equation (8), we get s = u − z ≥ uβ. It follows from
6/7 ≤ β < 1 that s/(2z + δ) ≥ uβ/3u(1 − β) = β/(3(1 − β)) ≥ 2, which means that sρ and
sρ overlap by at least half of their common length, and sλ is periodic. Since sλ is a prefix of
uλ of length s ≥ uβ, σ is in βP |α (w), a contradiction.
uλ
uλ
sλ

uρ

v

uρ

v
sρ

z
2z + δ

sρ

Figure 8 Sub-Case 1b

1b. Sub-Case b(uλ ) > b(uλ ). We conclude that sλ = uλ . By Equation (6),
u ≥ g/α ≥

g
1−β
(1 −
) ≥ gβ/α.
α
α

(9)

It follows from 6/7 ≤ β < 1 that s/(2z + δ) ≥ gαβ/(3αg(1 − β)) = β/(3(1 − β)) ≥ 2, which
means that sλ = uλ is periodic. Hence σ is in βP |α (w), a contradiction.
2. Case e(uλ ) > e(uλ ). Since e(uλ ) − g(1 − β)/α ≤ x ≤ e(uλ ) ≤ e(uλ ),
z = e(uλ ) − e(uλ ) ≤ g(1 − β)/α ≤ g(1 − β)/α ≤ u(1 − β).

(10)

The starting positions of both right copies differ by |b(sρ ) − b(sρ )| = |2z − δ|. Since 2z − δ ≤
max (δ, 2z), we get |2z − δ| ≤ 2g(1 − β)/α ≤ 2u(1 − β) by Equations (7) and (10).

uλ
uλ
sλ

uρ

v
uρ

v
z

sρ

2z − δ
sρ

Figure 9 Sub-Case 2a

uλ
uλ
sλ

uρ

v
uρ

v
z

sρ

2z − δ
sρ

Figure 10 Sub-Case 2b

2a. Sub-Case b(uλ ) ≤ b(uλ ). We conclude that sλ = uλ . It follows from 6/7 ≤ β < 1
that s/ |2z − δ| ≥ u/(2u(1 − β)) = 1/(2(1 − β)) ≥ 7/2 > 2, which means that sλ = uλ is
periodic. Hence σ is in βP |α (w), a contradiction.
2b. Sub-Case b(uλ ) > b(uλ ). By Equation (10), we get
√ z ≤ u(1 − β) and thus
s = u − z ≥ βu. It follows from Equations (7) and (9), and 2( 2 − 1) < 6/7 ≤ β < 1 that
s/ |2z − δ| ≥ βu/(2g(1 − β)/α) ≥ gβ 2 /(2g(1 − β)) = β 2 /(2(1 − β)) > 2, which means that sλ
is periodic. Since sλ is a prefix of uλ of length s ≥ uβ, σ is in βP |α (w), a contradiction. J
The next lemma follows immediately from Lemmas 6 and 18.
|

I Lemma 19. For α > 1, 6/7 ≤ β < 1 and a word w of length n, βP α (w) < 3αn/(1 − β).
I Theorem 20. For α > 1 and a word w of length n, |Gα| (w)| < 28αn + 7n.
|

Proof. By Lemmas 7 and 19, |Gα| (w)| = |βP |α (w)|+ βP α (w) < 2(α+1)E(w)/β+3αn/(1−β)
for every 6/7 ≤ β < 1. Applying Lemma 1, the term is upper bounded by 6(α + 1)n/β +
3αn/(1 − β). This number is minimal when β = 6/7, yielding the bound 28αn + 7n.
J

Auxiliary algorithmic results
Proof of Lemma 11.
Proof. Once we produce LCP data structures for w, we just have to compute the longest
common prefix of w[i, n] and w[i + p, n]. If this prefix is w[i + p, `], then w[i, `] is the longest
p-periodic factor starting on position i.
J
Proof of Lemma 12
Proof. We construct the dictionary of basic factors of a word of length n in O(n log n) time
and reorganise it such that for each basic factor we have an array with all its occurrences,
ordered by their starting positions. For each such array we construct data structures that
allow predecessor/successor search in O(log log n) time (see, e.g., [16]). When we have to
return the occurrences of y = w[i, i + 2k − 1] in z = w[j, j + c2k − 1], we search in the
basic factors-array corresponding to w[i, i + 2k − 1] the successor of j and, respectively, the
predecessor of j + c2k − 1 and then return a succinct representation of the occurrences of
w[i, i + 2k − 1] between these two values. This representation can be obtained in O(c) time.

z = w[j, j + 8 · 2j − 1]
r2
r3
y
y
y
y
y

r1
y
y
y

y

y
i

i + 2k

Figure 11 Occurrences of the basic factor y = w[i, i + 2k − 1] in z = w[j, j + 8 · 2k − 1]. The
overlapping occurrences are part of runs, and they can be returned as such. The representation of
the occurrences of y in z will return 4 elements: 3 runs and one separate occurrence.

We just have to detect those occurrences that form a run; this can be done with a constant
number of LCP queries. Indeed, for two consecutive occurrences, we compute the length of
their overlap, which gives us a period of w[i, i + 2k − 1]. Then we look in w to see how long the
run with this period can be extended to the right, which gives us the number of occurrences
of w[i, i + 2k − 1] in that run. As their starting positions form an arithmetic progression,
we can represent them compactly. So, we return the representation of the occurrences of
w[i, i + 2k − 1] from this run, and then move directly to the first occurrence of w[i, i + 2k − 1]
appearing after this run and still in the desired range; as there are at most O(c) runs and
separate occurrences of the given basic factor that are in z, the conclusion follows.
J

Proof of Lemma 13.
In [8] the following result was shown. Lemma 13 follows directly.
I Lemma 21. Given a word v, |v| = α log n, we can process v in time O(α log n) time such
that given any basic factor y = v[j · 2k + 1, (j + 1)2k ] with j, k ≥ 0 and j2k + 1 > (α − 1) log n,
we can construct in O(α) time O(α) bit-sets, each storing O(log n) bits, characterizing all
the occurrences of y in v.
The following lemma is useful for the proof. More precisely, one can also construct data
structures that allow us fast identification of the suffixes of a word that start with a given
basic factor.
I Lemma 22 ([7]). A word w of length n can be processed in O(n) time such that given any
basic factor w[i, i + 2k − 1] with k ≥ 0, we can retrieve in O(1) time the range of the suffix
array of w of suffixes starting with w[i, i + 2k − 1]. Equivalently, we can find the node of the
suffix tree of w closest to the root, such that the label of the path from the root to that node
has the prefix w[i, i + 2k − 1].
The proof of Lemma 21 follows.
Proof. We first show how the proof works for α = 1.
We first build the suffix tree for v in O(log n) time. We further process this suffix tree
such that we can find in constant time, for each factor v[j · 2k + 1, (j + 1)2k ], the node u of
the suffix tree which is closest to the root with the property that the label of the path from
the root to u starts with v[j · 2k + 1, (j + 1)2k ]. According to Lemma 22, this can be done in
linear time.

Now, we augment the suffix tree in such a manner that for each node we store an additional
bit-set, indicating the positions of v where the word labelling the path from the root to the
respective node occurs. Each of these bit-sets, of size O(log n) bits, can be stored in constant
space; indeed, each log n block of bits can be seen in fact as a number between 1 and n so
we only need to store a constant number of numbers smaller than n; in our model, each such
number fits in a memory word. Computing the bit-sets can be done in a bottom up manner
in linear time: for a node, we need to make the union of the bit-sets of its children, and this
can be done by doing a bitwise or operation between all the bit-sets corresponding to the
children. So, now, checking the bit-set associated to the lowest node of the suffix tree such
that the label of the path from the root to that node starts with v[j · 2k + 1, (j + 1)2k ] we
can immediately output a representation of this factor’s occurrences in v.
This concludes the proof for α = 1.
For α > 1, we just have to repeat the algorithm in the previous proof for the words
v[i log n + 1, (i + 2) log n]v[(α − 1) log n + 1, α log n], for 0 ≤ i ≤ α − 2, which allows us to
find all the occurrences of the basic factors of v[(α − 1) log n + 1, α log n] in v. The time is
clearly O(α).
J
I Remark. By this lemma, given a word v, |v| = α log n, and a basic factor y = v[j · 2k +
1, (j + 1)2k ], with j, k ≥ 0 and j2k + 1 > (α − 1) log n, we can produce O(α) bit-sets, each
containing exactly O(log n) bits, characterising all the occurrences of y in v. Let us also
assume that we have access to all values log x with x ≤ n (which can be ensured by a O(n)
preprocessing). Now, using the bit-sets encoding the occurrences of y in v and given a factor
z of v, |z| = c|y| for some c ≥ 1, we can obtain in O(c) time the occurrences of y in z: the
positions (at most c) where y occurs outside a run and/or at most c runs containing the
occurrences of y. Indeed, the main idea is to select by bitwise operations on the bit-sets
encoding the factors of v that overlap z the positions where y occurs (so the positions with an
1). For each two consecutive such occurrences of y we detect whether they are part of a run
in v (by LCP-queries on v) and then skip over all the occurrences of y from that run (and
the corresponding parts of the bit-sets) before looking again for the 1-bits in the bit-sets.
Proof. When given an additional subrange z of v, we have to select from the non-null bits of
the bit-sets corresponding to the factors v[j log n + 1, (j + 2) log n] of v those corresponding
to the range z. This can be easily done with bitwise operations in O(c) time. Indeed, when
looking at such a bit-set, we first select the most significant 1-bit (it occurs on the position
given by log m, where m is the integer value of the current bit-set), it gives an occurrence of
y. Then we turn this bit into 0, and select the next most-significant 1, which again gives an
occurrence of y. If these two occurrences are part of a run, we detect the ending position of
the run by a LCP query on v, and continue finding the y’s after that position. Otherwise,
we repeat the procedure (the second y detected able will be now detected as the first y). J
Missing cases from the proof of Lemma 14.
Assume uρ starts on the first position of rρ . If uρ ends on a position inside rρ , other
than its last position, then uλ should end on the last position of rλ (otherwise, both arms
could be extended to the right). This means that we know exactly the gap between the two
arms of the α-gapped repeat that we want to construct, as well as the fact that the arms
are p-periodic. We consider, again, the longest p-periodic suffix of rλ which is a prefix of rρ ,
and see whether the two occurrences of this factor determine a maximal α-gapped repeat. If
uρ ends on the last position of rρ then we know the exact arm of the α-gapped palindrome
we are looking for (that is, if it also fulfils the length conditions). We can proceed just like

p

uλ
y

u0

` + |y|

`+1

uρ
y

p

s

j2k + 1

s
(j + 1)2k

Figure 12 Fixing xm in the proof of Theorem 14, we try to spot gapped repeats whose arms
contain a certain basic factor. If we can extend this gapped repeat to a maximal gapped repeat, we
output it.

rλ s
uλ

rρ
uρ

(a)

rλ
uλ
(e)

s

rρ
uρ

rλ
uλ
uλ
uλ
p

rλ
uλ
zz

z

(c)

rλ s
uλ
(f)

rρ s
uρ

rρ
uρ

rλ
uλ

p

(b)

rρ
uρ

rρ
uρ

(d)

s

rλ
uλ

s

rρ
uρ

(g)

Figure 13 Catching gapped repeats with periodicity is done by case analysis in the proof of
Theorem 14. Each case is depicted in order (from left to right, top to bottom)

in the case analyzed before, when we knew that uλ = rλ , only that in this case we have to
determine the positions where uλ may start instead of those where uρ started. Finally, if uρ
ends on a position to the right of rρ , then uλ should also end after rλ and the suffix of uλ
occurring after rλ should be equal to the suffix of uρ occurring after rρ . We determine this
suffix by a longest common prefix query on xm , and then we obtain exactly the arms of the
repeat. We can check whether it is a valid maximal α-gapped repeat, and, if so, return it.
The last case is when uρ starts on a position to the left of rρ . Then uλ starts on a position
occurring before the first position of rλ , the prefix of uρ occurring before the beginning of rρ
equals the prefix of uλ occurring before rλ , and they can be determined in constant time.
Thus we know the starting points of both arms of the repeat, and we can determine them
exactly by a longest common prefix query. We just have to check whether the arms we
obtained form a valid maximal α-gapped repeat.

