and those not belonging to both former subsets.
They showed that the first two subsets contain at most \({\alpha 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 created by two different maximal \(\alpha \) -gapped repeats cannot \(\frac{1}{4\alpha }\) -cover the same point.
By this property, they bounded the size of the last subset by \({\alpha ^2 n}\) .
lemmaPoints immediately improves this bound of \({\alpha ^2 n}\)  to \({\alpha n}\) . Consequently, it shows that the number of maximal \(\alpha \) -gapped repeats of a word of length \(n\)  is \({\alpha n}\) .
Gapped repeats
We optimize the proof technique from [1]} and
improve the upper bound of the number of maximal \(\alpha \) -gapped repeats in a word of length \(n\)  from \({\alpha n}\)  to \(18 \alpha n\) .
Unlike [1]}, [3]}, we partition the maximal \(\alpha \) -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 secPointAnalysis.
We begin with a formal definition of both subsets and analyze the former subset.
Let \(0 < \beta < 1\) .
A gapped repeat (palindrome) \(\sigma = {u}_{{\lambda }},v,{u}_{{\rho }}\)  belongs to \(\beta \mathcal {P }_\alpha (w)\)  (\({\beta \mathcal {P }}^{{\intercal }}_\alpha (w)\) ) iff \({u}_{{\lambda }}\)  contains
a periodic prefix of length at least \(\beta {{u}_{{\lambda }}}\) .
We call \(\sigma \)  periodic.
Otherwise \(\sigma \in \overline{\beta \mathcal {P }}_\alpha (w)\)  (\(\sigma \in {\overline{\beta \mathcal {P }}}^{{\intercal }}_\alpha (w)\) ), where \(\overline{\beta \mathcal {P }}_\alpha (w):= \mathcal {G }_\alpha (w)\setminus \beta \mathcal {P }_\alpha (w)\)  and \({\overline{\beta \mathcal {P }}}^{{\intercal }}_\alpha (w):= {\mathcal {G }}^{{\intercal }}_\alpha (w)\setminus {\beta \mathcal {P }}^{{\intercal }}_\alpha (w)\) ;
we call \(\sigma \)  aperiodic.
Lemma  
Let \(w\)  be a word, \(\alpha > 1\)  and \(0 < \beta < 1\) 
two real numbers.
Then \({\beta \mathcal {P }_\alpha (w)}\)  is at most \(2 \alpha E(w) / \beta \) .

Let \(\sigma = ({u}_{{\lambda }},v,{u}_{{\rho }}) \in \beta \mathcal {P }_\alpha (w)\) .
By definition, the left arm \({u}_{{\lambda }}\)  has a periodic prefix \({s}_{{\lambda }}\)  of length at least \(\beta {{u}_{{\lambda }}}\) .
Let \({r}_{{\lambda }}\)  denote the run that generates \({s}_{{\lambda }}\) , i.e.,
\({s}_{{\lambda }}\subseteq {r}_{{\lambda }}\)  and they both have the common shortest period \(p\) .
By the definition of gapped repeats, there is a right copy \({s}_{{\rho }}\)  of \({s}_{{\lambda }}\)  contained in \({u}_{{\rho }}\)  with
\({s}_{{\rho }}=w[\mathsf {b}({s}_{{\lambda }})+{{u}_{{\lambda }}v},\mathsf {e}({s}_{{\lambda }})+{{u}_{{\lambda }}v}] \equiv {s}_{{\lambda }}.\)
Let \({r}_{{\rho }}\)  be a run generating \({s}_{{\rho }}\)  (it is possible that \({r}_{{\rho }}\)  and \({r}_{{\lambda }}\)  are identical).
By definition, \({r}_{{\rho }}\)  has the same period \(p\)  as \({r}_{{\lambda }}\) .
In the following, we will see that \(\sigma \)  is uniquely determined by \({r}_{{\lambda }}\)  and
the period \(q := {{u}_{{\lambda }}v}\) , if \(\sigma \)  is a periodic gapped repeat.
We will fix \({r}_{{\lambda }}\)  and pose the question how many maximal periodic gapped repeats can be generated by \({r}_{{\lambda }}\) .
Since \(\sigma \)  is maximal, \(\mathsf {b}({u}_{{\lambda }}) = \mathsf {b}({r}_{{\lambda }})\)  or \(\mathsf {b}({u}_{{\rho }}) = \mathsf {b}({r}_{{\rho }})\)  must hold;
otherwise we could extend \(\sigma \)  to the left.
We analyze the case \(\mathsf {b}({s}_{{\lambda }}) = \mathsf {b}({r}_{{\lambda }})\) , the other is treated exactly in the same way by symmetry.
The gapped repeat \(\sigma \)  is identified by \({r}_{{\lambda }}\)  and the period \(q\) .
We fix \({r}_{{\lambda }}\)  and count the number of possible values for the period \(q\) .
Given two different gapped repeats \(\sigma _1\)  and \(\sigma _2\)  with respective periods \(q_1\)  and \(q_2\)  such that the left arms of both
are generated by \({r}_{{\lambda }}\) , the difference \(\delta \)  between \(q_1\)  and \(q_2\)  must be at least \(p\) .
Since \({{u}_{{\lambda }}} \le {{s}_{{\lambda }}} / \beta \)  and \(\sigma \)  is \(\alpha \) -gapped,
\(1 \le q \le {{s}_{{\lambda }}} \alpha / \beta \le {{r}_{{\lambda }}} \alpha / \beta \) .
Then the number of possible periods \(q\)  is bounded by
\({{r}_{{\lambda }}} \alpha / (\beta p) = \exp ({r}_{{\lambda }}) \alpha / \beta \) .
Therefore the number of maximal \(\alpha \) -gapped repeats is bounded by \(\alpha E(w) / \beta \)  for the case \(\mathsf {b}({u}_{{\lambda }}) = \mathsf {b}({r}_{{\lambda }})\) .
Summing up we get the bound \(2 \alpha E(w) / \beta \) .
Remembering the results of secPointAnalysis, we map gapped repeats to their respective points.
By using the period as the \(y\) -coordinate, one can show lemmaNPCover.
Lemma  
Given a word \(w\) , and two real numbers \(\alpha > 1\)  and \(2/3 \le \beta < 1\) .
The points mapped by two different maximal gapped repeats in \(\overline{\beta \mathcal {P }}_\alpha (w)\)  cannot \(\frac{1-\beta }{\alpha }\) -cover the same point.

Let \(\sigma = {u}_{{\lambda }},v,{u}_{{\rho }}\)  and \(\overline{\sigma }= \overline{{u}_{{\lambda }}},\overline{v},\overline{{u}_{{\rho }}}\)  be two different maximal gapped repeats in \(\overline{\beta \mathcal {P }}_\alpha (w)\) .
Set \(u:= {{u}_{{\lambda }}} = {{u}_{{\rho }}}\) , \(\overline{u}:= {\overline{{u}_{{\lambda }}}} = {\overline{{u}_{{\rho }}}}\) , \(q := {{u}_{{\lambda }}v}\)  and \(\overline{q} := {\overline{{u}_{{\lambda }}}\overline{v}}\) .
We map the maximal gapped repeats \(\sigma \)  and \(\overline{\sigma }\)  to the points \((\mathsf {e}({u}_{{\lambda }}), q)\)  and \((\mathsf {e}(\overline{{u}_{{\lambda }}}),\overline{q})\) , respectively.
Assume, for the sake of contradiction, that both points \(\frac{1-\beta }{\alpha }\) -cover the same point \((x, y)\) .
Let \(z:= {\mathsf {e}({u}_{{\lambda }}) - \mathsf {e}(\overline{{u}_{{\lambda }}})}\)  be the difference of the endings of both left arms, and
\({s}_{{\lambda }}:= w[ [\mathsf {b}({u}_{{\lambda }}),\mathsf {e}({u}_{{\lambda }})]\cap [\mathsf {b}(\overline{{u}_{{\lambda }}}),\mathsf {e}(\overline{{u}_{{\lambda }}})] ]\) 
be the overlap of \({u}_{{\lambda }}\)  and \(\overline{{u}_{{\lambda }}}\) .
Let \(s:= {{s}_{{\lambda }}}\) , and
let \({s}_{{\rho }}\)  (resp. \(\overline{{s}_{{\rho }}}\) ) be the right copy of \({s}_{{\lambda }}\)  based on \(\sigma \)  (resp. \(\overline{\sigma }\) ).
Sub-Claim: The overlap \({s}_{{\lambda }}\)  is not empty, and \({s}_{{\rho }}\ne  \overline{{s}_{{\rho }}}\)
Sub-Proof.
Assume for this sub-proof that \(\mathsf {e}({u}_{{\lambda }}) < \mathsf {e}(\overline{{u}_{{\lambda }}})\)  (otherwise exchange \(\sigma \)  with \(\overline{\sigma }\) , or yield the contradiction \(\sigma = \overline{\sigma }\) ).
By combining the \((1-\beta )/\alpha \) -cover property with the fact that \(\overline{\sigma }\)  is \(\alpha \) -gapped, we yield
\(\mathsf {e}(\overline{{u}_{{\lambda }}}) - \overline{u}\le \mathsf {e}(\overline{{u}_{{\lambda }}}) - \overline{q}(1-\beta )/\alpha \le x \le \mathsf {e}({u}_{{\lambda }}) < \mathsf {e}(\overline{{u}_{{\lambda }}}).\) 
So the subword \(w[\mathsf {e}({u}_{{\lambda }})]\)  is contained in \(\overline{{u}_{{\lambda }}}\) .
If \({s}_{{\rho }}= \overline{{s}_{{\rho }}}\) , then we get a contradiction to the maximality of \(\sigma \) :
By the above inequality, \(w[\mathsf {e}({u}_{{\lambda }})+1]\)  is contained in \(\overline{{u}_{{\lambda }}}\) , too.
Since \(\overline{\sigma }\)  is a gapped repeat, the character \(w[\mathsf {e}({u}_{{\lambda }})+1]\)  occurs in \(\overline{{u}_{{\rho }}}\) , exactly at \(w[\mathsf {e}({u}_{{\rho }})+1]\) .
\(\Box \)
Without loss of generality let \(q \le \overline{q}\) . Then
\(&\overline{q} - \frac{\overline{q}(1-\beta )}{\alpha } \le y \le q \le \overline{q}.&\\&\text{So the difference of both periods is }0 \le \delta := \overline{q} - q \le \overline{q}(1-\beta )/\alpha \le \overline{u}(1-\beta ).&\\&\text{{equOrdGapRuleInv} also yields that }u\ge q/\alpha \ge \frac{\overline{q}}{\alpha } (1 - \frac{1-\beta }{\alpha }) \ge \overline{q}\beta /\alpha .&\) 

Since \({s}_{{\rho }}= [\mathsf {b}({s}_{{\lambda }})+q,\mathsf {e}({s}_{{\lambda }})+q]\) 
and \(\overline{{s}_{{\rho }}} = [\mathsf {b}({s}_{{\lambda }})+\overline{q},\mathsf {e}({s}_{{\lambda }})+\overline{q}]\) , we have
\(\mathsf {b}(\overline{{s}_{{\rho }}}) - \mathsf {b}({s}_{{\rho }}) = \delta \) .
By case analysis, we show that \({u}_{{\lambda }}\)  or \(\overline{{u}_{{\lambda }}}\)  has a periodic prefix,
which leads to the contradiction that \(\sigma \)  or \(\overline{\sigma }\)  are in \(\beta \mathcal {P }_\alpha (w)\) .
1. Case \(\mathsf {e}({u}_{{\lambda }}) \le \mathsf {e}(\overline{{u}_{{\lambda }}})\).
Since \(\mathsf {e}(\overline{{u}_{{\lambda }}}) - \overline{q}(1-\beta )/\alpha \le x \le \mathsf {e}({u}_{{\lambda }}) \le \mathsf {e}(\overline{{u}_{{\lambda }}})\) ,
\(z= \mathsf {e}(\overline{{u}_{{\lambda }}}) - \mathsf {e}({u}_{{\lambda }}) \le \overline{q}(1-\beta )/\alpha \le \overline{u}(1-\beta ).\) 
<FIGURE>1a. Sub-Case \(\mathsf {b}({u}_{{\lambda }}) \le \mathsf {b}(\overline{{u}_{{\lambda }}})\).
By equOrdGapRulePosFirstLeft, we get \(s= \overline{u}- z\ge \overline{u}\beta \) .
It follows from equOrdGapRule and \(2/3 \le \beta < 1\)  that
\(s/ \delta \ge \overline{u}\beta / \overline{u}(1-\beta ) = \beta / (1-\beta ) \ge 2\) ,
which means that \({s}_{{\rho }}\)  and \(\overline{{s}_{{\rho }}}\)  overlap at least half of their common length, so \({s}_{{\lambda }}\)  is periodic.
Since \({s}_{{\lambda }}\)  is a prefix of \(\overline{{u}_{{\lambda }}}\)  of length \(s\ge \overline{u}\beta \) , \(\overline{\sigma }\)  is in \(\beta \mathcal {P }_\alpha (w)\) , a contradiction.
<FIGURE>1b. Sub-Case \(\mathsf {b}({u}_{{\lambda }}) > \mathsf {b}(\overline{{u}_{{\lambda }}})\).
We conclude that \({s}_{{\lambda }}= {u}_{{\lambda }}\) .
It follows from equOrdGapRule,equOrdGapRuleTakeFirstArm and \(2/3 \le \beta < 1\)  that
\(s/ \delta \ge \overline{q} \alpha \beta / (\overline{q} \alpha (1-\beta )) = \beta / (1-\beta ) \ge 2\) ,
which means that \({s}_{{\lambda }}= {u}_{{\lambda }}\)  is periodic.
Hence \(\sigma \)  is in \(\beta \mathcal {P }_\alpha (w)\) , a contradiction.
2. Case \(\mathsf {e}({u}_{{\lambda }}) > \mathsf {e}(\overline{{u}_{{\lambda }}})\).
Since \(\mathsf {e}({u}_{{\lambda }}) - q(1-\beta )/\alpha \le x \le \mathsf {e}(\overline{{u}_{{\lambda }}}) \le \mathsf {e}({u}_{{\lambda }})\) ,
\(z= \mathsf {e}({u}_{{\lambda }}) - \mathsf {e}(\overline{{u}_{{\lambda }}}) \le q(1-\beta )/\alpha \le \overline{q}(1-\beta )/\alpha \le \overline{u}(1-\beta ).\) 
<FIGURE>2a. Sub-Case \(\mathsf {b}({u}_{{\lambda }}) \le \mathsf {b}(\overline{{u}_{{\lambda }}})\).
We conclude that \({s}_{{\lambda }}= \overline{{u}_{{\lambda }}}\) .
It follows from equOrdGapRule and \(2/3 \le \beta < 1\)  that
\(s/ \delta \ge \overline{u}/ (\overline{u}(1-\beta )) = 1 / (1-\beta ) \ge 3 > 2\) ,
which means that \({s}_{{\lambda }}= \overline{{u}_{{\lambda }}}\)  is periodic.
Hence \(\overline{\sigma }\)  is in \(\beta \mathcal {P }_\alpha (w)\) , a contradiction.
<FIGURE>2b. Sub-Case \(\mathsf {b}({u}_{{\lambda }}) > \mathsf {b}(\overline{{u}_{{\lambda }}})\).
By equOrdGapRulePosFirstRight, we get \(s= u- z\ge u\beta \) .
If \(\delta \le s/ 2\) , \({s}_{{\rho }}\)  and \(\overline{{s}_{{\rho }}}\)  overlap at least half of their common length,
which leads to the contradiction that \({u}_{{\lambda }}\)  has a periodic prefix \({s}_{{\lambda }}\)  of length at least \(u\beta \) .
Otherwise, let us assume that \(s/ 2 < \delta \) .
By equOrdGapRule,equOrdGapRuleTakeFirstArm we get
\(u/ \delta \ge \overline{q} \alpha \beta / (\overline{q} \alpha (1-\beta )) = \beta / (1-\beta ) \ge 2\) 
with \(2/3 \le \beta < 1\) .
Hence, \(\delta \)  is upper bounded by \(u/ 2\) ; so
\({u}_{{\rho }}\)  has a periodic prefix of length at least \(2 \delta \)  (since \(2 \delta > s\ge u\beta \) ), a contradiction.
The next lemmaNP follows immediately from lemmaPoints,lemmaNPCover.
Lemma  
For \(\alpha > 1\) , \(2/3 \le \beta < 1\)  and a word \(w\)  of length \(n\) , \({\overline{\beta \mathcal {P }}_\alpha (w)} < 3 \alpha n / (1 - \beta )\) .

Given a word \(w\)  of length \(n\) , and a real number \(\alpha > 1\) .
Then \({\mathcal {G }_\alpha (w)} < 18 \alpha n\) .


Combining the results of lemmaP,lemmaNP,
\({\mathcal {G }_\alpha (w)} = {\beta \mathcal {P }_\alpha (w)} + {\overline{\beta \mathcal {P }}_\alpha (w)} < 2 \alpha E(w) /\beta + 3 \alpha n / (1 - \beta )\) 
for \(2/3 \le \beta < 1\) .
Applying lemmaExponent, the term is upper bounded by \(6 \alpha n / \beta + 3 \alpha n / (1 - \beta )\) .
The number is minimal for \(\beta = 2/3\) , yielding the bound \(18 \alpha n\) .
We can bound the number of maximal \(\alpha \) -gapped palindromes by similar proofs to \(28 \alpha n + 7 n\) .
This bound solves an open problem in [4]}, where Kolpakov and Kucherov
conjectured that the number of \(\alpha \) -gapped palindromes with \(\alpha \ge 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 \(\sigma \)  be a maximal \(\alpha \) -gapped repeat (or \(\alpha \) -gapped palindrome).
If the gapped repeat (palindrome) has a periodic prefix \({s}_{{\lambda }}\)  generated by some run, the right arm has a periodic prefix (suffix) \({s}_{{\rho }}\) 
generated by a run of the same period.
Since \(\sigma \)  is maximal, both runs have to obey constraints that are similar in both cases, considering whether \(\sigma \)  is a gapped repeat or a gapped palindrome.
So it is easy to change the proof of lemmaP in order to work with palindromes.
Like with aperiodic gapped repeats,
we can apply the point analysis to the aperiodic \(\alpha \) -gapped palindromes, too.
As main idea, we map a gapped palindrome \({u}_{{\lambda }},v,{u}_{{\rho }}\)  injectively to the pair of integers \((\mathsf {e}({u}_{{\lambda }}), {v})\) ,
exchanging the period with the size of the gap. See appendix for proofs.

Algorithms
The computational model we use to design and analyze our algorithms is the standard unit-cost 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 \(\lbrace 1,\ldots ,n\rbrace \) , so each letter fits in a single memory-word. This is a common assumption in stringology (see, e.g., the discussion in [5]}).
For a word \(w\) , \(|w|=n\) , we build in \({\mathcal {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 \({\mathit {LCP}}_w(i,j)\)  (the subscript \(w\)  is omitted when there is no danger of confusion). Such structures are called \({\mathit {LCP}}\)  data structures in the following (see, e.g., [5]}, [7]}). We begin with a simple lemma.

Given a word \(w\) , \(|w|=n\) , we can process it in \({\mathcal {O}}(n)\)  time such that, for each \(i,p\le n\) , we can return in \({\mathcal {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 \(\ell |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 \({\mathcal {O}}(\ell )\)  such occurrences (see, e.g., [8]}).
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 \({\mathcal {O}}(\ell )\)  runs containing occurrences of \(v\)  in \(z\) , or, equivalently, \({\mathcal {O}}(\ell )\)  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 \(2^k\) , for \(k\ge 1\) ) of the input word are important. For some integer \(c\ge 2\) , the occurrences of the basic factor \(w[i,i+2^k-1]\)  in a subword of length \(c2^k\)  can be represented in a compact manner:
\({\mathcal {O}}(c)\)  positions of the single occurrences of \(w[i,i+2^k-1]\)  and \({\mathcal {O}}(c)\)  first occurrences of \(w[i,i+2^k-1]\)  in runs, together with the period of \(w[i,i+2^k-1]\) .
We recall the next lemma (see [9]}, [8]}, appendix).

Given a word \(w\)  of length \(n\)  and an integer \(c\ge 2\) , we can process \(w\)  in time \({\mathcal {O}}(n\log n)\)  such that given any basic factor \(y=w[i,i+2^k-1]\)  and any subword of \(w\)  \((z,[j,j+c 2^k -1])\) , with \(k\ge 0\) , we can compute in \({\mathcal {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 apply these results directly in the main proofs of this section.
Given a word \(v\)  and some integer \(\beta \ge 16\)  with \(|v|=\beta \log n\) , as well as a basic factor \(y=v[i2^k+1,(i+1)2^{k}]\) , with \(i,k\ge 0\)  and \(i2^k+1> (\beta -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 \({\mathcal {O}}(\beta )\)  bit-sets, each containing \({\mathcal {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 [11]} (see also [9]} and the appendix).

Given a word \(v\)  and an integer \(\beta > 16\) , with \(|v|=\beta \log n\) , we can process \(v\)  in time \({\mathcal {O}}(\beta \log n)\)  time such that given any basic factor \(y=v[i2^k+1,(i+1)2^{k}]\)  with \(i,k\ge 0\)  and \(i2^k+1> (\beta -16)\log n\) , we can find in \({\mathcal {O}}(\beta )\)  time the \({\mathcal {O}}(\beta )\)  bit-sets, each storing \({\mathcal {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\ge 1\) , we can obtain in \({\mathcal {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 \(\alpha \) -gapped repeats of a word.
We first show how to find maximal repeats with short arms.

Given a word \(w\)  and \(\alpha \ge 1\) , we can find all the maximal \(\alpha \) -gapped repeats \(u_\lambda , u^{\prime }, u_\rho \)  occurring in \(w\) , with \(|u_\rho |\le 16 \log n\) , in time \({\mathcal {O}}(\alpha n)\) .


If a maximal \(\alpha \) -gapped repeat \(u_\lambda , u^{\prime }, u_\rho \)  (where we denote by \(u\)  the underlying factor of both arms), has \(|u|\le 16 \log n\) , we get that \(u_\rho \)  must be completely contained in a subword \((w^{\prime },[m\log n+1 , (m+17)\log n])\) , for some \(m\)  with \(\frac{n}{\log n}-17 \ge m\ge 0\) . By fixing the interval where \(u_\rho \)  may occur (that is, fix \(m\) ), we also fix the place where \(u_\lambda \)  may occur. Indeed, the entire subword \(u_\lambda , u^{\prime }, u_\rho \)  is completely contained in the factor \(x_m=(w^{\prime \prime },[(m - 16 \alpha )\log n +1 , (m+17)\log n])\)  (or, in a factor \(x_m=(w^{\prime \prime },[1, (m+17)\log n])\)  if \((m - 16 \alpha )\log n +1<1\) ).
Hence, we look for maximal \(\alpha \) -gapped repeats \(u_\lambda , u^{\prime },u_\rho \)  completely contained in \(x_m\)  with \(u_\rho \)  completely contained in the suffix of length \(16 \log n\)  of \(x_m\) ; then we repeat this process for all \(m\) .
To begin with, we process \(x_m\)  as in Lemma , and construct \({\mathit {LCP}}\) -structures for it.
Now, once we fixed the subword \(x_m\)  of \(w\)  where we search the maximal \(\alpha \) -gapped repeats, we try to fix also their length. That is, we find all maximal \(\alpha \) -gapped repeats \(u_\lambda , u^{\prime }, u_\rho \)  with \(2^{k+1}\le |u|\le 2^{k+2}\)  completely contained in \(x_m\)  with \(u_\rho \)  completely contained in the suffix of length \(16 \log n\)  of \(x_m\) ; we execute this process for all \(0\le k\le \log (16 \log n)\) . Note that all the maximal \(\alpha \) -gapped repeats with arms shorter than 2 (occurring anywhere in the word \(w\) ) can be trivially found in \({\mathcal {O}}(\alpha n)\)  time.
Since we can find occurrences of basic factors in \(x_m\)  efficiently, we try to build a maximal gapped repeat by extending
gapped repeats whose arms contain a basic factor (see figExtendXm in the appendix).
To this end, we analyze some subwords of \(x_m\) :
If \(2^{k+1}\le |u|\le 2^{k+2}\)  then \(u_\rho \)  contains at least one subword \((y,[j2^k+1,(j+1)2^k])\)  starting within its first \(2^k\)  positions.
A copy of the factor \(y\)  occurs also within the first \(2^k\)  positions of \(u_\lambda \)  (with the same offset with respect to the starting position of \(u_\lambda \)  as the offset of the occurrence of \(y\)  with respect to the starting position of \(u_\rho \) ).
So, finding the respective copy of \(y\)  from \(u_\lambda \)  helps us discover the place where \(u_\lambda \)  actually occurs.
Indeed, assume that we identified the copy of \(y\)  from \(u_\lambda \) , and assume that this copy is \((y,[\ell +1,\ell +|y|])\) ; we try to build \(u_\lambda \)  and \(u_\rho \)  around these two occurrences of \(y\) , respectively.
Hence, in order to identify \(u_\lambda \)  and \(u_\rho \)  we compute the longest factor \(p\)  of \(x_m\)  that ends both on \(j2^k\)  and on \(\ell \)  and the longest factor \(s\)  that starts both on \((j+1)2^k+1\)  and on \(\ell +|y|+1\) .
Now, if \(\ell +|y|+|s|\le j2^k-|p|\)  then \(u_\lambda \)  is obtained by concatenating \(p\)  and \(s\)  around \(x_m[\ell +1,\ell +|y|]\)  while \(u_\rho \)  is obtained by concatenating \(p\)  and \(s\)  to the left and, respectively, right of \(x_m[j2^k+1,(j+1)2^k]\) ; 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 \(2^{k+1}\)  and \(2^{k+2}\) , and its right arm contains position \(j2^k+1\)  of \(x_m\)  within its first \(2^k\)  positions.
Now we explain how to determine efficiently the copy of \(y\)  around which we try to build \(u_\lambda \) . As \(|u|<2^{k+2}\)  and \(|y|=2^k\)  we get that the copy of \(y\)  that corresponds to \(u_\lambda \)  should be completely contained in the subword of \(x_m\)  of length \(\alpha 2^{k+2}\)  ending on position \(j2^k\) . As said above, we already processed \(x_m\)  to construct the data structures from Lemma . Therefore, we can obtain in \({\mathcal {O}}(\alpha )\)  time a representation of all the occurrences of \(y\)  inside the factor of length \(\alpha 2^{k+2}\)  ending on position \(j2^k\) . These occurrences can be single occurrences and occurrences within runs.
There are \({\mathcal {O}}(\alpha )\)  single occurrences, and we can process each of them individually, as explained, to find the maximal \(\alpha \) -gapped repeat they determine together with the occurrence of \(y\)  from \(u_\rho \) .
However, it is not efficient to do the same for the occurrences of \(y\)  within runs. For these (which are also \({\mathcal {O}}(\alpha )\)  many) we proceed as follows.
Assume we have a run of occurrences of \(y\)  inside the factor of \(x_m\)  of length \(\alpha 2^{k+2}\)  ending on position \(j2^k\) . Let \(\ell \)  be the starting position of the first occurrence of \(y\)  in this run and let \(p\)  be the period of \(y\) . Now, using Lemma  we can determine the maximal \(p\) -periodic subword \(r_\lambda \)  of \(x_m\)  containing this run of \(y\) -occurrences. Similarly, we can determine the maximal \(p\) -periodic subword \(r_\rho \)  that contains the occurrence of \(y\)  from \(u_\rho \)  (i.e., \(x_m[j2^k+1,(j+1)2^k]\) ). To determine efficiently the \(\alpha \) -gapped repeats that contain \(x_m[j2^k+1,(j+1)2^k]\)  in the right arm and a corresponding occurrence of \(y\)  from \(r_\lambda \)  in the left arm we analyze several cases (see figPeriodicExtension in the appendix).
Assume \(u_\rho \)  starts on a position of \(r_\rho \) , other than its first one.
Then \(u_\lambda \)  should also start on the first position of \(r_\lambda \)  (or we could extend both arms to the left, a contradiction to the maximality of the repeat).
If \(u_\rho \)  ends on a position to the right of \(r_\rho \) , then \(u_\lambda \)  also ends on a position to the right of \(r_\lambda \) , and, moreover, the suffix of \(u_\lambda \)  occurring after the end of \(r_\lambda \)  and the suffix of \(u_\rho \)  occurring after the end of \(r_\rho \)  are equal, and can be computed by a longest common prefix query on \(x_m\) .
This means that \(u_\lambda \)  can be determined exactly (we know where it starts and where it ends) so \(u_\rho \)  can also be determined exactly (we know where it ends), and we can check if the obtained repeat is indeed a maximal \(\alpha \) -gapped repeat,
and the arms fulfill the required length conditions (i.e., length between \(2^{k+1}\)  and \(2^{k+2}\) , the right arm contains position \(j2^k+1\)  of \(x_m\)  within its first \(2^k\)  positions).
If \(u_\rho \)  ends exactly on the same position as \(r_\rho \)  then \(u_\rho \)  is periodic of period \(p\) ; we just have to compute the longest \(p\) -periodic factor that ends on the same position as \(r_\rho \)  and starts at the same position as \(r_\lambda \) , and this can also be determined in constant time just by taking the longest \(p\) -periodic prefix of \(r_\lambda \)  which is also a suffix of \(r_\rho \) .
So, again, we can determine exactly \(u_\lambda \)  and \(u_\rho \) , and we can check if they form a maximal \(\alpha \) -gapped repeat with the arms fulfilling the length restrictions.
The final, and more complicated case, is when \(u_\rho \)  ends on a position of \(r_\rho \) , other than its last position.
In that case, we get that \(u_\lambda =r_\lambda \)  (or, otherwise, we could extend both arms to the right).
Essentially, this means that we know exactly where \(u_\lambda \)  is located and its length (and we continue only if this length is between \(2^{k+1}\)  and \(2^{k+2}\) ); so \(u_\lambda \)  denotes a factor \(z^h z^{\prime }\)  for some \(z\)  of length \(p\) .
Now, looking at the run \(r_\rho \) , we can get easily the position of the first occurrence of \(z\)  in that run, and the position of its last occurrence.
If the first occurrence is \(\ell ^{\prime }\) , then the occurrences of \(z\)  have their starting positions \(\ell ^{\prime }\) , \(\ell ^{\prime }+p, \ldots , \ell ^{\prime }+tp \)  for some \(t\) .
As we know the length of \(u_\lambda \)  and the fact that \(u_\lambda , u^{\prime }, u_\rho \)  is \(\alpha \) -gapped, we can determine in constant time the values \(0\le i\le t\)  such that \(u_\rho \)  may start on position \(\ell ^{\prime }+ip\) , the repeat we obtain is \(\alpha \) -gapped, and \(u_\rho \)  contains position \(j2^k+1\)  of \(x_m\)  within its first \(2^k\)  positions.
If \(u_\rho \)  is a prefix of \(r_\rho \)  we also have to check that we cannot extend simultaneously \(u_\rho \)  and \(u_\lambda \)  to the left; if \(u_\rho \)  is a suffix of \(r_\lambda \)  we have to check that we cannot extend simultaneously \(u_\rho \)  and \(u_\lambda \)  to the right.
Then we can return the maximal \(\alpha \) -gapped repeats we constructed.
The cases when \(u_\rho \)  starts on the first position of \(r_\rho \)  or when it starts on a position to the left of \(r_\rho \)  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 \(x_m\)  for each \(m\)  separately.
However, when moving from \(x_m\)  to \(x_{m+1}\)  we must also check that the right arm of each repeat we find is not completely contained in \(x_m\)  (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 \(x_m\)  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 \({\mathcal {O}}(\alpha + N_{j,m,k})\)  time, where \(N_{j,m,k}\)  is the number of maximal \(\alpha \) -gapped repeats determined for the fixed \(m,j,k\) . So, the time complexity of the algorithm is:
\({\mathcal {O}}(n+\sum _{0\le m\le n/\log n}(16\alpha \log n+ \sum _{0\le k\le \log (16 \log n)} (\sum _{j\le 16 \log n/ 2^k} (\alpha + N_{j,m,k})))) \subseteq {\mathcal {O}}(\alpha n)\) ,
as the total number of maximal \(\alpha \) -gapped repeats is \({\mathcal {O}}(\alpha n)\)  and we need \({\mathcal {O}}(|x_m|)\)  preprocessing time for each \(x_m\)  and \({\mathcal {O}}(n)\)  preprocessing time for \(w\) .
Next, we find all maximal \(\alpha \) -gapped repeats with longer arms.

Given a word \(w\)  and \(\alpha \ge 1\) , we can find all the maximal \(\alpha \) -gapped repeats \(u_\lambda , u^{\prime }, u_\rho \)  occurring in \(w\) , with \(|u_\rho |> 16 \log n\) , in time \({\mathcal {O}}(\alpha n)\) .


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 \(\alpha \) -gapped repeat, we try to fix the place and length of the right arm \(u_\rho \)  of the respective repeat, which restricts the place where the left arm \(u_\lambda \)  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 , as we have to deal with repeats with arms longer than \(16 \log n\) .
Instead, we will use the structures constructed in Lemma .
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 \(w^{\prime }\) , of length \(\frac{n}{\log 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 \({\mathit {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.
We can now construct in \({\mathcal {O}}(n)\)  time the suffix arrays and \({\mathit {LCP}}\) -data structures for both \(w\)  and \(w^{\prime }\) , as well as the data structures of Lemma  for the word \(w^{\prime }\) .
Now, we guess the length of the arms of the repeat.
We try to find the maximal \(\alpha \) -gapped repeats \(u_\lambda , u^{\prime }, u_\rho \)  of \(w\)  with \(2^{k+1} \log n \le |u_\lambda | \le 2^{k+2}\log n\) , \(k\le \log \frac{n}{\log n}-2\) .
We fix \(k\)  and split again the word \(w\) , this time in factors of length \(2^k \log n\) , called \(k\) -blocks.
Assume that each split is exact (padding the word with some new symbols ensures this).
Now, if a maximal \(\alpha \) -gapped repeat \(u_\lambda , u^{\prime }, u_\rho \)  with \(2^{k+1} \log n \le |u_\lambda | \le 2^{k+2}\log n\)  exists, then it contains an occurrence of a \(k\) -block within its first \(2^k\log n\)  positions.
So, let \(z\)  be a \(k\) -block and assume that it is the first \(k\) -block occurring in \(u_\rho \)  (in this way fixing a range where \(u_\rho \)  may occur).
Obviously, if \(u_\rho \)  contains \(z\) , then \(u_\lambda \)  also contains an occurrence of \(z\) ; however, this occurrence is not necessarily starting on a position \(j\log n + 1\)  for some \(j\ge 0\)  (so, it is not necessarily a sequence of blocks).
But, at least one of the factors of length \(2^{k-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_\lambda \) .
So, let us fix now a factor \(y\)  of length \(2^{k-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_\rho \)  is not necessarily a sequence of blocks (so it cannot be mapped directly to a factor of \(w^{\prime }\) ). But, we look for an occurrence of \(y\)  starting on one of the \( \alpha 2^{k+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_\lambda \) .
By binary searching the suffix array of \(w^{\prime }\)  (using \({\mathit {LCP}}\) -queries on \(w\)  to compare the factors of \(\log n\)  symbols of \(y\)  and the blocks of \(w^{\prime }\) , at each step of the search) we try to detect a factor of \(w^{\prime }\)  that encodes a word equal to \(y\) .
Assume that we can find such a sequence \(y^{\prime }\)  of \(2^{k-1}\)  blocks of \(w^{\prime }\)  (otherwise, \(y\)  cannot correspond to a sequence of blocks from \(u_\lambda \) , so we should try other factors of \(z\)  instead).
Using Lemma  for \(w^{\prime }\) , we get in \({\mathcal {O}}(\log \log |w^{\prime }|+\alpha )\)  time a representation of the occurrences of \(y^{\prime }\)  in the range of \(\alpha 2^{k+2}\)  blocks of \(w^{\prime }\)  occurring before the blocks of \(z\) ; this range corresponds to an interval of \(w\)  with a length of \(\alpha 2^{k+2} \log n\) .
Further, we process these occurrences of \(y^{\prime }\)  just like in the previous lemma.
Namely, the occurrences of \(y^{\prime }\)  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_\lambda \) ; this arm, together with the corresponding arm \(u_\rho \)  can be constructed just like before.
In the case of single occurrences (which are at most \({\mathcal {O}}(\alpha )\) , again), we try to extend both the respective occurrence and the occurrence of \(y\)  from \(u_\rho \)  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 \(\alpha \) -gapped repeat.
Note that we must check also that the length of the arm of the repeat is between \(2^{k+1}\)  and \(2^{k+2}\) , and that \(z\)  is the first \(k\) -block of the right arm.
As before, complications occur when the occurrences of \(y^{\prime }\)  are within runs.
In this case, the run of occurrences of \(y^{\prime }\)  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_\rho \)  should always correspond to a block sequence from \(u_\lambda \) , so definitely to one of the factors encoded in the run of occurrences of \(y^{\prime }\) .
Therefore, by determining the maximal factor that contains \(y\)  and has the same period as the run of occurrences of \(y^{\prime }\)  (with the period measured in \(w\) ), we can perform a very similar analysis to the corresponding one from the case when we searched maximal \(\alpha \) -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 \(y_1\)  and \(y_2\)  (of length \(2^{k-1}\) ) occurring in the first \(\log n\)  symbols of \(z\)  we cannot get occurrences of the corresponding factors \(y^{\prime }_1\)  and \(y^{\prime }_2\)  that define the same repeat; in that case, the distance between \(y^{\prime }_1\)  and \(y^{\prime }_2\)  should be at least one block, so the distance between \(y_1\)  and \(y_2\)  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 \(z_1\)  such that this factor determines an \(\alpha \) -gapped maximal repeat, then the same maximal repeat cannot be determined by a factor of another \(k\) -block, since \(z_1\)  is the first \(k\) -block of \(u_\rho \) .
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 \(w^{\prime }\)  and of all the needed data structures) takes \({\mathcal {O}}(n)\)  time.
Further, we can choose \(k\)  (and implicitly an interval for the length of the arms of the repeats) such that \(k\le \log \frac{n}{\log n}-2\) .
After choosing \(k\) , we can choose a \(k\) -block \(z\)  in \(\frac{n}{2^k \log n}\)  ways.
Further, we analyze each factor \(y\)  of length \(2^{k-1}\)  starting within the first \(\log n\)  positions of the chosen \(k\) -block \(z\) .
For each such factor \(y\)  we find in \({\mathcal {O}}(\log \frac{n}{\log n} + \log \log n+ \alpha )\)  time the representation of the occurrences of the block encoding the occurrence of \(y\)  from \(u_\lambda \) .
From each of the \({\mathcal {O}}(\alpha )\)  single occurrences we check whether it is possible to construct a maximal \(\alpha \) -gapped repeat in \({\mathcal {O}}(1)\)  time.
We also have \({\mathcal {O}}(\alpha )\)  occurrences of the block encoding \(y\)  in runs, and each of them is processed in \({\mathcal {O}}(N_{z,y})\)  time, where \(N_{z,y}\)  is the number of maximal \(\alpha \) -gapped repeats we find for some \(z\)  and \(y\) .
Overall, this adds up to a total time of \({\mathcal {O}}(n \log n + \alpha n)\) , as the total number of maximal \(\alpha \) -gapped repeats in \(w\)  is upper bounded by \({\mathcal {O}}(\alpha n)\) .
If \(\alpha \ge \log n\) , the statement of the lemma follows.
If \(\alpha < \log n\)  we proceed as follows.
Initially, we run the algorithm only for \(k> \log \log n\)  and find the maximal \(\alpha \) -gapped repeats \(u_\lambda u^{\prime } u_\rho \)  with \(2^{\log \log n} \log n \le |u_\lambda |\) , in \({\mathcal {O}}(\alpha n)\)  time.
Further, we search maximal \(\alpha \) -gapped repeats with shorter arms.
Now, \(|u_\lambda |\)  is upper bounded by \(2^{\log \log n +1}\log n=2 (\log n)^2\) , so \(|u_\lambda u^{\prime }u_\rho |\le \ell _0\) , for \(\ell _0=\alpha \cdot 2 (\log n)^2+2 (\log n)^2=2(\alpha +1)(\log n)^2\) .
Such an \(\alpha \) -gapped repeat \(u_\lambda u^{\prime }u_\rho \)  is, thus, contained in (at least) one factor of length \( 2\ell _0\)  of \(w\) , starting on a position of the form \(1+m\ell _0\)  for \(m\ge 0\) .
So, we take the factors \(w[1+m\ell _0,(m+2)\ell _0]\)  of \(w\) , for \(m\ge 0\) , and apply for each such factor, separately, the same strategy as above to detect the maximal \(\alpha \) -gapped repeats contained completely in each of them.
The total time needed to do that is \({\mathcal {O}}\left(\alpha \ell _0 \frac{n}{\ell _0} + N_{\ell _0}\right)={\mathcal {O}}(\alpha n)\) , where \(N_{\ell _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 \(\alpha \) -gapped repeats \(u_\lambda u^{\prime }u_\rho \)  with \(2^{\log \log (2\ell _0)} \log (2\ell _0) \le |u| \) .
This means we find all the maximal \(\alpha \) -gapped repeats with \(|u|\ge 2^{\log \log (2\ell _0) +1} \log (2\ell _0)\) .
Since \(2^{\log \log (2\ell _0) +1} \log (2\ell _0) \le 16\log n\)  (for \(n\)  large enough, as \(\alpha \le \log n\) ), we can apply Lemma  for gapped repeats with an arm-length smaller than
\(2^{\log \log (2\ell _0) +1} \log (2\ell _0)\) .
Putting together the results of Lemmas  and  we get the following theorem.

Given a word \(w\)  and \(\alpha \ge 1\) , we can compute \(\mathcal {G }_\alpha (w)\)  in time \({\mathcal {O}}(\alpha n)\) .
By a completely similar approach we can compute \({\mathcal {G }}^{{\intercal }}_\alpha (w)\) , generalizing the algorithm of [4]}.
To this end, we construct \({\mathit {LCP}}\) -structures for \(w{w}^{{\intercal }}\)  (allowing us to test efficiently whether a factor \({w[i,j]}^{{\intercal }}\)  occurs at some position in \(w\) ).
When we search the \(\alpha \) -gapped palindromes \(u_\lambda ,v,u_\rho \)  (with \({u}_{{\rho }}\equiv {{u}_{{\lambda }}}^{{\intercal }}\) ), we split again \(w\)  in blocks and \(k\) -blocks, for each \(k\le \log |w|\) , to check whether there exists such an \(u_\lambda ,v,u_\rho \)  with \(2^{k}\le |u_\lambda |\le 2^{k+1}\) .
This search is conducted pretty much as in the case of repeats, only that now when we fix some factor \(y\)  of \(u_\rho \) , we have to look for the occurrences of \({y}^{{\intercal }}\)  in the factor of length \({\mathcal {O}}(\alpha |u_\rho |)\)  preceding it; the \({\mathit {LCP}}\) -structures for \(w{w}^{{\intercal }}\)  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 \(\alpha \ge 1\) , we can compute \({\mathcal {G }}^{{\intercal }}_\alpha (w)\)  in time \({\mathcal {O}}(\alpha n)\) .


Appendix

A short recent history of this problem
The problem of searching for gapped repeats and palindromes in words is not so new (see [7]}, [15]}, [16]}), and different solutions were proposed depending on the type of restrictions imposed on the gap.
In [4]}, Kolpakov and Kucherov introduced the notion of \(\alpha \) -gapped palindromes, and showed how to compute
the set \({\mathcal {G }}^{{\intercal }}_\alpha (w)\)  of all maximal \(\alpha \) -gapped palindromes in \({\mathcal {O}}(\alpha ^2 n + |{\mathcal {G }}^{{\intercal }}_\alpha (w)|)\)  time for any input word \(w\)  of length \(n\)  over constant alphabets.
In [1]}, Kolpakov et al. introduced the notion of \(\alpha \) -gapped repeats, and showed that the number of maximal \(\alpha \) -gapped repeats in a word \(w\)  of length \(n\)  is \({\mathcal {O}}(\alpha ^2 n)\) , and that this maximal set \(\mathcal {G }_\alpha (w)\)  can be computed in \({\mathcal {O}}(\alpha ^2 n)\)  time.
They suggested two open problems concerning this:

closing the gap between the upper bound \({\mathcal {O}}(\alpha ^2n)\)  and the lower bound \(\Omega (\alpha n)\) 
for the number of maximal \(\alpha \) -gapped repeats, and

developing a more efficient algorithm.

Their preliminary experiments suggested that the upper bound should be \({\mathcal {O}}(\alpha 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 \(\alpha \) -gapped repeats seems to be an interesting open problem, and also conjectured that this bound is \({\mathcal {O}}(\alpha n)\) .
As a reaction, several connected papers appeared: [9]} shows how to compute the longest \(\alpha \) -gapped repeat/palindrome in \({\mathcal {O}}(\alpha n)\)  time, [20]} 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 \(\alpha \) ), [21]} gives an \({\mathcal {O}}(\alpha n +|\mathcal {G }_\alpha (w)|)\) -time solution to find all maximal \(\alpha \) -gapped repeats for an input word over constant alphabets.
Finally, in August 2015, the fourth author of this paper announced on the Stringmasters web-pagehttp://stringmasters.mimuw.edu.pl/open_problems.html that the bound on the number of \(\alpha \) -gapped repeats is indeed \({\mathcal {O}}(\alpha n)\) ; together with [21]} this lead to an optimal algorithm for solving the problem of finding all \(\alpha \) -gapped repeats in the particular case of constant alphabets.
This announcement was followed by the paper [3]} which basically confirmed the bound \({\mathcal {O}}(\alpha n)\)  and also gave an algorithm computing efficiently all \(\alpha \) -gapped maximal repeats for constant alphabets.
Our paper concludes in big measure this line of research: we give concrete bounds on the number of \(\alpha \) -gapped repeats and \(\alpha \) -gapped palindromes, and, building on the approach from [9]}, we give optimal algorithms for finding them in the usual case of integer alphabets.

Gapped repeats
The following figure might ease the understanding the proof of lemmaP regarding periodic gapped repeats.
<FIGURE>
Gapped palindromes
Lemma  
Given a word \(w\) , and two real numbers \(\alpha > 1\)  and \(0 < \beta < 1\) . Then
\({{\beta \mathcal {P }}^{{\intercal }}_\alpha (w)}\)  is at most \(2 (\alpha +1) E(w) / \beta \) .

Let \(\sigma \in \beta \mathcal {P }_\alpha (w)\)  (or \(\sigma \in {\beta \mathcal {P }}^{{\intercal }}_\alpha (w)\) ).
The gapped palindrome \(\sigma \)  consists of the triple \(({u}_{{\lambda }},v,{u}_{{\rho }}) \in \beta \mathcal {P }_\alpha (w)\) .
By definition, the left arm \({u}_{{\lambda }}\)  has a periodic prefix \({s}_{{\lambda }}\)  of length at least \(\beta {{u}_{{\lambda }}}\) .
Let \({r}_{{\lambda }}\)  denote the run that generates \({s}_{{\lambda }}\) , i.e.,
\({s}_{{\lambda }}\subseteq {r}_{{\lambda }}\)  and they both have the common shortest period \(p\) .
By the definition of gapped palindromes, there is a right copy \({s}_{{\rho }}\)  of \({s}_{{\lambda }}\)  contained in \({u}_{{\rho }}\)  with
\({s}_{{\rho }}=w[\mathsf {b}({u}_{{\rho }})+(\mathsf {e}({u}_{{\lambda }})-\mathsf {e}({s}_{{\lambda }})), \mathsf {b}({u}_{{\rho }})+(\mathsf {e}({u}_{{\lambda }})-\mathsf {e}({s}_{{\lambda }}))+{{s}_{{\lambda }}}-1] \equiv {{s}_{{\lambda }}}^{{\intercal }}\) 
Let \({r}_{{\rho }}\)  be a run generating \({s}_{{\rho }}\)  (it is possible that \({r}_{{\rho }}\)  and \({r}_{{\lambda }}\)  are identical).
By definition, \({r}_{{\rho }}\)  has the same period \(p\)  as \({r}_{{\lambda }}\) .
In the following, we will see that \(\sigma \)  is uniquely determined by \({r}_{{\lambda }}\)  and
the distance \(d := \mathsf {b}({s}_{{\rho }}) - \mathsf {e}({s}_{{\lambda }})\) , if \(\sigma \)  is a periodic gapped palindrome.
We will fix \({r}_{{\lambda }}\)  and study how many maximal periodic gapped repeats (palindromes) can be generated by \({r}_{{\lambda }}\) .
<FIGURE>Since \(\sigma \)  is maximal, \(\mathsf {b}({u}_{{\lambda }}) = \mathsf {b}({r}_{{\lambda }})\)  or \(\mathsf {e}({u}_{{\rho }}) = \mathsf {e}({r}_{{\rho }})\)  must hold;
otherwise we could extend \(\sigma \)  outwards.
We analyze the case \(\mathsf {b}({s}_{{\lambda }}) = \mathsf {b}({r}_{{\lambda }})\) , the other is treated exactly in the same way by symmetry.
The gapped palindrome \(\sigma \)  is identified by \({r}_{{\lambda }}\)  and \(d\) .
We fix \({r}_{{\lambda }}\)  and count the number of possible values for \(d\) .
Given two different periodic \(\alpha \) -gapped palindromes with the distances \(d_1\)  and \(d_2\) ,
the difference between \(d_1\)  and \(d_2\)  must be at least \(p\) , due to lemmaRepetitionsOverlap.
It follows from \({{u}_{{\lambda }}} \le {{s}_{{\lambda }}} / \beta \)  that
\(d = {v} + 2({{u}_{{\lambda }}}-{{s}_{{\lambda }}}) \le {v} + 2 {{s}_{{\lambda }}} / \beta \) .
Since \(\sigma \)  is \(\alpha \) -gapped, \({v} \le (\alpha - 1) {{u}_{{\lambda }}} \le (\alpha - 1) {{s}_{{\lambda }}} / \beta \) , and hence,
\(1 \le d \le {{s}_{{\lambda }}} (\alpha +1) / \beta \) .
Then the number of possible values for the distance \(d\)  is bounded by
\({{s}_{{\lambda }}} (\alpha +1) / (\beta p) \le {{r}_{{\lambda }}} (\alpha +1) / (\beta p) = \exp ({r}_{{\lambda }}) (\alpha +1) / \beta \) .
In total, the number of maximal \(\alpha \) -gapped palindromes in this case is bounded by \((\alpha +1) E(w) / \beta \)  for the case
\(\mathsf {b}({u}_{{\lambda }}) = \mathsf {b}({r}_{{\lambda }})\) .
Summing up we get the bound \(2 (\alpha +1) E(w) / \beta \) .
Lemma  
Given a word \(w\) , and two real numbers \(\alpha > 1\)  and \(6/7 \le \beta < 1\) .
The points mapped by two different maximal gapped palindromes in \({\overline{\beta \mathcal {P }}}^{{\intercal }}_\alpha (w)\)  cannot \(\frac{1-\beta }{\alpha }\) -cover the same point.

Let \(\sigma = {u}_{{\lambda }},v,{u}_{{\rho }}\)  and \(\overline{\sigma }= \overline{{u}_{{\lambda }}},\overline{v},\overline{{u}_{{\rho }}}\)  be two different gapped palindromes in \({\overline{\beta \mathcal {P }}}^{{\intercal }}_\alpha (w)\) .
Set \(u:= {{u}_{{\lambda }}} = {{u}_{{\rho }}}\) , \(\overline{u}:= {\overline{{u}_{{\lambda }}}} = {\overline{{u}_{{\rho }}}}\) , \(g:= {v}\)  and \(\overline{g} := {\overline{v}}\) .
We map the maximal gapped palindromes \(\sigma \)  and \(\overline{\sigma }\)  to the points \((\mathsf {e}({u}_{{\lambda }}), g)\)  and \((\mathsf {e}(\overline{{u}_{{\lambda }}}),\overline{g})\) , respectively.
Assume, for the sake of contradiction, that both points \(\frac{1-\beta }{\alpha }\) -cover the same point \((x, y)\) .
Let \(z:= {\mathsf {e}({u}_{{\lambda }}) - \mathsf {e}(\overline{{u}_{{\lambda }}})}\)  be the difference of the endings of both left arms, and
\({s}_{{\lambda }}:= w[ [\mathsf {b}({u}_{{\lambda }}),\mathsf {e}({u}_{{\lambda }})]\cap [\mathsf {b}(\overline{{u}_{{\lambda }}}),\mathsf {e}(\overline{{u}_{{\lambda }}})] ]\) 
be the overlap of \({u}_{{\lambda }}\)  and \(\overline{{u}_{{\lambda }}}\) .
Let \(s= {{s}_{{\lambda }}}\) ,
and let \({s}_{{\rho }}\)  (resp. \(\overline{{s}_{{\rho }}}\) ) be the reversed copy of \({s}_{{\lambda }}\)  based on \(\sigma \)  (resp. \(\overline{\sigma }\) ).
Sub-Claim: The overlap \({s}_{{\lambda }}\)  is not empty, and \({s}_{{\rho }}\ne  \overline{{s}_{{\rho }}}\)
Sub-Proof.
Assume for this sub-proof that \(\mathsf {e}({u}_{{\lambda }}) < \mathsf {e}(\overline{{u}_{{\lambda }}})\)  (otherwise exchange \(\sigma \)  with \(\overline{\sigma }\) , or yield the contradiction \(\sigma = \overline{\sigma }\) ).
By combining the \((1-\beta )/\alpha \) -cover property with the fact that \(\overline{\sigma }\)  is \(\alpha \) -gapped, we yield
\(\mathsf {e}(\overline{{u}_{{\lambda }}}) - \overline{u}\le \mathsf {e}(\overline{{u}_{{\lambda }}}) - \overline{g}(1-\beta )/\alpha \le x \le \mathsf {e}({u}_{{\lambda }}) < \mathsf {e}(\overline{{u}_{{\lambda }}}).\) 
So the subword \(w[\mathsf {e}({u}_{{\lambda }})]\)  is contained in \(\overline{{u}_{{\lambda }}}\) .
If \({s}_{{\rho }}= \overline{{s}_{{\rho }}}\) , then we get a contradiction to the maximality of \(\sigma \) :
By the above inequality, \(w[\mathsf {e}({u}_{{\lambda }})+1]\)  is contained in \(\overline{{u}_{{\lambda }}}\) , too.
Since \(\overline{\sigma }\)  is a gapped palindrome, the character \(w[\mathsf {e}({u}_{{\lambda }})+1]\)  occurs in \(\overline{{u}_{{\rho }}}\) , exactly at \(w[\mathsf {b}({u}_{{\rho }})-1]\) .
\(\Box \)
Without loss of generality let \(g\le \overline{g}\) .
Then
\(\overline{g} - \frac{\overline{g}(1-\beta )}{\alpha } \le y \le g\le \overline{g}.\) 
So the difference of both gaps is
\(0 \le \delta := \overline{g} - g\le \overline{g}(1-\beta )/\alpha \le \overline{u}(1-\beta ).\) 
By case analysis, we show that \({s}_{{\lambda }}\)  is periodic,
which leads to the contradiction that \(\sigma \)  or \(\overline{\sigma }\)  are in \({\beta \mathcal {P }}^{{\intercal }}_\alpha (w)\) .
1. Case \(\mathsf {e}({u}_{{\lambda }}) \le \mathsf {e}(\overline{{u}_{{\lambda }}})\).
Since \(\mathsf {e}(\overline{{u}_{{\lambda }}}) - \overline{g}(1-\beta )/\alpha \le x \le \mathsf {e}({u}_{{\lambda }}) \le \mathsf {e}(\overline{{u}_{{\lambda }}})\) ,
\(z= \mathsf {e}(\overline{{u}_{{\lambda }}}) - \mathsf {e}({u}_{{\lambda }}) \le \overline{g}(1-\beta )/\alpha \le \overline{u}(1-\beta ).\) 
Since \({s}_{{\lambda }}\)  is a prefix of \(\overline{{u}_{{\lambda }}}\)  and a suffix of \({u}_{{\lambda }}\) ,
the reverse copy \({s}_{{\rho }}\)  is a suffix of \(\overline{{u}_{{\rho }}}\)  and a prefix of \({u}_{{\rho }}\) .
The starting positions of both right copies \(\overline{{s}_{{\rho }}}\)  and \({s}_{{\rho }}\)  differ by \(\mathsf {b}(\overline{{s}_{{\rho }}}) - \mathsf {b}({s}_{{\rho }}) = 2z+ \delta > 0\) .
By equOrdGapRulePal,equOrdGapRulePosFirstLeftPal, we get \(2z+ \delta \le 3 \overline{g}(1-\beta )/\alpha \le 3 \overline{u}(1-\beta )\) .
<FIGURE>1a. Sub-Case \(\mathsf {b}({u}_{{\lambda }}) \le \mathsf {b}(\overline{{u}_{{\lambda }}})\).
By equOrdGapRulePosFirstLeftPal, we get \(s= \overline{u}- z\ge \overline{u}\beta \) .
It follows from \(6/7 \le \beta < 1\)  that \(s/ (2z+ \delta ) \ge \overline{u}\beta / 3 \overline{u}(1-\beta ) = \beta / (3(1-\beta )) \ge 2\) ,
which means that \({s}_{{\rho }}\)  and \(\overline{{s}_{{\rho }}}\)  overlap by at least half of their common length, and \({s}_{{\lambda }}\)  is periodic.
Since \({s}_{{\lambda }}\)  is a prefix of \(\overline{{u}_{{\lambda }}}\)  of length \(s\ge \overline{u}\beta \) , \(\overline{\sigma }\)  is in \({\beta \mathcal {P }}^{{\intercal }}_\alpha (w)\) , a contradiction.
<FIGURE>1b. Sub-Case \(\mathsf {b}({u}_{{\lambda }}) > \mathsf {b}(\overline{{u}_{{\lambda }}})\).
We conclude that \({s}_{{\lambda }}= {u}_{{\lambda }}\) .
By equOrdGapRuleInvPal,
\(u\ge g/\alpha \ge \frac{\overline{g}}{\alpha } (1 - \frac{1-\beta }{\alpha }) \ge \overline{g}\beta /\alpha .\) 
It follows from \(6/7 \le \beta < 1\)  that \(s/ (2z+ \delta ) \ge \overline{g} \alpha \beta / (3 \alpha \overline{g} (1-\beta )) = \beta / (3(1-\beta )) \ge 2\) ,
which means that \({s}_{{\lambda }}= {u}_{{\lambda }}\)  is periodic.
Hence \(\sigma \)  is in \({\beta \mathcal {P }}^{{\intercal }}_\alpha (w)\) , a contradiction.
2. Case \(\mathsf {e}({u}_{{\lambda }}) > \mathsf {e}(\overline{{u}_{{\lambda }}})\).
Since \(\mathsf {e}({u}_{{\lambda }}) - g(1-\beta )/\alpha \le x \le \mathsf {e}(\overline{{u}_{{\lambda }}}) \le \mathsf {e}({u}_{{\lambda }})\) ,
\(z= \mathsf {e}({u}_{{\lambda }}) - \mathsf {e}(\overline{{u}_{{\lambda }}}) \le g(1-\beta )/\alpha \le \overline{g}(1-\beta )/\alpha \le \overline{u}(1-\beta ).\) 
The starting positions of both right copies differ by \({\mathsf {b}({s}_{{\rho }}) - \mathsf {b}(\overline{{s}_{{\rho }}})} = {2z- \delta }\) .
Since \(2z- \delta \le \max {\delta ,2z}\) ,
we get \({2z- \delta } \le 2 \overline{g}(1-\beta )/\alpha \le 2 \overline{u}(1-\beta )\)  by equOrdGapRulePal,equOrdGapRulePosFirstRightPal.
<FIGURE>2a. Sub-Case \(\mathsf {b}({u}_{{\lambda }}) \le \mathsf {b}(\overline{{u}_{{\lambda }}})\).
We conclude that \({s}_{{\lambda }}= \overline{{u}_{{\lambda }}}\) .
It follows from \(6/7 \le \beta < 1\)  that \(s/ {2z- \delta } \ge \overline{u}/ (2 \overline{u}(1-\beta )) = 1 / (2(1-\beta )) \ge 7/2 > 2\) ,
which means that \({s}_{{\lambda }}= \overline{{u}_{{\lambda }}}\)  is periodic.
Hence \(\overline{\sigma }\)  is in \({\beta \mathcal {P }}^{{\intercal }}_\alpha (w)\) , a contradiction.
<FIGURE>2b. Sub-Case \(\mathsf {b}({u}_{{\lambda }}) > \mathsf {b}(\overline{{u}_{{\lambda }}})\).
By equOrdGapRulePosFirstRightPal, we get \(z\le u(1-\beta )\)  and thus \(s= u- z\ge \beta u\) .
It follows from equOrdGapRuleTakeFirstArmPal,equOrdGapRulePal, and \(2(\sqrt{2}-1) < 6/7 \le \beta < 1\)  that
\(s/ {2z- \delta } \ge \beta u/ (2 \overline{g}(1-\beta )/\alpha ) \ge \overline{g}\beta ^2 / (2 \overline{g}(1-\beta ))= \beta ^2 / (2 (1-\beta )) > 2\) ,
which means that \({s}_{{\lambda }}\)  is periodic.
Since \({s}_{{\lambda }}\)  is a prefix of \({u}_{{\lambda }}\)  of length \(s\ge u\beta \) , \(\sigma \)  is in \({\beta \mathcal {P }}^{{\intercal }}_\alpha (w)\) , a contradiction.
The next lemma follows immediately from lemmaPoints,lemmaPalNPCover.
Lemma  
For \(\alpha > 1\) , \(6/7 \le \beta < 1\)  and a word \(w\)  of length \(n\) , \({{\overline{\beta \mathcal {P }}}^{{\intercal }}_\alpha (w)} < 3 \alpha n / (1 - \beta )\) .

For \(\alpha > 1\)  and a word \(w\)  of length \(n\) , \({{\mathcal {G }}^{{\intercal }}_\alpha (w)} < 28 \alpha n + 7 n\) .


By lemmaP,lemmaPalNP,
\({{\mathcal {G }}^{{\intercal }}_\alpha (w)} = {{\beta \mathcal {P }}^{{\intercal }}_\alpha (w)} + {{\overline{\beta \mathcal {P }}}^{{\intercal }}_\alpha (w)} < 2 (\alpha +1) E(w) / \beta + 3 \alpha n / (1 - \beta )\)  for every \(6/7 \le \beta < 1\) .
Applying lemmaExponent, the term is upper bounded by \(6 (\alpha +1) n / \beta + 3 \alpha n / (1 - \beta )\) .
This number is minimal when \(\beta = 6/7\) , yielding the bound \(28 \alpha n + 7 n\) .

Auxiliary algorithmic results
Proof of Lemma .

Once we produce \({\mathit {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,\ell ]\) , then \(w[i,\ell ]\)  is the longest \(p\) -periodic factor starting on position \(i\) .
Proof of Lemma 

We construct the dictionary of basic factors of a word of length \(n\)  in \({\mathcal {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 \({\mathcal {O}}(\log \log n)\)  time (see, e.g., [25]}). When we have to return the occurrences of \(y=w[i,i+2^k-1]\)  in \(z=w[j,j+c 2^k -1]\) , we search in the basic factors-array corresponding to \(w[i,i+2^k-1]\)  the successor of \(j\)  and, respectively, the predecessor of \(j+c2^k -1\)  and then return a succinct representation of the occurrences of \(w[i,i+2^k-1]\)  between these two values. This representation can be obtained in \({\mathcal {O}}(c)\)  time. We just have to detect those occurrences that form a run; this can be done with a constant number of \({\mathit {LCP}}\)  queries. Indeed, for two consecutive occurrences, we compute the length of their overlap, which gives us a period of \(w[i,i+2^k-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+2^k-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+2^k-1]\)  from this run, and then move directly to the first occurrence of \(w[i,i+2^k-1]\)  appearing after this run and still in the desired range; as there are at most \({\mathcal {O}}(c)\)  runs and separate occurrences of the given basic factor that are in \(z\) , the conclusion follows.
<FIGURE>Proof of Lemma .
In [9]} the following result was shown. Lemma  follows directly.
Given a word \(v\) , \(|v|=\alpha \log n\) , we can process \(v\)  in time \({\mathcal {O}}(\alpha \log n)\)  time such that given any basic factor \(y=v[j\cdot 2^k+1,(j+1)2^{k}]\)  with \(j,k\ge 0\)  and \(j2^k+1> (\alpha -1)\log n\) , we can construct in \({\mathcal {O}}(\alpha )\)  time \({\mathcal {O}}(\alpha )\)  bit-sets, each storing \({\mathcal {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.
[[11]}]
A word \(w\)  of length \(n\)  can be processed in \({\mathcal {O}}(n)\)  time such that given any basic factor \(w[i,i+2^k-1]\)  with \(k\ge 0\) , we can retrieve in \({\mathcal {O}}(1)\)  time the range of the suffix array of \(w\)  of suffixes starting with \(w[i,i+2^k-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+2^k-1]\) .
The proof of Lemma REF  follows.

We first show how the proof works for \(\alpha =1\) .
We first build the suffix tree for \(v\)  in \({\mathcal {O}}(\log n)\)  time. We further process this suffix tree such that we can find in constant time, for each factor \(v[j\cdot 2^k+1,(j+1)2^{k}]\) , 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\cdot 2^k+1,(j+1)2^{k}]\) . According to Lemma REF , 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 \({\mathcal {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\cdot 2^k+1,(j+1)2^{k}]\)  we can immediately output a representation of this factor's occurrences in \(v\) .
This concludes the proof for \(\alpha =1\) .
For \(\alpha >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[(\alpha -1)\log n+1 ,\alpha \log n]\) , for \(0\le i\le \alpha -2\) , which allows us to find all the occurrences of the basic factors of \(v[(\alpha -1)\log n+1 ,\alpha \log n]\)  in \(v\) . The time is clearly \({\mathcal {O}}(\alpha )\) .
By this lemma, given a word \(v\) , \(|v|=\alpha \log n\) , and a basic factor \(y=v[j\cdot 2^k+1,(j+1)2^{k}]\) , with \(j,k\ge 0\)  and \(j2^k+1> (\alpha -1)\log n\) , we can produce \({\mathcal {O}}(\alpha )\)  bit-sets, each containing exactly \({\mathcal {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\le n\)  (which can be ensured by a \({\mathcal {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\ge 1\) , we can obtain in \({\mathcal {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 \({\mathit {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.


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 \({\mathcal {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 \({\mathit {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\) ).
Missing cases from the proof of Lemma .
<FIGURE><FIGURE>Assume \(u_\rho \)  starts on the first position of \(r_\rho \) . If \(u_\rho \)  ends on a position inside \(r_\rho \) , other than its last position, then \(u_\lambda \)  should end on the last position of \(r_\lambda \)  (otherwise, both arms could be extended to the right). This means that we know exactly the gap between the two arms of the \(\alpha \) -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_\lambda \)  which is a prefix of \(r_\rho \) , and see whether the two occurrences of this factor determine a maximal \(\alpha \) -gapped repeat. If \(u_\rho \)  ends on the last position of \(r_\rho \)  then we know the exact arm of the \(\alpha \) -gapped palindrome we are looking for (that is, if it also fulfils the length conditions). We can proceed just like in the case analyzed before, when we knew that \(u_\lambda =r_\lambda \) , only that in this case we have to determine the positions where \(u_\lambda \)  may start instead of those where \(u_\rho \)  started. Finally, if \(u_\rho \)  ends on a position to the right of \(r_\rho \) , then \(u_\lambda \)  should also end after \(r_\lambda \)  and the suffix of \(u_\lambda \)  occurring after \(r_\lambda \)  should be equal to the suffix of \(u_\rho \)  occurring after \(r_\rho \) . We determine this suffix by a longest common prefix query on \(x_m\) , and then we obtain exactly the arms of the repeat. We can check whether it is a valid maximal \(\alpha \) -gapped repeat, and, if so, return it.
The last case is when \(u_\rho \)  starts on a position to the left of \(r_\rho \) . Then \(u_\lambda \)  starts on a position occurring before the first position of \(r_\lambda \) , the prefix of \(u_\rho \)  occurring before the beginning of \(r_\rho \)  equals the prefix of \(u_\lambda \)  occurring before \(r_\lambda \) , 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 \(\alpha \) -gapped repeat.
