Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

Roman Kolpakov

Gregory Kucherov
email: gregory.kucherov@univ-mlv.fr

Optimal bounds for computing α-gapped repeats

Keywords: combinatorics on words, algorithms on strings, combinatorial algorithms, time complexity, repeats, gapped repeats, subrepetitions

diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Notation and basic definitions. Let w = w [START_REF] Lothaire | Combinatorics on Words[END_REF]w [START_REF] Galil | Time-space-optimal string matching[END_REF] . . . w[n] = w [1 . . n] be an arbitrary word. The length n of w is denoted by |w|. For any 1 ≤ i ≤ j ≤ n, the word w[i] • • • w[j] is called a factor of w and denoted by w[i . . j]. Note that notation w[i . . j] denotes two entities: a word and its occurrence starting at position i in w. To underline the second meaning, we will sometimes use the term segment. Speaking about the equality between factors can also be ambiguous, as it may mean that the factors are identical words or the same segment (i.e. the same occurrence). If two factors u and v are identical words, we call them equal and denote this by u = v. To express that u and v are the same segment, we use the notation u ≡ v. For any i = 1 . . . n, the factor w[1 . . i] (resp. w[i . . n]) is a prefix (resp. suffix) of w. By positions on w we mean indices 1, 2, . . . , n of letters in w. For any segment v ≡ w[i . . j] of w, positions i and j are called respectively start position and end position of v and denoted by beg(v) and end (v) respectively. Let u, v be two segments of w. Segment u is contained in v iff beg(v) ≤ beg(u) and end (u) ≤ end (v).

Letter

w[i] is contained in v iff beg(v) ≤ i ≤ end (v).
A positive integer p is called a period of w if w[i] = w[i + p] for each i = 1, . . . , n -p. Clearly, a word can have several periods. We denote by per(w) the smallest period of w and define the exponent of w as exp(w) = |w|/per(w). A word is called periodic if its exponent is at least 2. Occurrences of periodic words are called repetitions.

Repetitions, squares, runs. Patterns in strings formed by repeated factors are of primary importance in word combinatorics [START_REF] Lothaire | Combinatorics on Words[END_REF] as well as in various applications such as string matching algorithms [START_REF] Galil | Time-space-optimal string matching[END_REF][START_REF] Crochemore | Squares, cubes, and time-space efficient string searching[END_REF], molecular biology [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences -Computer Science and Computational Biology[END_REF], or text compression [START_REF] Storer | Data Compression: Methods and Theory[END_REF]. The simplest and best known example of such patterns is a factor of the form uu, where u is a nonempty word. Such repetitions are called squares. Squares have been extensively studied. While the number of all square occurrences can be quadratic (consider word a n ), it is known that the number of primitively-rooted squares is O(n log n) [START_REF] Crochemore | Squares, cubes, and time-space efficient string searching[END_REF], where a square uu is primitively-rooted if the exponent of u is not an integer greater than 1. An optimal O(n log n)-time algorithm for finding all primitively-rooted squares was proposed in [START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF] (see also [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF][START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF][START_REF] Crochemore | Algorithms on Strings[END_REF]).

Repetitions can be seen as a natural generalization of squares. A repetition in a given word is called maximal if it cannot be extended by at least one letter to the left nor to the right without changing (increasing) its minimum period. More precisely, a repetition r ≡ w[i . . j] in w is called maximal if it satisfies the following conditions:

1. w[i -1] = w[i -1 + per(r)] if i > 1, 2. w[j + 1 -per(r)] = w[j + 1] if j < n.
For example, word cababaaa has two maximal repetitions: ababa and aaa. Maximal repetitions are usually called runs in the literature. Since any repetition is contained in some run, the set of all runs can be considered as a compact encoding of all repetitions in the word. This set has many useful applications, see, e.g., [START_REF] Crochemore | Extracting powers and periods in a string from its runs structure[END_REF]. For any word w, we denote by R(w) the number of maximal repetitions in w and by E(w) the sum of exponents of all maximal repetitions in w. The following statements are proved in [START_REF] Kolpakov | On maximal repetitions in words[END_REF].

Theorem 1. max |w|=n E(w) = O(n). Corollary 1. max |w|=n R(w) = O(n).
A series of articles (e.g., [START_REF] Rytter | The number of runs in a string: Improved analysis of the linear upper bound[END_REF][START_REF] Rytter | The number of runs in a string[END_REF][START_REF] Crochemore | Maximal repetitions in strings[END_REF][START_REF] Puglisi | How many runs can a string contain?[END_REF][START_REF] Crochemore | Towards a solution to the "runs" conjecture[END_REF][START_REF] Deza | A d-step approach to the maximum number of distinct squares and runs in strings[END_REF][START_REF] Crochemore | On the maximal sum of exponents of runs in a string[END_REF]) focused on more precise upper bounds on E(w) and R(w) trying to obtain the best possible constant factor behind the O-notation. A breakthrough in this direction was recently made in [START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF] (preliminary version in [START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF]) where the so-called "runs conjecture" R(w [1..n]) < n was proved. To the best of our knowledge, the currently best upper bound R(w [1..n]) ≤ 22 23 n on R(w) for binary words w is shown in [START_REF] Fischer | Beyond the runs theorem[END_REF].

On the algorithmic side, an O(n)-time algorithm for finding all runs in a word of length n was proposed in [START_REF] Kolpakov | On maximal repetitions in words[END_REF] for the case of constant-size alphabet. Another O(n)-time algorithm, based on a different approach, has been proposed in [START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF]. The O(n) time bound holds for (polynomially-bounded) integer alphabets as well, see, e.g., [START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF]. However, for the case of unboundedsize alphabets where characters can only be tested for equality, the lower bound Ω(n log n) on computing all runs has been known for a long time [START_REF] Main | Linear time recognition of squarefree strings[END_REF]. It is an interesting open question (raised over 20 years ago in [START_REF] Breslauer | Efficient string algorithmics[END_REF]) whether the O(n) bound holds for an unbounded linearly-ordered alphabet. The best known bound for this problem is currently O(n • α(n)) [START_REF] Crochemore | Near-optimal computation of runs over general alphabet via non-crossing LCE queries[END_REF] (here α(•) is the inverse of the Ackermann function), improving on [START_REF] Kosolobov | Computing runs on a general alphabet[END_REF][START_REF] Gawrychowski | Faster longest common extension queries in strings over general alphabets[END_REF].

Gapped repeats and subrepetitions. Another natural generalization of squares and runs are factors of the form uvu where u and v are nonempty words. We call such factors gapped repeats. For a gapped repeat uvu, the left (resp. right) occurrence of u is called its left arm (resp. right arm), and v is called its gap. The period of this gapped repeat is |u| + |v|. For a gapped repeat π, we denote the length of its arms by c(π) and its period by p(π). Note that p(π) is not necessarily equal to per(π) but per(π) ≤ p(π). Note also that gapped repeats with distinct periods can have the same start and end positions in the word, i.e. they can occur in the same segment in the word. For example, in string cabacaabaa, segment abacaaba corresponds to two gapped repeats having arms a and aba and periods 7 and 5 respectively. Gapped repeats having different periods but forming the same segment are considered distinct. This means that in order to specify a gapped repeat it is generally not sufficient to specify its segment. Let u and u be equal factors such that end (u ) + 1 < beg(u ). Then we denote by (u , u ) the gapped repeat with left arm u and right arm u . Let l = |u | = |u |. Note that, since u = u , then for any i, j such that 1 ≤ i ≤ j ≤ l we have u [i . . j] = u [i . . j]. We will call factors u [i . . j] and u [i . . j] corresponding factors for the repeat (u , u ).

For any real α > 1, a gapped repeat π is called α-gapped if p(π) ≤ αc(π). The maximality of gapped repeats is defined similarly to that of repetitions: a gapped repeat (w[i . . j ], w[i . . j ]) in w is called maximal if it satisfies both of the following conditions:

1. w[i -1] = w[i -1] if i > 1, 2. w[j + 1] = w[j + 1] if j < n.
In other words, a gapped repeat π is maximal if its arms cannot be extended to the left nor to the right by one letter without breaking its period p(π). As observed in [START_REF] Kolpakov | Searching of gapped repeats and subrepetitions in a word[END_REF], any α-gapped repeat is contained either in a (unique) maximal α-gapped repeat with the same period, or in a (unique) maximal repetition with a period that is a divisor of the repeat's period. For example, in the above string cabacaabaa, the gapped repeat (ab)aca(ab) is contained in the maximal repeat (aba)ca(aba) with the same period 5. In string cabaaabaaa, the gapped repeat (ab)aa(ab) of period 4 is contained in the maximal repetition abaaabaaa of period 4. Since all maximal repetitions can be computed efficiently in O(n) time (see above), the problem of computing all α-gapped repeats in a word can be reduced to the problem of finding all maximal α-gapped repeats.

Several variants of the problem of computing gapped repeats have been studied earlier. In [START_REF] Brodal | Finding maximal pairs with bounded gap[END_REF], it was shown that all maximal gapped repeats with a gap length belonging to a specified interval can be found in time O(n log n + S), where n is the word length and S is output size. In [START_REF] Kolpakov | Finding repeats with fixed gap[END_REF], an algorithm was proposed for finding all gapped repeats with a fixed gap length d running in time O(n log d + S). In [START_REF] Kolpakov | Searching of gapped repeats and subrepetitions in a word[END_REF], it was proved that the number of maximal α-gapped repeats in a word of length n is bounded by O(α 2 n) and all maximal α-gapped repeats can be found in O(α 2 n) time for the case of integer alphabet. A new approach to computing gapped repeats was proposed in [START_REF] Gawrychowski | Longest α-gapped repeat and palindrome[END_REF][START_REF] Dumitran | Longest gapped repeats and palindromes[END_REF] and more recently in [START_REF] Gawrychowski | Efficiently finding all maximal α-gapped repeats[END_REF]. In particular, in [START_REF] Gawrychowski | Longest α-gapped repeat and palindrome[END_REF] it was shown that the longest α-gapped repeat in a word of length n over an integer alphabet can be found in O(αn) time. In a recent paper [START_REF] Tanimura | A faster algorithm for computing maximal α-gapped repeats in a string[END_REF], an algorithm was proposed for finding all maximal α-gapped repeats in O(αn + S) time where S is the output size, for a constant-size alphabet. The algorithm uses an approach previously introduced in [START_REF] Badkobeh | Computing the maximalexponent repeats of an overlap-free string in linear time[END_REF].

Recall that repetitions are segments of exponent at least 2. Another way to approach gapped repeats is to consider segments with exponent smaller than 2, but (strictly) greater than 1. Clearly, such a segment corresponds to a gapped repeat π = uvu with per(π) = p(π) = |u| + |v|. We call such factors (segments) subrepetitions. More precisely, for any δ, 0 < δ < 1, by a δ-subrepetition we mean a factor z that satisfies 1 + δ ≤ exp(z) < 2. Again, the notion of maximality straightforwardly applies to subrepetitions as well: maximal subrepetitions are defined exactly in the same way as maximal repetitions. The relationship between maximal subrepetitions and maximal gapped repeats was clarified in [START_REF] Kolpakov | Searching of gapped repeats and subrepetitions in a word[END_REF]. Directly from the relationship, a maximal subrepetition π in a string w corresponds to a maximal gapped repeat satisfying p(π) = per(π). For example, in word aabababcababac, the maximal subrepetition abababcababa = abababc 12/7 of period 7 corresponds to the maximal gapped repeat (ababa)bc(ababa) of period 7. Furthermore, a maximal δ-subrepetition corresponds to a maximal 1 δ -gapped repeat. However, there may be more maximal 1 δ -gapped repeats than maximal δ-subrepetitions. One reason for that is that one maximal subrepetition may correspond to several maximal gapped repeats with different periods. Thus, in the above example, maximal subrepetition abababcababa contains three maximal gapped repeats: (ababa)bc(ababa), (aba)babcab(aba), and (a)bababcabab(a). Another reason is that a maximal gapped repeat may occur inside a repetition and not a subrepetition: e.g. word aabababb contains a maximal repetition ababab that corresponds to a maximal gapped repeat (ab)ab(ab).

Some combinatorial results on the number of maximal subrepetitions in a string were obtained in [START_REF] Kolpakov | On maximal repetitions of arbitrary exponent[END_REF]. In particular, it was proved that the number of maximal δ-subrepetitions in a word of length n is bounded by O( n δ log n). In [START_REF] Kolpakov | Searching of gapped repeats and subrepetitions in a word[END_REF], an O(n/δ 2 ) bound on the number of maximal δ-subrepetitions in a word of length n was obtained. Moreover, in [START_REF] Kolpakov | Searching of gapped repeats and subrepetitions in a word[END_REF], two algorithms were proposed for finding all maximal δ-subrepetitions in the word running respectively in O( n log log n δ 2

) time and in O(n log n + n δ 2 log 1 δ ) expected time, over the integer alphabet. In [START_REF] Badkobeh | Computing the maximalexponent repeats of an overlap-free string in linear time[END_REF], it is shown that all subrepetitions with the largest exponent (over all subrepetitions) in an overlap-free string can be found in O(n) time for a constant-size alphabet.

Our results. Throughout the paper we assume a constant-size alphabet. In this work we improve the results of [START_REF] Kolpakov | Searching of gapped repeats and subrepetitions in a word[END_REF] on maximal gapped repeats: we prove an O(αn) bound on the number of maximal α-gapped repeats in a word of length n (Section 3). We show that this bound is asymptotically tight. The same bound has recently been proved independently in [START_REF] Gawrychowski | Efficiently finding all maximal α-gapped repeats[END_REF] using a different method based on techniques from [START_REF] Kolpakov | Searching of gapped repeats and subrepetitions in a word[END_REF]. From our bound, we additionally derive an O(n/δ) bound on the number of maximal δ-subrepetitions occurring in a word, which improves the bound of [START_REF] Kolpakov | On maximal repetitions of arbitrary exponent[END_REF] by a log n factor. Then, based on the algorithm of [START_REF] Gawrychowski | Longest α-gapped repeat and palindrome[END_REF], we obtain an asymptotically optimal O(αn) time bound for computing all maximal α-gapped repeats in a word (Section 4). Note that this bound also follows from [START_REF] Tanimura | A faster algorithm for computing maximal α-gapped repeats in a string[END_REF] that presents an O(αn + S) algorithm for computing all maximal α-gapped repeats. Here we present an alternative algorithm with the same bound that we obtained independently of [START_REF] Tanimura | A faster algorithm for computing maximal α-gapped repeats in a string[END_REF][START_REF] Gawrychowski | Efficiently finding all maximal α-gapped repeats[END_REF].

Preliminaries

In this section we state a few propositions that are used later in the paper. The following fact is well-known (see, e.g., [START_REF] Kolpakov | On primary and secondary repetitions in words[END_REF]Proposition 2]).

Proposition 1. Any period p of a word w for which |w| ≥ 2p is divisible by per(w), the smallest period of w.

Let ∆ be some natural number. A period p of some word w is called a ∆-period if p is divisible by ∆. The minimum ∆-period of w, if it exists, is denoted by p ∆ (w). The word w is called ∆-periodic if |w| ≥ 2p ∆ (w). It is clear that any ∆-periodic word is also periodic. Proposition 1 can be generalized in the following way.

Proposition 2. Any ∆-period p of a word w for which |w| ≥ 2p is divisible by p ∆ (w).

Proof. By Proposition 1, period p is divisible by per(w), so p is divisible by lcm(per(w), ∆). On the other hand, lcm(per(w), ∆) is a ∆-period of w. Thus, p ∆ (w) = lcm(per(w), ∆), and p is divisible by p ∆ (w) as stated.

Consider an arbitrary word w = w[1 . . n] of length n. Note that any repetition r in w can be extended to a unique maximal repetition r with the same minimum period. We call r the extension of r.

Let r be a repetition in the word w. We call any factor of w of length per(r) that is contained in r a cyclic root of r. For cyclic roots we have the following property, proved e.g. in [27, Proposition 2]. Proposition 3. Two cyclic root u , u of a repetition r are equal if and only if beg(u ) ≡ beg(u ) (mod per(r)).

Number of maximal repeats and subrepetitions

In this section, we obtain an improved upper bound on the number of maximal gapped repeats and subrepetitions in a string w. Following the general approach of [START_REF] Kolpakov | Searching of gapped repeats and subrepetitions in a word[END_REF], we split all maximal gapped repeats into three categories according to the periodicity properties of repeats: periodic, semiperiodic and ordinary repeats. Bounds for periodic and semiperiodic repeats are directly borrowed from [START_REF] Kolpakov | Searching of gapped repeats and subrepetitions in a word[END_REF], while for ordinary repeats, we obtain a better bound. Since the number of α-gapped repeats can be bounded by the number of α -gapped repeats, we assume without loss of generality that α = k for a natural number k.

We describe now the three types of maximal gapped repeats.

Periodic repeats. We say that a maximal gapped repeat uvu is periodic if its arms u are periodic strings (i.e. of exponent at least 2). The set of all periodic maximal α-gapped repeats in w is denoted by PP α . The following bound on the size of PP α was obtained in [START_REF] Kolpakov | Searching of gapped repeats and subrepetitions in a word[END_REF]Corollary 6].

Lemma 1. |PP k | = O(kn) for any integer k > 1.
Semiperiodic repeats. A maximal gapped repeat uvu is called prefix (respectively, suffix) semiperiodic if the arms u of this repeat are not periodic, but have a periodic prefix (respectively, suffix) whose length is at least half the arm length. For example, the repeat ababaabacccababaaba with arms ababaaba is prefix semiperiodic since its arms have the periodic prefix ababa.

A maximal gapped repeat is semiperiodic if it is either prefix semiperiodic or suffix semiperiodic. The set of all semiperiodic α-gapped maximal repeats is denoted by SP α . In [START_REF] Kolpakov | Searching of gapped repeats and subrepetitions in a word[END_REF]Corollary 8], the following bound was obtained on semiperiodic maximal α-gapped repeats.

Lemma 2 ([27]

).

|SP k | = O(kn) for any integer k > 1.
Ordinary repeats. Maximal gapped repeats which are neither periodic nor semiperiodic are called ordinary. The set of all ordinary maximal α-gapped repeats in the word w is denoted by OP α . In the rest of this section, we prove that the cardinality of OP α is O(αn).

To estimate the number of ordinary maximal k-gapped repeats, we use the following idea from [START_REF] Kolpakov | On primary and secondary repetitions in words[END_REF]. We represent a maximal repeat π ≡ (u , u ) in OP k by a triple (i, j, c) where i = beg(u ), j = beg(u

) and c = c(π) = |u | = |u |.
We view such triples as points in a three-dimensional space. Obviously, π is uniquely defined by values i, j and c, therefore two different repeats from OP k can not be represented by the same point.

For any two points (i , j , c ), (i , j , c ) we say that point (i , j , c

) covers point (i , j , c ) if i ≤ i ≤ i + c /6, j ≤ j ≤ j + c /6, c ≥ c ≥ 2c 3 . A point is covered by a repeat π if it is covered by the point representing π. By V [π]
we denote the set of all points covered by a repeat π. Then we show that no point can be covered by two different repeats from OP k . Lemma 3. Two different repeats from OP k cannot cover the same point.

Proof. By contradiction let π 1 ≡ (u 1 , u 1 ), π 2 ≡ (u 2 , u 2 ) be two different repeats from OP k covering the same point (i, j, c). Denote c 1 = c(π 1 ), c 2 = c(π 2 ), p 1 = per(π 1 ), p 2 = per(π 2 ). Note that beg(u 1 ) -beg(u 1 ) = p 1 and beg(u 2 ) -beg(u 2 ) = p 2 . Without loss of generality, we assume

c 1 ≥ c 2 . From c 1 ≥ c 2 , c 1 ≥ c ≥ 2c 1 3 , and c 2 ≥ c ≥ 2c 2 3 we have c 1 ≥ c 2 ≥ 2c 1 3 , i.e. c 2 ≤ c 1 ≤ 3c 2
2 . Note that w[i] is contained in both u 1 , u 2 , i.e. these left arms overlap. Therefore, if p 1 = p 2 , then the left arms u 1 , u 2 must coincide due to the maximality of these repeats, and then the repeats π 1 and π 2 must coincide as well. Thus,

p 1 = p 2 . Denote ∆ = |p 1 -p 2 | > 0. From beg(u 1 ) ≤ i ≤ beg(u 1 ) + c 1 /6 and beg(u 1 ) ≤ j ≤ beg(u 1 ) + c 1 /6 we have (j -i) -c 1 /6 ≤ p 1 ≤ (j -i) + c 1 /6.
Analogously, we have

(j -i) -c 2 /6 ≤ p 2 ≤ (j -i) + c 2 /6. Thus ∆ ≤ (c 1 + c 2 )/6, which, together with the inequality c 1 ≤ 3c 2 2 , implies ∆ ≤ 5c 2
12 . First consider the case when one of the arms u 1 , u 2 is contained in the other, i.e. u 2 is contained in u 1 since c 1 ≥ c 2 . In this case, u 1 contains some factor u 2 corresponding to the factor

u 2 in u 1 . Thus beg(u 2 ) -beg(u 2 ) = p 2 , beg( u 2 ) -beg(u 2 ) = p 1 and u 2 = u 2 = u 2 , so that |beg(u 2 ) -beg( u 2 )| = ∆,
and then ∆ is a period of u 2 for which ∆ ≤ 5 12 c 2 = 5 12 |u 2 |. Thus, u 2 is periodic, which contradicts that π 2 is not periodic. Now consider the case when u 1 , u 2 are not contained in one another. Denote by z the overlap between u 1 and u 2 . Let z be a suffix of u l and a prefix of u r where l, r = 1, 2, l = r. Then u l contains a suffix z corresponding to the suffix z in u l , and u r contains a prefix z corresponding to the prefix z in u r . Then z = z = z . Thus beg(z ) -beg(z ) = p l and beg( z ) -beg(z ) = p r and z = z = z , so that

|beg(z ) -beg( z )| = |p l -p r | = ∆,
therefore ∆ is a period of z and z , and so ∆ is a period of z . Note that in this case beg

(u l ) < beg(u r ) ≤ i ≤ beg(u l ) + c l /6, therefore 0 < beg(u r ) -beg(u l ) ≤ c l /6. Thus |z | = c l -(beg(u r ) -beg(u l )) ≥ 5 6 c l ≥ 5 6 c 2 .
From ∆ ≤ 5 12 c 2 and c 2 ≤ 6 5 |z | we obtain ∆ ≤ |z |/2. Thus, z is a periodic suffix of u l such that |z | ≥ 5 6 |u l |, i.e. π l is either suffix semiperiodic or periodic which contradicts π l ∈ OP k and ends the proof.

Denote by Q k the set of all points (i, j, c) for which 1 ≤ i, j, c ≤ n and i

< j ≤ i + ( 3 2 k + 1 4 )c. Lemma 4. Any point covered by a repeat from OP k belongs to Q k .
Proof. Let a point (i, j, c) be covered by some repeat π ≡ (u , u ) from OP k . Denote c = c(π). Note that w[i] and w[j] are contained respectively in u and u and n > c ≥ c ≥ 2c 3 > 0, so inequalities 1 ≤ i, j, c ≤ n and i < j follow. Note also that

j ≤ beg(u ) + c /6 = beg(u ) + per(π) + c /6 ≤ i + kc + c /6, therefore, taking into account c ≤ 3c 2 , we have j ≤ i + ( 3 2 k + 1 4
)c. This shows that (i, j, c) belongs to Q k as stated.

From Lemmas 3 and 4, we obtain

Lemma 5. |OP k | = O(nk).
Proof. Assign to each point (i, j, c) the weight ρ(i, j, c) = 1/c 3 . For any finite set A of points, we define

ρ(A) = (i,j,c)∈A ρ(i, j, c) = (i,j,c)∈A 1 c 3 .
Let π be an arbitrary repeat from OP k represented by the point (i , j , c ). Then

ρ(V [π]) = i ≤i≤i +c /6 j ≤j≤j +c /6 2c /3≤c≤c 1 c 3 > c 2 36 2c /3≤c≤c 1 c 3 .
Using an estimation of sums by integrals (as in [START_REF] Kolpakov | Searching of gapped repeats and subrepetitions in a word[END_REF]), one can deduce that Therefore,

π∈OP k ρ(V [π]) = Ω(|OP k |). (1)
Note also that

ρ(Q k ) ≤ n i=1 i<j≤i+( 3 2 k+ 1 4 )c n c=1 1 c 3 < n( 3 2 k + 1 4 )c n c=1 1 c 3 < 2nk n c=1 1 c 2 < 2nk ∞ c=1 1 c 2 = nkπ 2 3 . Thus, ρ(Q k ) = O(nk). (2)
By Lemma 4, any point covered by a repeat from OP k belongs to Q k . On the other hand, by Lemma 3, no point of Q k can be covered by two repeats from OP k . Therefore,

π∈OP k ρ(V [π]) ≤ ρ(Q k ).
Thus, using ( 1) and ( 2), we conclude that

|OP k | = O(nk) as expected.
Eventually, putting together Lemma 1, Lemma 2, and Lemma 5, we obtain that, for any integer k ≥ 2, the number of maximal k-gapped repeats in w is O(nk). As mentioned above, the bound straightforwardly generalizes to the case of real α > 1 since the number of α-gapped repeats can be bounded by the number of α -gapped repeats. We conclude with the following statement.

Theorem 2. For any α > 1, the number of maximal α-gapped repeats in w is O(αn).

Note that the bound of Theorem 2 is asymptotically tight under the natural restriction α ≤ n. To see this, consider words w k = (0110) k . It is easy to check that for a large enough α and k = Ω(α), w k contains Θ(α|w k |) maximal α-gapped repeats whose arms are single-letter words. For example, for α = 3+4 where = 0, 1, 2, . . ., word w k contains 1 2 ( +1)(2k -) maximal α-gapped repeats 01(1001) i 10 with arms 0, for i ≤ .

We now apply Theorem 2 to obtain an upper bound on the number of maximal δ-subrepetitions. The following proposition [27, Proposition 3] follows from the fact that each maximal δ-subrepetition defines at least one maximal 1/δ-gapped repeat (cf. Introduction).

Proposition 4 ([27]

). For 0 < δ < 1, the number of maximal δ-subrepetitions in a string is no more than the number of maximal 1/δ-gapped repeats.

Theorem 2 combined with Proposition 4 immediately implies the upper bound for maximal δ-subrepetitions stated in the following theorem. The bound improves on the bound of [START_REF] Kolpakov | On maximal repetitions of arbitrary exponent[END_REF] by a log n factor. Theorem 3. For 0 < δ < 1, the number of maximal δ-subrepetitions in w is O(n/δ).

The O(n/δ) bound on the number of maximal δ-subrepetitions is asymptotically tight, at least on an unbounded alphabet: word ab 1 ab 2 . . . ab k of length n = 2k contains Ω(n/δ) maximal δ-subrepetitions for δ ≤ 1/2.

Computing all maximal α-gapped repeats

In this section, we present an O(αn + S) algorithm for computing all maximal α-gapped repeats in a word w of length n. The same bound has been independently proved in [START_REF] Tanimura | A faster algorithm for computing maximal α-gapped repeats in a string[END_REF], here we present a different solution. Together with the O(αn) bound of Theorem 2, this yields an O(αn)-time algorithm.

To get the result, α-gapped repeats are split into two classes analyzed in the following sections.

Computing PR-repeats

Some maximal α-gapped repeats can be located within maximal repetitions (runs). For example, word cabababababaa contains maximal gapped repeats (a)babababab(a), (aba)babab(aba) and (ababa)b(ababa) within the run abababababa = (ab) 11/2 . In this section, we describe the structure of such repeats, and in particular the structure of repeats that are periodic (see Section 3), like the repeat (ababa)b(ababa) above. We show how those maximal α-gapped repeats can be extracted from the runs in the input string. Repeats that are located within runs but are not periodic are found separately, together with other repeats (periodic or not) that are not located within runs. This latter part is described in the next section.

Let π ≡ (u , u ) be a periodic gapped repeat. If the extensions of u and u are the same repetition r then we say that r generates π and we call π a PRrepeat (that stands for Periodic Run-generated). Other gapped repeats are just called non-PR repeats. Later on we use the following sufficient condition for PR-repeats. Proposition 5. Let π ≡ (u , u ) be a maximal gapped repeat whose arms u and u contain a pair of corresponding factors having the same extension r. Then π is generated by r.

Proof. Observe that to prove the proposition, it is enough to show that both arms u and u are contained in r, i.e. beg(r) ≤ beg(u ) and end (r) ≥ end (u ). By contradiction, let beg(r) > beg(u ). Then both letters w[beg(r)-1] and w[beg(r) -1 + per(r)] are contained in u . Let these letters be respectively j-th and (j + per(r))-th letters of u . Then we have u [j] = u [j] = u [j + per(r)] = u [j + per(r)], i.e. u [j] = u [j + per(r)], which is a contradiction to the fact that both letters u [j] and u [j + per(r)] are contained in r. The inequality end (r) ≥ end (u ) is proved similarly.

All maximal PR-repeats can be easily computed according to the following lemma. Proof. Let π be generated by r. Consider prefixes of u and u of length per(r). These prefixes are equal cyclic roots of r, and by Proposition 3 the difference beg(u ) -beg(u ) = p(π) is divisible by per(r). Inequalities |r|/2 < p(π) ≤ |r| -2per(r) follow immediately from the definition of a repeat generated by a repetition. To prove the last two conditions of the lemma, it is sufficient to prove beg(u ) = beg(r) and end (u ) = end (r). Let beg(u ) = beg(r), i.e. beg(u ) > beg(r). Then both letters w[beg(u ) -1] and w[beg(u ) -1] are contained in r. Thus, since the difference (beg(u ) -1) -(beg(u )-1) = p(π) is divisible by per(r), we have w[beg(u )-1] = w[beg(u )-1] which contradicts the maximality of π. The relation end (u ) = end (r) is proved analogously. Thus, all the conditions of the lemma are proved. On the other hand, if π satisfies all the conditions of the lemma then π is obviously generated by r.

Corollary 2. A maximal repetition r generates no more than exp(r)/2 maximal PR-repeats, and all these repeats can be computed from r in O(exp(r)) time.

To find all maximal α-gapped PR-repeats in a string w, we first compute all maximal repetitions in w in O(n) time (see Introduction). Then, for each maximal repetition r, we output all maximal α-gapped repeats generated by r. Using Corollary 2, this can be done in O(exp(r)) time. Thus the total time of processing all maximal repetitions is O(E(w)). Since E(w) = O(n) by Theorem 1, all maximal α-gapped PR-repeats in w can be computed in O(n) time.

Computing non-PR-repeats

We now turn to the most laborious part of the algorithm: computation of maximal α-gapped non-PR-repeats. Recall that non-PR-repeats are those which are either non-periodic, or periodic but not located within a single run that is the extension of their arms. For example, gapped repeat (ababa)aba(ababa) is periodic but is a non-PR-repeat because its periodic arms ababa with minimum period 2 are not contained in a single run with the same minimum period. Our goal is to show that all maximal α-gapped non-PR-repeats can be found in O(αn) time. Observe that there exists a straightforward algorithm for computing all maximal α-gapped repeats in O(n 2 ) time that proceeds as follows: for each period p < n, find all maximal α-gapped repeats with period p in O(n) time by consecutively comparing symbols w[i] and w[i + p] for i = 1, 2, . . . , n -p.

From the results of [START_REF] Brodal | Finding maximal pairs with bounded gap[END_REF], it follows that all maximal α-gapped repeats can be found in time O(n log n + S). This, together with Theorem 2, leads to an O(αn)-time algorithm for the case α ≥ log n. Therefore, we only have to consider the case α < log n.

(i) Preliminaries

Assume that α < log n. For this case, we proceed with a modification of the algorithm of [START_REF] Gawrychowski | Longest α-gapped repeat and palindrome[END_REF]. We compute all maximal α-gapped non-PR-repeats π in w for which c(π) ≥ log n. To do so, we divide w into blocks of ∆ = (log n)/4 consecutive symbols of w. Without loss of generality, we assume that n = 2 k ∆, i.e. w contains exactly 2 k blocks. A word x of length 2 l ∆ where 0 ≤ l ≤ k-1 is called a basic factor of w if x = w[i∆+1 . . (i+2 l )∆] for some i. Such an occurrence w[i∆ + 1 . . (i + 2 l )∆] of x starting at a block frontier will be called aligned. A basic factor x of length 2 l ∆, where 1 ≤ l ≤ k -1, is called superbasic if x = w[q2 l ∆ + 1 . . (q + 1)2 l ∆] for some q. Similar to basic factors, an occurrence of a superbasic factor x starting at the frontier between two consecutive tuples of 2 l blocks (i.e. at a position (i2 l ∆ + 1) for some l) is also called aligned.

Aligned and unaligned occurrence of basic and superbasic factors are illustrated in Figure 1. Note that w contains O(n) aligned occurrences of basic factors and O( n log n ) aligned occurrences of superbasic factors.

Let z ≡ w[q2 l ∆ + 1 . . (q + 1)2 l ∆] be an aligned occurrence of a superbasic factor of length 2 l ∆ in w. For τ = 0, 1, . . . ∆ -1, an occurrence w[q2 l ∆ + 1 + τ . . (q2 l +2 l-1 )∆+τ ] of a basic factor of length 2 l-1 ∆ is called τ -associated (or simply associated) with z. Note that any basic factor occurrence τ -associated with z is entirely contained in z and is uniquely defined by the word z and τ . Thus, z has no more than ∆ associated occurrences of basic factors.

w = ∆ q 2 l +1 2 l ∆+1 2 l ∆ (q+1) ∆ ∆ i (i+ )
To continue, we need one more definition: for 1 ≤ i, j ≤ n, denote by LCP(i, j) the length of the longest common prefix of w[i . . n] and w[j . . n], and by LCS(i, j) the length of the longest common suffix of w[1 . . i] and w[1 . . j].

Let π ≡ (u , u ) be a maximal gapped repeat in w for which c(π) ≥ log n = 4∆. Note that in this case, the left arm u contains at least one aligned occurrence of superbasic factor. Consider aligned occurrences of superbasic factors of maximal length contained in u . Note that u can contain either one or two adjacent such occurrences. Let z be the leftmost of them. Remark that in this case, we have the following restrictions imposed on u : beg(z) -|z| < beg(u ) ≤ beg(z), end (z) ≤ end (u ) < end (z) + 2|z|.

(3)

Thus, c(π) < 4|z|. Consider factor z in u corresponding to z in u . Note that z can be non-aligned. Consider in z the leftmost aligned basic factor y of length |z |/2. Observe that beg(z ) ≤ beg(y ) < beg(z ) + ∆ and y is entirely contained in z . Let y be the factor of z corresponding to factor y in z . It is easily seen that y is an occurrence of a basic factor associated with z, and π is uniquely defined by z, y and y . Thus, any maximal gapped repeat π for which c(π) ≥ log n is uniquely defined by a triple (z, y , y ), where z is an aligned occurrence of some superbasic factor, y is an occurrence of some basic factor associated with z, and y is an aligned occurrence of the same basic factor. From now on, we say in such case that π is defined by the triple (z, y , y ).

Observe that π ≡ (u , u ) can be retrieved from (z, y , y ) using LCP and LCS functions as follows:

beg(u ) = beg(y ) -LCS(beg(y ) -1, beg(y ) -1), end (u ) = end (y ) + LCP(end (y ) + 1, end (y ) + 1), beg(u ) = beg(y ) -LCS(beg(y ) -1, beg(y ) -1), end (u ) = end (y ) + LCP(end (y ) + 1, end (y ) + 1).

(4)

Assume additionally that π is an α-gapped repeat for α > 1. Then, on the one hand, taking into account inequalities (3) and c(π) < 4|z|, we have

end (y ) ≤ end (u ) = end (u ) + per(π) < end (z) + 2|z| + αc(π) < end (z) + 2|z| + 4α|z| < end (z) + 6α|z| = end (z) + 12α|y |.
On the other hand, beg(y ) ≥ beg(u ) > end (u ) ≥ end(z). Thus, for any triple (z, y , y ) defining a maximal α-gapped repeat in w, the occurrence y is contained in the segment w[end (z)+1 . . end (z)+12α|y |] of length 12α|y | to the right of z. We denote this segment by I(z).

(ii) High-level description of the computation of non-PR-repeats

The computation of non-PR-repeats is described in the rest of this section. Before going into detail, we give a high-level description of this part.

The main idea of the algorithm is to consider all triples (z, y , y ) which can define maximal α-gapped non-PR-repeats and, for each such triple, to check if it actually defines such a repeat, which is then computed and output. All the triples (z, y , y ) are considered in a natural way: for each aligned occurrence z of a superbasic factor and each occurrence y of a basic factor associated with z, we consider all aligned occurrences y of the same basic factor in segment I(z). The main difficulty in the algorithm is to enumerate all aligned occurrences y efficiently. In order to overcome this difficulty, we use precomputed linked lists alignocc contained all aligned occurrences of basic factors in the left-to-right order. In order to compute the lists alignocc, we first compute all basic and superbasic factors by naming occurrences of the same factor by a unique name, using the suffix tree of the whole word. Then, again with the suffix tree, we identify all occurrences of basic factors associated with aligned occurrences of superbasic factors. Finally, for each basic factor y we insert all aligned occurrences of y to the list alignocc(y). We now proceed to a detailed description.

(iii) Naming basic factors on a suffix tree and computing their associated occurrences

We now describe how this computation is implemented. First we construct the suffix tree of the input string w. Suffix tree is a classical data structure of size O(n) that can be built in O(n) time for a constant-size alphabet (see e.g. [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences -Computer Science and Computational Biology[END_REF][START_REF] Crochemore | Algorithms on Strings[END_REF]). A suffix tree can be preprocessed in O(n)-time to support retrieving LCP(i, j) for any i, j in constant time (see e.g. [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences -Computer Science and Computational Biology[END_REF]). Similarly, we precompute w to support LCS(i, j) for any i, j in constant time.

Then we compute all basic factors of w including superbasic factors. This computation is performed by naming all the basic factors, i.e. assigning to each aligned occurrence of a basic factor a name of this factor. The most convenient way to name basic factors is to assign to a basic factor y of length 2 l a pair (l, i), where i is the start position of the leftmost aligned occurrence of y in w. Note that since we have only n/∆ distinct start positions i, the size of the two-dimensional array required for working with these pairs is O(n). To perform the required computation, we first mark in the suffix tree each node labeled by a basic factor by the name of this factor (in the case when this node is implicit we make it explicit). To this end, for each node v of the suffix tree we compute the value minleaf (v) which is the smallest leaf number divisible by ∆ in the subtree rooted in v if such a number exists. This can be easily done in O(n) time during a bottom-up traversal of the tree. Then, each suffix tree edge (u, v) for which the string depth of u is less than 2 l , the string depth of v is not less than 2 l , and minleaf (v) is defined is treated in the following way: if the string depth of v is 2 l , node v is marked by name (l, minleaf (v)), otherwise a new node of string depth 2 l is created within edge (u, v) and marked by name (l, minleaf (v)). We call the obtained tree marked suffix tree. Since we have O(n) distinct basic factors, the marked suffix tree contains no more than O(n) additionally inserted nodes. Thus, this tree has O(n) size and is built in O(n) time.

To assign to each aligned occurrence w[i . . i + 2 l -1] of a basic factor the name of this factor, we perform a depth-first top-down traversal of the marked suffix tree. During the traversal we maintain an auxiliary array basancestor: at the first visit of a node marked by a name (l, m) we set basancestor[l] to m, and at the second visit of this node we reset basancestor[l] to undefined. While during the traversal we get to a leaf i divisible by ∆, for each l = 0, 1, . . . , k -1 we identify w[i . . i + 2 l -1] as an occurrence of the basic factor named by (l, basancestor[l]). Note that this traversal is performed in O(n) time.

Then, we compute all occurrences of basic factors associated with aligned occurrences of superbasic factors. This is done again during a depth-first topdown traversal of the marked suffix tree. During the traversal, we maintain the same auxiliary array basancestor. Assume that during the traversal we get to a leaf labelled by a position q2 p ∆ + 1 + τ , where q is odd and 0 ≤ τ < ∆. Then for each l = 0, 1, . . . , p -1 for which basancestor[l] is defined, we identify w[q2 p ∆ + 1 + τ . . (q2 p + 2 l )∆ + τ ] as an occurrence of the basic factor named (l, basancestor[l]), which is τ -associated with the superbasic factor occurrence w[q2 p ∆ + 1 . . (q2 p + 2 l+1 )∆]. Observe that this traversal is performed in O(n) time as well.

(iv) Computing lists of aligned occurrences of basic factors

Let y be a ∆-periodic basic factor (cf Section 2). Note that y is also periodic, and then any occurrence of y in w is a repetition. By Proposition 1, the period per(y) is a divisor of p ∆ (y). Given the value p ∆ (y), we can compute in constant time the extension r of any occurrence y of a ∆-periodic basic factor y as follows: beg(r) = beg(y ) -LCS(beg(y ) -1, beg(y ) + p ∆ (y) -1), end (r) = end (y ) + LCP(beg(y ) + 1, beg(y ) -p ∆ (y) + 1).

Using Proposition 2, it is easy to show that any set of all aligned occurrences of y having the same extension is a sequence of occurrences, where the difference between start positions of any two consecutive occurrences is equal to p ∆ (y), i.e. the start positions of all these occurrences form a finite arithmetic progression with common difference p ∆ (y). We will call such a set a series of occurrences. The following fact can be easily proved. At the next step of the algorithm, in order to effectively select appropriate occurrences y in the checked triples (z, y , y ), for each basic factor y we construct a linked list alignocc(y) of all aligned occurrences of y in the leftto-right order in w. If y is not ∆-periodic, each item of alignocc(y) consists of only one aligned occurrence of y defined, for example, by its start position (we will call such items ordinary). If y is ∆-periodic, each item of alignocc(y) contains a series of aligned occurrences of y. If a series of aligned occurrences of y consists of only one occurrence, we will consider the item of alignocc(y) for this series as ordinary, otherwise, if a series of aligned occurrences of y consists of at least two occurrences, the item of alignocc(y) for this series will be defined, for example, by start positions of leftmost and rightmost occurrences in the series and the value p ∆ (y) (such item will be called an s-item). The following fact follows from Proposition 6. To construct the lists alignocc, we insert for each i = 1, 2, . . . , n and each l = 0, 1, . . . , k -1 consecutively the occurrence y ≡ w[i . . i + 2 l -1] of some basic factor y to the appropriate list alignocc(y) as follows. Consider the last item in the current list alignocc(y). Let it be an ordinary item consisting of an occurrence y of y starting at position j. Denote δ = i -j. Consider the following two cases for δ. Case 1: δ > |y|/2. Then, by Proposition 7, y and y are contained in distinct items of alignocc(y), and in this case we insert y to alignocc(y) as a new ordinary item. Case 2: δ ≤ |y|/2. In this case, by Proposition 7, y and y are the first two occurrences of the same series of occurrences of y and, moreover, δ = p ∆ (y). Let r be the extension of the occurrences of this series. It is easy to see that end (r) = end (y ) + LCP(end (y ) + 1, end (y ) + 1), i.e. end (r) can be computed in constant time. From the values beg(y ), end (r) and p ∆ (y), we can compute in constant time the start position of the last occurrence of y in the considered series of occurrences and thereby identify completely this series. Thus, in this case we replace the last item of alignocc(y) by the identified series of occurrences of y. Now let the last item in alignocc(y) be a series of occurrences. Then, if y is not contained in this series, we insert y to alignocc(y) as a new ordinary item. Thus, each occurrence of a basic factor in w is processed in constant time, and the total time for construction of lists alignocc is O(n).

Furthermore, in order to optimize the selection of appropriate occurrences y in the checked triples (z, y , y ), for each pair (z, y ) where z is an aligned occurrence of a superbasic factor and y is an occurrence of some basic factor y associated with z, we compute a pointer firstocc(z, y ) to the first item in alignocc(y) containing at least one occurrence of y to the right of z. For these purposes, we use auxiliary lists factends(i) defined for each position i in w. Lists factends(i) consist of pairs (z, y ) and are constructed at the stage computation of occurrences associated with aligned occurrences of superbasic factors: each time we find a new occurrence y associated with an aligned occurrence z of a superbasic factor, we insert the pair (z, y ) into the list factends(end(z)+1). After construction of lists alignocc, we compute consecutively for each i = 1, 2, . . . , n pointers firstocc(z, y ) for all pairs (z, y ) from the list factends(i). During the computation, we save in each list alignocc(y) the last item pointed to before (this item is denoted by lastpnt(y)). To compute firstocc(z, y ), we go through the list alignocc(y) from lastpnt(y) (or from the beginning of alignocc(y) if lastpnt(y) does not exist) until we find the first item containing at least one occurrence of y to the right of the position i. The found item is pointed to by firstocc(z, y ) and becomes a new item lastpnt(y). Since the total size of lists alignocc and factends is O(n), the total time for computing firstocc(z, y ) is also O(n).

(v) Main step: computing large repeats

At the main stage of the algorithm, in order to process each pair (z, y ), note that all occurrences y contained in I(z) such that the triple (z, y , y ) defines a maximal α-gapped repeat are located in the fragment of alignocc(y) consisting of all items having at least one occurrence of y contained in I(z). We call this fragment a checked fragment. Thus, we consider all items of the checked fragment by going through this fragment from the first item which can be found in constant time by the value firstocc(z, y ). For each considered item, we check triples (z, y , y ) for all occurrences y from this item as follows.

Let the considered item be an ordinary item consisting of only one occur-rence y . Recall that gapped repeat (u , u ) defined by the triple (z, y , y ) can be computed in constant time by formulas (4). Thus, if (u , u ) is an α-gapped repeat satisfying conditions (3), we output it. Now let the item considered in the checked fragment be a s-item. This implies that the basic factor y is ∆-periodic, i.e y is ∆-periodic. Moreover, from the s-item we can derive the value p ∆ (y). Therefore we can compute in constant time extensions r and r of occurrences y and y respectively. Denote by ρ the series of occurrences contained in the s-item. Recall that our goal is to compute effectively all α-gapped repeats defined by triples (z, y , y ) for which y ∈ ρ. Observe that if r and r are the same repetition, then by Proposition 5 all such repeats are PR-repeats, therefore we can assume that r and r are distinct repetitions. Note that per(r ) = per(r ) = per(y). Let (u , u ) be an α-gapped repeat defined by a triple (z, y , y ) where y ∈ ρ. First, consider the case when u is not contained in r , i.e. either beg(u ) < beg(r ) or end (u ) > end (r ). From Propositions 8 and 9, we derive the following fact. Thus, for computing α-gapped repeats (u , u ) for which u is not contained in r , it is enough to consider in ρ only occurrences y left and y right with start positions s left and s right respectively, provided that these occurrences exist. We check the occurrences y left and y right in the same way as we did for occurrence y in the case of ordinary item. Then, it remains to check all occurrences from ρ except for possible occurrences y left and y right . Denote by ρ = ρ \ {y left , y right } the set of all such occurrences. Assume that |r | ≤ |r |, i.e. s left ≤ s right (the case |r | > |r | is similar). In order to check all occurrences from ρ , we consider the following subsets of ρ separately: subset ρ 1 of all occurrences y such that beg(y ) < s left , subset ρ 2 of all occurrences y for which s left < beg(y ) < s right , and subset ρ 3 of all occurrences y for which s right < beg(y ). Note that start positions of all occurrences in each of these subsets form a finite arithmetic progression with common difference p ∆ (y). Thus, we unambiguously denote all occurrences in each of the subsets ρ i , i = 1, 2, 3, by y 0 , y 1 , . . . , y k where y 0 is the leftmost occurrence in the subset ρ i and beg(y j ) = beg(y 0 ) + jp ∆ (y) for j = 1, . . . , k. Note that values beg(y 0 ) and k for each subset ρ i can be computed in constant time.

First, consider an occurrence y j from ρ 1 . Let π ≡ (u , u ) be the repeat defined by triple (z, y , y j ). Note that per(π) = beg(y j ) -beg(y ) = q + jp ∆ (y), [START_REF] Storer | Data Compression: Methods and Theory[END_REF] where q = beg(y 0 )-beg(y ). Taking into account that y and y j are contained in maximal repetitions r and r respectively, it is easy to verify that LCS(beg(y ) -1, beg(y j ) -1) = beg(y j ) -beg(r ), LCP(end (y ) + 1, end (y j ) + 1) = end (r ) -end (y ).

Therefore, beg(u ) = beg(r ) -per(π) = q -jp ∆ (y), where q = beg(r ) -q, and end (u ) = end (r ). It follows that

c(π) = |u | = end (u ) -beg(u ) + 1 = q + jp ∆ (y),
where q = end (r ) + 1 -q . Recall that for any α-gapped repeat π, we have c(π) < per(π) ≤ αc(π). Thus, π is an α-gapped repeat if and only if q < q ≤ αq + (α -1)jp ∆ (y).

Moreover, u has to satisfy conditions [START_REF] Crochemore | Squares, cubes, and time-space efficient string searching[END_REF]. Thus, the triple (z, y , y j ) defines an α-gapped repeat if and only if conditions ( 6) and ( 3) are verified for j. Note that all these conditions are linear inequalities on j, and then can be resolved in constant time. Thus, we output all α-gapped repeats defined by triples (z, y , y ) for which y ∈ ρ 1 in time O(1 + S), where S is the size of the output.

Consider now an occurrence y j from ρ 2 . Let π ≡ (u , u ) be the repeat defined by the triple (z, y , y j ). Note that in this case, per(π) also satisfies relation [START_REF] Storer | Data Compression: Methods and Theory[END_REF]. Analogously to the previous case of set ρ 1 , we obtain that beg(u ) = beg(r ) and end (u ) = end (r ), and then c(π) = |r |. Therefore, π is an α-gapped repeat if and only if

|r | < q + jp ∆ (y) ≤ α|r |. (7)
Thus, in this case, we output all α-gapped repeats defined by triples (z, y , y j ) for which j satisfies conditions ( 7) and ( 3). Since all these conditions can be resolved for j in constant time, all these repeats can be output in time O(1 + S) where S is the output size. Finally, consider an occurrence y j from ρ 3 . Let π ≡ (u , u ) be the repeat defined by triple (z, y , y j ). In this case, per(π) also satisfies relation [START_REF] Storer | Data Compression: Methods and Theory[END_REF]. Analogously to the case of set ρ 1 , we obtain that beg(u ) = beg(r ) and end (u ) = end (r ) -per(π) = q -jp ∆ (y), where q = end (r ) -q, and then c(π) = end (u ) -beg(u ) + 1 = q -jp ∆ (y), where q = q -beg(r ) + 1. Therefore, π is an α-gapped repeat if and only if q -jp ∆ (y) < q + jp ∆ (y) ≤ α( q -jp ∆ (y)).

Thus, in this case, we output all α-gapped repeats defined by triples (z, y , y j ) for which j satisfies conditions ( 8) and (3). Like in the previous cases, this can be done in time O(1 + S), where S is the output size. Putting together all the three considered cases, we conclude that all αgapped repeats defined by triples (z, y , y ) for which y ∈ ρ can be computed in time O(1 + S) where S is the output size. Thus, in O(1 + S) time we can process each item of the checked fragment. Therefore, since by Corollary 3 the checked fragment has O(α) items, the total time for processing pair (z, y ) is O(α + S) where S is the total number of α-gapped repeats defined by triples (z, y , y ). Since each occurrence z has no more than ∆ associated occurrences y , the total number of processed pairs (z, y ) is O(n). Thus the time complexity of the main stage of the algorithm is O(αn + S), where S is the size of the output. Taking into account that S = O(αn) by Theorem 2, we conclude that the time complexity of the main stage is O(αn). Thus, all maximal α-gapped non-PR-repeats π in w for which c(π) ≥ log n can be computed in O(αn) time. Algorithm 1 summarizes the computation of all large maximal α-gapped non-PR-repeats.

Algorithm 1 Computing of all large maximal α-gapped non-PR-repeats 1: construct the suffix trees of the string w and the reverse string w R 2: preprocess the suffix trees of w and w R for computing LCP(i, j) and LCS(i, j) in constant time for each aligned occurrence z ≡ w[q2 l ∆ + 1..(q + 1)2 l ∆] of superbasic factor do 8:

for each occurrence y of a basic factor y associated with z do check if triple (z, y , y ) defines a maximal α-gapped non-PRrepeat and, if so, compute and output this repeat To compute all remaining maximal α-gapped non-PR-repeats in w, i.e. maximal α-gapped non-PR-repeats π such that c(π) < log n, note that the length of any such repeat π is not greater than

(1 + α)c(π) < (1 + log n) log n < 2 log 2 n.
Thus, setting ∆ = 2 log 2 n , any such repeat is contained in at least one of the segments I i ≡ w[i∆ + 1 . . (i + 2)∆ ] for 0 ≤ i < n/∆ . Therefore, all the remaining α-gapped repeats can be found by searching segments I i separately. The procedure of searching for repeats in I i is similar to the algorithm described above. If α ≥ log log n, searching for repeats in I i can be done by the algorithm proposed in [START_REF] Brodal | Finding maximal pairs with bounded gap[END_REF]. The O(|I i | log |I i | + S) time complexity implied by this algorithm, where by Theorem 2 the output size S is O(α|I i |), can be bounded here by O(α∆ ). Thus, the total time complexity for searching all segments I i is O(αn). In the case of α < log log n, we search each segment I i for all remaining maximal α-gapped non-PR-repeats π in w for which c(π) ≥ log |I i | in time O(α∆ ), in the same way as we described above for the word w. The total time for searching all segments I i is O(αn). Then, it remains to compute all maximal α-gapped non-PR-repeats π in w for which c(π) < log |I i | ≤ 3 log log n. Observe that the length of any such repeat is not greater than (1 + α)3 log log n < (1 + log log n)3 log log n ≤ 6 log 2 log n.

Thus, setting ∆ = 6 log 2 log n , any such repeat is contained in at least one of the segments I i ≡ w[i∆ +1 . . (i+2)∆ ] for 0 ≤ i < n/∆ . Note that these segments are words of length 2∆ over an alphabet of size σ, therefore the total number of distinct segments I i is not greater than σ 2∆ ≤ σ 12 log 2 log n . In each of the distinct segments I i , all maximal α-gapped repeats can be found by the trivial algorithm described above in O(∆ 2 ) = O(log 4 log n) time. Thus, maximal α-gapped repeats in all distinct segments I i can be found in O(σ 12 log 2 log n log 4 log n) = o(n) time. We conclude that all remaining maximal α-gapped repeats in w can be found in O(n + S) time where S is the total number of maximal α-gapped repeats contained in all segments I i . According to Theorem 2, this number can be bounded by O(αn), and the time for finding all the remaining maximal α-gapped repeats can be bounded by O(αn) as well. This leads to the final result.

Theorem 4. For a fixed α > 1, all maximal α-gapped repeats in a word of length n over a constant alphabet can be found in O(αn) time.

Note finally that since, as mentioned earlier, a word can contain Θ(αn) maximal α-gapped repeats, the O(αn) time bound stated in Theorem 4 is asymptotically optimal.

Conclusion

Besides gapped repeats we can also consider gapped palindromes which are factors of the form uvu R where u and v are nonempty words and u R is the reversal of u [START_REF] Kolpakov | Searching for gapped palindromes[END_REF]. A gapped palindrome uvu R in a word w is called maximal if w[end (u) + 1] = w[beg(u R ) -1] and w[beg(u) -1] = w[end (u R ) + 1] for beg(u) > 1 and end (u R ) < |w|. A maximal gapped palindrome uvu R is αgapped if |u| + |v| ≤ α|u| [START_REF] Gawrychowski | Longest α-gapped repeat and palindrome[END_REF]. It can be shown in a way similar to the results of this paper that for α > 1 the number of maximal α-gapped palindromes in a word of length n is bounded by O(αn) and for the case of constant alphabet, all these palindromes can be found in O(αn) time 1 .

In this paper we consider maximal α-gapped repeats with α > 1. However this notion can be formally generalized to the case α ≤ 1. In particular, maximal 1-gapped repeats are maximal repeats whose arms are adjacent or overlapping. It is easy to see that such repeats form runs whose minimum periods are divisors of the periods of these repeats. Moreover, each run in a word is formed by at least one maximal 1-gapped repeat, therefore the number of runs in a word is not greater than the number of maximal 1gapped repeats. More precisely, each run r is formed by exp(r)/2 distinct maximal 1-gapped repeats. Thus, if a word contains runs with exponent not less than 4 then the number of maximal 1-gapped repeats is strictly greater than the number of runs. However, using an easy modification of the proof of "runs conjecture" from [START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF], it can be also proved that the number of maximal 1-gapped repeats in a word is strictly less than the length of the word.

Denoting by R(n) (respectively, R 1 (n)) the maximal possible number of runs (respectively, maximal possible number of maximal 1-gapped repeats) in words of length n, based on the fact that known words with a relatively large number of runs have no runs with big exponents, it seems that R(n) = R 1 (n).

Conjecture 1. The maximal number of runs in words of length n is equal to the maximal number of 1-gapped repeats.

We can also consider the case of α < 1 for repeats with overlapping arms, in particular, the case of maximal 1/k-gapped repeats where k is integer greater than 1. It is easy to see that such repeats form runs with exponents not less than k + 1. It is known from [START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF]Theorem 11] that the number of such runs in a word of length n is less than n/k, and it seems to be possible to modify the proof of this fact for proving that the number of maximal 1/kgapped repeats in the word is also less than n/k = αn. These observations together with results of computer experiments for the case of α > 1 leads to the following conjecture.

Conjecture 2. For any α > 0, the maximal number of α-gapped repeats in a word of length n is less than αn.

This generalization of the "runs conjecture" constitutes an interesting open problem. Another interesting open question is whether the obtained O(n/δ) bound on the number of maximal δ-subrepetitions is asymptotically tight for the case of constant-size alphabet.

Another interesting question is a generalization of the upper bound to the case of gapped repeats where the interval of possible gap lengths is specified by arbitrary functions on the arm length. Such a generalization was recently obtained in [START_REF] Kolpakov | On the number of gapped repeats with arbitrary gap[END_REF].

2c /3≤c≤c 1 c 3 ≥ 5 32 1 c 2

 13512 for any c . Thus, for any π from OP k ρ(V [π])

Lemma 6 .

 6 A maximal gapped periodic repeat π ≡ (u , u ) is generated by a maximal repetition r if and only if p(π) is divisible by per(r) and |r|/2 < p(π) ≤ |r| -2 per(r), u ≡ w[beg(r) . . end (r) -p(π)], u ≡ w[beg(r) + per(r) . . end (r)].

Figure 1 :

 1 Figure 1: Basic and superbasic factors

Proposition 6 .

 6 Let y , y be two consecutive aligned occurrences of a basic factor y in w. Then |beg(y ) -beg(y )| ≤ |y|/2 if and only if y is ∆-periodic, y and y are contained in the same series of occurrences, and, moreover, |beg(y ) -beg(y )| = p ∆ (y).

Proposition 7 .Corollary 3 .

 73 Let y , y be two consecutive aligned occurrences of a basic factor y in w. Then |beg(y ) -beg(y )| ≤ |y|/2 if and only if y and y are contained in the same s-item of alignocc(y) and, moreover, |beg(y )beg(y )| = p ∆ (y). Proposition 7 implies that if two aligned occurrences y , y of a basic factor y are contained in distinct items of alignocc(y) then |beg(y ) -beg(y )| > |y|/2. Therefore, we have the following consequence of the proposition. Let y be a basic factor of w. Then for any segment v in w, the list alignocc(y) contains O(|v|/|y|) items having at least one occurrence of y contained in v.

Proposition 8 .Proposition 9 .

 89 If beg(u ) < beg(r ), then beg(r ) -beg(u ) = beg(r )beg(u ). Proof. Define γ = beg(r ) -beg(u ), γ = beg(r ) -beg(u ). Assume by contradiction γ > γ . Since repetition r is maximal we have u [γ ] ≡ w[beg(r ) -1] = w[beg(r ) -1 + per(r )] ≡ u [γ + per(r )]. Moreover, from γ > γ we have that both letters u [γ ] and u [γ + per(r )] are contained in the repetition r , and u [γ ] = u [γ +per(r )] since per(r ) = per(r ). Thus, from u [γ ] = u [γ ] we obtain a contradiction u [γ +per(y)] = u [γ + per(y)]. Similarly, we obtain a contradiction u [γ + per(y)] = u [γ + per(y)] if it is assumed γ < γ . The following proposition can be proved similarly. If end (u ) > end (r ), then end (u ) -end (r ) = end (u )end (r ). Define s left = beg(y ) + (beg(r ) -beg(r )), s right = beg(y ) + (end (r ) -end (r )).

Corollary 4 .

 4 If beg(u ) < beg(r ) then beg(y ) = s left . If end (u ) > end (r ) then beg(y ) = s right .

3 :

 3 compute and name basic and superbasic factors 4: compute all occurrences of basic factors associated with superbasic factors 5: compute lists alignocc(y) of aligned occurrences of basic factors y 6: for l = 1, . . . , log(n/∆) -1 do 7:

9 :

 9 compute all aligned occurrences y of the basic factor y which are contained in I(z) by using list alignocc(y) 10:for each computed occurrence y do 11:

Note that in[START_REF] Gawrychowski | Longest α-gapped repeat and palindrome[END_REF], the number of maximal α-gapped palindromes was conjectured to be O(α

n).

Acknowledgements. A part of this work was done during a visit of RK to the LIGM Lab of Université Paris-Est, supported by a Metchnikov grant of the French Embassy in Russia. RK was partially supported by Russian Foundation for Fundamental Research (Grant 15-07-03102). GK was partially supported by Labex Bézout grant of the French government.