Maxime Crochemore

Lucian Ilie
email: ilie@csd.uwo.ca

Emine Seid-Hilmi

THE STRUCTURE OF FACTOR ORACLES * †

Keywords: factor oracle, string matching, suffix trie, suffix tree, graph quotient MSC: 68P05, 68P10, 68P20, 68Q45

The factor oracle is a relatively new data structure for the set of factors of a string. It has been introduced by Allauzen, Crochemore, and Raffinot in 1999. It may recognize nonfactors (hence the name "oracle") but its implementational simplicity and experimental behaviour are stunning; factor oracle based string matching has been conjectured optimal on average. However, its structure is not well understood. We take important steps in clarifying its structure by explaining how it can be obtained as a quotient of the trie of the set of factors. When seen this way, all known properties of the factor oracle become simple observations. Also, we introduce a framework where various oracles can be compared. The factor oracle is better than several natural ones obtained from the trie of the set of factors, the suffix and the factor automata, respectively.

Introduction

The factor oracle is a relatively new data structure for the set of factors of a string which has been introduced by Allauzen, Crochemore, and Raffinot in [START_REF] Allauzen | Factor oracle: a new structure for pattern matching[END_REF][START_REF] Allauzen | Efficient experimental string matching by weak factor recognition[END_REF]. The starting point was the notion of weak factor recognition which means constructing a no-biased algorithm for detecting factors of a string. (That is, when testing whether a string is a factor, a no answer is always correct.) In the string matching algorithms based on reversed factors, identifying correctly nonfactors is enough. Therefore, the factor oracle recognizes all factors of a string but may recognize some nonfactors as well (hence the name "oracle"). On the other hand, the string-matching algorithms based on it are as efficient as the best existing ones but far simpler to implement; they also require less memory. According to the experimental results, it has been conjectured in [START_REF] Allauzen | Factor oracle: a new structure for pattern matching[END_REF][START_REF] Allauzen | Efficient experimental string matching by weak factor recognition[END_REF] that these algorithms are optimal on average. A number of other applications of the factor oracle to data compression, repetitions searching, and learning have been investigated in [START_REF] Assayag | Using factor oracles for machine improvisation[END_REF][START_REF] Kato | Substring search and repeat search using factor oracles[END_REF][START_REF] Lefebvre | Compror: On-line lossless data compression with a factor oracle[END_REF][START_REF] Lefebvre | A heuristic for computing repeats with a factor oracle: application to biological sequences[END_REF][START_REF] Lefebvre | An improved algorithm for finding longest repeats with a modified factor oracle[END_REF].

The structure of the factor oracle is however not well understood. Proving various properties of it was, so far, rather difficult and therefore solving the open problems concerning it difficult to attempt.

We present here a different way of looking at the factor oracle, namely as a quotient of the trie for the set of factors. Using our construction, all known properties of the factor oracle become simple observations. Moreover, we introduce the general notion of an oracle for the set of factors of a string -the factor oracle is a particular case here -and build a framework for comparing such oracles since, arguably, all of them have to include a quotient of the trie.

Several other natural oracles can be obtained in this way and we prove that the factor oracle is the best among those. Particular examples exist when the factor oracle can be improved but whether there exists a general strategy for building better oracles remains open.

We hope that the new approach will be of help in solving various open problems concerning the factor oracle; see Section 9 for details.

The paper is structured as follows. We recall in the next section all basic concepts needed and then present in Section 3 a variant of Ukkonen's algorithm for building tries in which some additional information is computed; this information helps us later in constructing quotients of the trie. The very simple algorithm of [START_REF] Allauzen | Factor oracle: a new structure for pattern matching[END_REF][START_REF] Allauzen | Efficient experimental string matching by weak factor recognition[END_REF] for constructing the factor oracles is described briefly in Section 4. Section 5 describes an oracle naturally obtained from the trie, called trie oracle. In Section 6 we show how the factor oracle can be obtained from the trie oracle and why it is better. Two other natural oracles can be obtained from the suffix and the factor automata, respectively. We show in Section 7 that they are the same as the trie oracle and therefore never better than the factor oracle. Section 8 contains a direct construction of the factor oracle as a quotient of the trie, which makes it very simple to prove things about the factor oracle as done in Section 9. We conclude with a brief discussion in Section 10.

Basic definitions

Let A be an alphabet; A * is the free monoid generated by A, that is, the set of all finite strings over A. The empty string is ε. For a string w ∈ A * , we denote by |w| the length of w. If w = xyz, for w, x, y, z ∈ A * , then x, y, z are a prefix, factor, and suffix of w, resp. When different from w they are called proper. The set of all factors (suffixes) of w is denoted Fact(w) (Suff(w), respectively).

For a string w, we shall denote by suf(w) the longest proper suffix of w, that is the string obtained from w by removing its first letter; for the empty string we have suf(ε) = nil. The ith letter of w is w[i] and, for 1

≤ i ≤ j ≤ |w|, we denote w[i..j] = w[i]w[i + 1] • • • w[j].
A finite automaton is a directed graph. In an automaton the nodes are usually called states and the labelled edges are called transitions. where the edges are labelled by letters from A; if we have an edge i a -→ j, then j is an a-son of i. The automaton is deterministic if any node has at most one a-son, for any letter a and nondeterministic otherwise. To define the language recognized by an automaton, we need to identify an initial node and some final nodes. Then, the strings recognized are precisely those labelling paths from the initial node to a final node. The set of the strings recognized by an automaton M is denoted L(M ). In general, for a node i, the language L(i) is the set of all labels of paths starting from i and ending in a final node. Unless otherwise specified, all our graphs, when seen as automata, will have 0 or ε as initial node and all nodes are final.

The quotient of a graph G is any graph obtained from G by merging together the nodes according to a given equivalence relation ≡. The edges are modified accordingly, so that multiple edges labelled the same between two nodes are eliminated. The quotient is denoted G| ≡ .

Inspired by the discussion of [START_REF] Allauzen | Factor oracle: a new structure for pattern matching[END_REF][START_REF] Allauzen | Efficient experimental string matching by weak factor recognition[END_REF] on the properties the factor oracle should have, we introduce the notion of oracle for the set of factors of a string w; it is a deterministic automaton which:

(o 1 ) recognizes at least all factors of w; (o 2 ) is acyclic (it recognizes a finite set of strings); (o 3 ) has |w| + 1 states (lowest possible); (o 4 ) has linearly many edges (independent of alphabet size); (o 5 ) for each node, all incoming edges have the same label (for efficient implementation).

The criteria (o 1 )-(o 4 ) appear in [START_REF] Allauzen | Factor oracle: a new structure for pattern matching[END_REF][START_REF] Allauzen | Efficient experimental string matching by weak factor recognition[END_REF]; (o 5 ) is new but nevertheless satisfied by the factor oracle; it is very important for implementation because it makes the memorization of the edge labels unnecessary. Notice the difference between an oracle for the set of factor of a string and the factor oracle of [START_REF] Allauzen | Factor oracle: a new structure for pattern matching[END_REF][START_REF] Allauzen | Efficient experimental string matching by weak factor recognition[END_REF]. As we shall work with both automata and trees, we shall simply call them all graphs.

Ukkonen's algorithm for tries

The trie of a string w ∈ A * , denoted Trie(w), is the tree containing all factors of w. Formally, it is a directed graph having as nodes the factors of w and (labelled) edges u a -→ ua, where u, ua ∈ Fact(w), a ∈ A. Each factor is the label of a path starting from the root. See Fig. 1 for an example. Whenever we discuss tries, we shall identify each node with the corresponding path from the root.

The trie is, in some sense, the most basic data structure for strings as most of the other ones -suffix trees, DAWGs, suffix automata -can be obtained from it.

As we show below, the factor oracle can also be obtained from it.

Ukkonen [START_REF] Ukkonen | Constructing suffix trees on-line in linear time[END_REF] gave a linear-time on-line algorithm for constructing suffix trees which are tries with all chains (paths of nodes of outdegree 1) compacted. However, his construction works also for the simpler case of tries. We describe it below as it will be useful in constructing a number of oracles from the obtained trie.

We shall need suffix links, which are links from a node u to suf(u); we shall represent them as dotted arrows; the regular edges are represented as solid arrows. The suffix path from a node u is: u, suf(u), suf 2 (u), . . . , continuing as long as the suffix links are defined; we shall denote it by suf * (u).

The algorithm works sequentially, considering the letters of w one at a time. To add one letter a, we start from the deepest node in the current trie and follow the suffix links adding new a-sons with their suffix links; this is done until one node having an a-son is found or the value of the suffix link becomes nil; see [START_REF] Crochemore | Automata for matching patterns[END_REF] for details.

Important for us later will be the time each node has been created, that is, the index of the letter in the string which caused the addition of that node. This will be denoted, for a node u, by time(u); we shall sometimes write the time as a subscript to the label of the node: u time(u) .

Here is the pseudocode for Ukkonen's algorithm. We also compute the time values and some S ′ -links which will be discussed later.

Ukkonen trie(w) -given a string

w = w[1]w[2] • • • w[n], w[i] ∈ A, 1 ≤ i ≤ n; -return Trie(w);
1. construct the two-node Trie(w [START_REF] Allauzen | Factor oracle: a new structure for pattern matching[END_REF]) with the suffix links 2.

for i from 2 to n do

3. v ← deepest leaf of Trie(w[1..i -1]) 4. k ← min{i | suf i (v) has a w[i]-son or it is nil} 5.
for ℓ from 0 to k -1 do

6. create suf ℓ (v) w[i] -→ x 7. create a suffix link for x [ to w[i]-son of suf ℓ+1 (v) (or ε if nil) ] 8. time(x) ← i 9. if suf k (v) = nil then S ′ (i) ← 0 10. else u ← w[i]-son of suf k-1 (v) 11. S ′ (i) ← time(u)
Notice that, at step 7, the w

[i]-son of suf ℓ+1 (v) is created if it does not exist.
The trie obtained for the string baababbabc is shown in Fig. 1. The string has been chosen to show the most important aspects of our constructions. Setting, by convention, S ′ (0) = -1, the values of S ′ for the example in Fig. 1 are: i 0 1 2 3 4 5 6 7 8 9 10 S ′ (i) -1 0 0 2 1 2 4 1 2 6 0

The following remarks about Ukkonen's trie construction algorithm are useful. Remark 1. If v is the deepest node in the trie with time(v) = i, then all nodes in the trie with time equal to i are found on the suffix path suf * (v). The S ′ -link S ′ (i), for i > 0, is the first node on the suffix path which has a time different from i (or 0 if such a node does not exist).

Remark 2. Notice that, if u with time(u) = j is a node on the suffix path suf * (v), then not all nodes with time equal to j need to be on the suffix path suf * (v). In our example we have the suffix path (the subscripts show the time values): baa 3 , aa 3 , a 2 , but the node ba 2 is not on the suffix path of baa. The shallowest (closest to root) node with time value j must be on suf * (v). This gives also that u ∈ suf * (v) implies time(u) ∈ S ′ * (time(v)), but the converse need not be true. (Here S ′ * (i) is the S ′path of i, that is, i, S ′ (i), S ′ 2 (i), . . ..)

A simple algorithm for the factor oracle

We recall in this section the sequential algorithm of Allauzen, Crochemore, and Raffinot (ACR, for short) for constructing factor oracles. However, we shall not assume we know that the obtained graph is the factor oracle. We shall show later that the same object can be obtained from the trie we described before and the most important properties we need about the factor oracle will follow from there.

ACR factor oracle(w)

-given a string w = w[1]w[2] • • • w[n], w[i] ∈ A, 1 ≤ i ≤ n; -return Factor Oracle(w); 1. S(0) ← -1 2.
for i from 1 to n do

3. create i -1 w[i] -→ i 4.
ℓ ← S(i -1) 5.

while (ℓ = -1) and (ℓ has no w[i]-son) do

6. create ℓ w[i] -→ i 7. ℓ ← S(ℓ) 8. if ℓ = -1 then S(i) ← 0 9. else S(i) ← the w[i]-son of ℓ
The factor oracle for the string baababbabc is shown in Fig. 2. Again, regular edges are solid arrows whereas the S-links are dotted. Notice the string baabc which is recognized but is not a factor. The S-links for the example are: We notice first that it is nondeterministic; the node 2 has two b-sons. We make it deterministic in the following way: eliminate any edge i a -→ j whenever we can We prove below that the trie oracle is an oracle for Fact(w). The trie oracle is deterministic, acyclic, has |w| + 1 states, and for each node all incoming edges are labelled the same. We prove next that it recognizes at least all factors of w. The next lemma concerns Trie | time and is useful for our purpose.

Lemma 3. In Trie(w)| time , if j ∈ S ′ * (i), then L(i) ⊆ L(j).
Proof. By induction on i from |w| to 1. For i = |w|, we have L(i) = {ε} and the property holds. Assume it true for i + 1, i + 2, . . . , |w| and prove it for i. For any edge i a -→ i ′ , there exists v a -→ va in Trie(w) with time(v) = i and time(va) = i ′ . We can also find a node u ∈ suf * (v) such that time(u) = j and there exists an edge u a -→ ua; we can take for u the shallowest node with time value j. Now ua ∈ suf * (va) and if we put j ′ = time(ua), then j ′ ∈ S ′ * (i ′ ). By the inductive hypothesis, L(i ′ ) ⊆ L(j ′ ). As this holds for every a-son of i, the claim follows. -→ i + 1 and (type 2) i -→ j, with j = i + 1; for Trie(w) we consider the time values of the ends of an edge. There are |w| edges of type 1 in Trie(w)| time so we need to count the other ones.

In Trie(w), each internal node has exactly one outgoing edge of type 1. Therefore, the number of edges of type 1 is the same as the number of internal nodes. The total number of edges equals the number of nodes minus one (it is a tree). Therefore, the number of edges of type 2 is the number of leaves minus one. But the number of leaves is at most the number of nonempty suffixes of w, that is, |w|. So, there are at most |w| -1 edges of type 2. The claim follows.

Note that this lemma also applies to Trie Oracle(w). Corollary 6. For any w, the set of strings recognized by Trie Oracle(w) is closed under taking factors.

Proof. The sequence of S ′ -links starting from any node of Trie Oracle(w) ends in the initial node 0. Therefore, Lemma 3 implies that any string recognized starting from some i is also recognized starting from 0.

The following proposition follows from the above results. Proposition 7. For any w, Trie Oracle(w) is an oracle for Fact(w).

The factor oracle from the trie oracle

We show in this section how to obtain the factor oracle from the trie oracle by removing certain edges. The differences between the two graphs in Figs. 2 and4 are shown in bold in the latter. The factor oracle recognizes strictly less strings than the trie oracle in this case; for instance, baababc is recognized by the latter but not by the former. Notice that we do not attempt to find a better algorithm for computing the factor oracle (the simplicity of the one in [START_REF] Allauzen | Factor oracle: a new structure for pattern matching[END_REF][START_REF] Allauzen | Efficient experimental string matching by weak factor recognition[END_REF] we presented above seems almost impossible to beat) but to understand its tricky structure and properties. Here is the result. Theorem 8. For any string w, we have (i) for any i there is e i ≥ 1 such that S ′ ei (i) = S(i);

(ii) Factor Oracle(w) is obtained from Trie Oracle(w) by removing, for all i with e i ≥ 2, all edges S ′ k (i)

w[i+1] -→ i + 1, 1 ≤ k ≤ e i -1.
Proof. We prove that the two assertions hold for any prefix of length n of w by induction on n. The assertions are clear for n = 1. We assume they hold for n and prove them for n + 1. Denote w[n + 1] = a and consider the path of S-links in Factor Oracle(w[1..n]) starting from n and ending in the first node which has an a-son:

n 0 = n i0 = n, n i1 = S(n), n i2 = S 2 (n), . . . , n i k = S k (n) , (4)
for some 0

= i 0 < i 1 < i 2 < • • • < i k ; that is, all n i ℓ , 0 ≤ ℓ ≤ k -1 do not have an a-son but n i k has one, say m.
If there is no node with an a-son on this path, then we set m = 0. In our example in Fig. 2, the sequence (4) for n = 5 is 5, 2 (m = 4) and for n = 9 it is 9, 4, 1, 0 (m = 0). The steps 3-7 in the algorithm ACR factor oracle(w) will create the node n + 1 and edges n i ℓ a -→ n + 1, 0 ≤ ℓ ≤ k -1 and then, at step 9, S(n + 1) gets the value m.

On the other hand, the inductive hypothesis says that in Trie(w[1.

.n]) there is a path of suffix links starting from the deepest node such that the time values of the nodes on this path look like this: n 0 , . . . , n 0 , n 1 , . . . , n 1 , n 2 , . . . , n 2 , . . . , n i k , . . . , n i k ,

where the last n i k corresponds to the shallowest node with that time value. It will have an a-son or else it is the root. Each sequence of n i , n i , . . . , n i could actually contain a single n i . We have also S ′ (n i ) = n i+1 , for all 0 ≤ i ≤ i k -1. a In our example in Fig. 1, the sequence (5) for n = 5 is 5, 5, 5, 2, 2 corresponding to the nodes baaba 5 , aaba 5 , aba 5 , ba 2 , a 2 ; the node a has a b-son (w[4] = b) and time(ab) = 4 = m; for n = 9 we have the sequence 9, 9, 9, 9, 9, 9, 6, 4, 1, 0 corresponding to the nodes baababbab 9 , aababbab 9 , ababbab 9 , babbab 9 , abbab 9 , bbab 9 , bab 6 , ab 4 , b 1 , ε 0 ; no node has a c-son. Notice the value 6 which does not appear in [START_REF] Blumer | The smallest automaton recignizing the subwords of a text[END_REF]. Also, there are other nodes with time values 6 and 4 which do not appear on this path. The steps 5-7 in the algorithm Ukkonen trie(w) will create a-sons with time value n + 1 for all nodes corresponding to the time values in (5) which do not have one. For each n i ℓ , the nodes with the time value n i ℓ will be merged in Trie(w[1..n + 1])| time into one, so we obtain the same edges as those created in Factor Oracle(w[1..n + 1]). For each n i which is not among the n i ℓ s, the edges added will be removed by (ii) in the statement. This is the case for n = 9 in our example: the edge 6 c -→ 10 will be removed. Lastly, if there are any n i k s in (5) without a As the reader may have noticed, there is a relation between i ℓ s and the exponents e i s in the statement:

S ′ en i ℓ (n i ℓ ) = n i ℓ+1 , which means i ℓ = en i 0 + en i 1 + • • • + en i ℓ-1
but we don't need these exact values of i ℓ s. About (i), if m = 0, then S ′ (n+1) = 0 = S(n+1). Assume m = 0 and denote the node corresponding to the last n i k in (5) by u. We have then, by Remark 2 above, that ua ∈ suf * (w[1..n + 1]) which gives m = time(ua) ∈ S ′ * (time(w[1..n + 1])) = S ′ * (n + 1). In our example, for n = 9, we have S ′ (9) = 6 but S ′ 2 (9) = 4 = S(9).

Oracles from the suffix and the factor automata

Two other oracles for Fact(w) can be obtained naturally from the suffix and the factor automata by merging the states that were split during construction. We recall briefly the definition and the construction of the suffix automaton. For more details we refer to [START_REF] Crochemore | Automata for matching patterns[END_REF].

The suffix automaton of a string w, denoted SA(w), is the minimal deterministic automaton (not necessarily complete) that recognizes the set of suffixes of w, that is, Suff(w). Its states are therefore classes of the right syntactic congruence ≡ Suff(w) . The suffix automaton was introduced in [START_REF] Blumer | The smallest automaton recignizing the subwords of a text[END_REF].

In the (on-line) construction algorithm of SA(w), it is important to see how the syntactic congruence changes from a prefix x of w to the next one, say xa, where a is a letter. Let z be the longest suffix of xa that occurs in x and let z ′ be the longest string in the same ≡ Suff(x) -class as z. The classes of ≡ Suff(xa) are the classes of ≡ Suff(x) with two modifications:

-only when z = z ′ , the ≡ Suff(x) -class of z and z ′ is split into two ≡ Suff(xa)classes: one containing the strings of the same length as z or shorter, the other containing the remaining ones (including z ′ ); -a new class is added, that is, the ≡ Suff(xa) -class of the whole new string xa.

Define the suffix function s w : Fact(w) -→ Fact(w) by s w (v) = the longest u ∈ Suff(v) such that u ≡ Suff(w) v. The function s w introduces the s-links b among the states of the suffix automaton. The suffix automaton for our running example is shown in Fig. 5 where the dotted lines are the s-links.

In terms of the automaton, the splitting of the syntactic congruence classes explained above translates into splitting of states. Preserving the above notation, when a new state is added for the prefix xa, then we have s w (xa) = z and if z = z ′ , then the state recognizing both z and z ′ in SA(x) needs to be split in SA(xa) into one state recognizing z and the shorter strings and another recognizing the ones longer than z, including z ′ . This is the case, for instance, in Fig. 5, when state number 9, corresponding to the prefix xa = baababbab (of length 9) is added. In this case we have z = bab is the longest suffix of xa that appears also in x, but z ′ = baabab. Therefore, state 6 is split into 6 and 6 ′ .

An oracle for Fact(w) can be obtained from the suffix automaton by merging together the states that were split during the algorithm constructing the suffix automaton and then making the result deterministic, as we did with Trie(w)| time ; denote the new oracle SA Oracle(w). We prove that SA Oracle(w) is isomorphic with Factor Oracle(w). What we actually show is that the result of merging the states of SA(w) is isomorphic with Trie(w)| time .

An equivalence can be defined in an obvious way from the splitting of states. There is no need to be very formal in that respect. Assume the states in the same class are denoted i, i ′ , i ′′ , . . . , i (j) , . . .. Because SA(w) can be obtained from Trie(w) by merging together isomorphic subtrees, it is enough to prove that all strings recognized at state i (j) by SA(w) have time equal to i. Assume xa is the prefix of length i of w. When the state i is added to the automaton, the strings recognized at i are precisely the suffixes of xa that did not appear so far (as factors of x). That means, suffixes strictly longer than z. But then i is also the first (leftmost) position where all these strings occur in w, that is, it is exactly the time at which they are considered by Ukkonen's algorithm. Later on, if the state i is split, the strings accepted at i are simply distributed among various i (j) -states, but they all preserve the former time = i. The second oracle for Fact(w) is obtained in the same way from the factor automaton of w, that is, the minimal deterministic automaton the recognizes Fact(w). The factor automaton was introduced in [START_REF] Crochemore | Transducers and repetitions[END_REF]. Its construction is similar to the one of SA(w) and the oracle is again obtained by merging the split states plus determinization. However, the proof that the same oracle is obtained is completely similar. For our running example, baababbabc, the two machines are identical; the last letter c does not appear anywhere else in the string, making the two syntactic congruences ≡ Suff(w) and ≡ Fact(w) equal. If this last introduced oracle is denoted FA Oracle(w), then we proved Theorem 9. For any string w, the oracles Trie Oracle(w), SA Oracle(w) and FA Oracle(w) are isomorphic.

The factor oracle from the trie

We describe two ways of obtaining the factor oracle directly from the trie; different from constructing the trie oracle and then performing the eliminations in Theorem 8(ii). Both constructions here are similar to the one presented in Section 6 but they are independent of the factor oracle; in particular, they do not make reference to the S-links.

The first one uses the idea that the edges which the trie oracle has but the factor oracle does not appear from the fact that we may add an a-son to a node v even when there is already a node with the same time value as v which has an a-son.

In our example, this happens when adding the edge ba 2 b -→ bab 6 when there is already a 2 b -→ ab 4 (subscripts show the time). Modifying Ukkonen's algorithm for tries so that such edges are not added would produce a graph whose quotient with respect to the time values produces precisely the factor oracle. For our example this new graph would look like the trie in Fig. 1 with the subtree rooted at bab removed. The new S ′ -links would be the same as the S-links in the factor oracle. However, the new suffix links would not be true suffix links but powers of those. Precisely, the new suffix link for a node u would link to the longest suffix of u that exists in the new graph. For instance, in our example, we would have the new (pseudo)suffix link of bbab pointing to ab = suf 2 (bbab) as the suffix bab is no longer in the new graph.

A better way to modify Ukkonen's algorithm is to add an a-son to a node v even if there exists another, say u, with the same time value and that has an a-son but the (new) time value of v will not be the index of the current letter in w but time(ua). This new version of the algorithm, say Ukkonen trie 2(w), would have line 8 replaced by the following pseudocode (for clarity, denote the new time values by time 2 and the new S ′ -links by S ′′ ):

8. time 2(x) ← i 8.1. if suf k (v) = nil then 8.2. t ← time 2(suf k (v)); t ′ ← time 2(suf k (v)w[i]); ℓ ← k -1 8.3. while time 2(suf ℓ (v)) = t do 8.4. time 2(suf ℓ (v)w[i]) ← t ′ ; ℓ ← ℓ -1
Denote the graph constructed by this algorithm Trie 2(w) and let Trie Oracle 2(w) be the quotient Trie 2(w)| time 2 . From the construction it should be clear that a deterministic automaton is obtained. Remarks 1 and 2 hold as well for Trie 2(w) with one exception. Not all nodes with a given time 2 are found on the suffix path from the deepest node with that time 2 value. The nodes with the same time 2 form a tree with the shallowest node as root. In our example, this happens for the nodes with time 2 value 4; the root is ab 4 .

Lemma 19. Let v be a factor of w recognized by Factor Oracle(w) in i. Then any suffix of v is recognized in j ≤ i.

Proof. The suffix of v is in Trie 2(w) on the suffix path of v and therefore has a lower, or equal, time 2 value.

Lemma 20. Factor Oracle(w) has at most 2|w| -1 edges.

Proof. This follows from Lemma 5. Denote repet(w, i) the longest suffix of w[1..i] that appears at least twice in w[1..i].

Lemma 21. The reading of repet(w, i) in Factor Oracle(w) ends in S(i).

Proof. Starting from the deepest node of Trie 2(w) with time 2 value i; it corresponds to the node w[1..i]. Moving up its suffix path, we encounter shorter suffixes until one which is already in Trie 2(w) is found. That node has time 2 value S(i) and its label is precisely repet(w, i).

Discussion and open problems

Our framework for discussing oracles for the set of factors of a string is provided by the following result. Remark 23. Notice that, in particular, for any oracle O, Trie(w)| ≡O is deterministic. Also, all edges in O which are not in Trie(w)| ≡O can be eliminated and it still remains an oracle. Therefore, comparing oracles for the set of factors reduces to comparing quotients of the trie.

There exist particular examples, such as the string abcacdace from [START_REF] Cleophas | Constructing factor oracles[END_REF], in which the factor oracle is not the best possible oracle. The smaller oracle for the string abcacdace has one transition less than the factor oracle. However it accepts 16 errors compared to 13 errors accepted by the factor oracle. There are strings, such as abcacdaceacf for which there exists a smaller oracle which makes also less errors; in this case 33 errors whereas the factor oracle makes 39; see Figs. 6 and7. Finally, we recall briefly the most important open problems about the factor oracle; they apply to all oracles for the set of factors of a string:

(1) Are factor oracle based string matching algorithms optimal on average, as conjectured by [START_REF] Allauzen | Factor oracle: a new structure for pattern matching[END_REF][START_REF] Allauzen | Efficient experimental string matching by weak factor recognition[END_REF]? (2) What is the number of errors (maximal and average), that is, nonfactors that are recognized by the factor oracle? Examples were given in [START_REF] Mancheron | Combinatorial characterization of the language recognized by factor and suffix oracles[END_REF] where this number is exponential but they are over an unbounded alphabet. There are examples over a binary alphabet where it is still superpolynomial: for the string abab 2 ab 3 . . . ab n , the number of errors is greater than n!. (3) What is the average number of external transitions for the factor oracle or, put otherwise, what is its average size? (4) Is there a simple strategy for building better oracles? Our framework of quotients of the trie allows comparing them. (5) Characterize the set recognized by the factor oracle; not in terms of the factor oracle itself, like in [START_REF] Mancheron | Combinatorial characterization of the language recognized by factor and suffix oracles[END_REF].

Fig. 1 .

 1 Fig. 1. The trie built by the algorithm Ukkonen trie for the string baababbabc.

Fig. 2 .

 2 Fig. 2. Factor Oracle(baababbabc)

Fig. 3 .Fig. 4 .

 34 Fig. 3. Trie(baababbabc)| time

Corollary 4 .Lemma 5 .

 45 For any w, Trie Oracle(w) recognizes at least all factors of w. Proof. It is clear that Trie(w)| time recognizes at least all factors of w. But whenever an edge j a -→ i is removed to create Trie Oracle(w), there is another edge j a -→ ℓ, with ℓ < i. In such a case we have ℓ ∈ S ′ * (i) and Lemma 3 says that eliminating the former edge does not affect the set of recognized strings. What is left to show is property (o 4 ) in the definition of an oracle. For any w, Trie(w)| time has at most 2|w| -1 edges. Proof. There are two types of edges in Trie(w)| time and Trie(w): (type 1) i w[i]

  a-sons, the edges they get are removed when constructing Trie Oracle(w[1..n + 1]) from Trie(w[1..n+1])| time . This is the case in our example for n = 5: the edge 2 b -→ 6 is removed. In all cases Factor Oracle(w[1..n + 1]) is obtained as claimed by (ii).

Fig. 5 .

 5 Fig. 5. SA(baababbabc)

Proposition 22 .

 22 Any oracle for the set of factors of a string w contains a quotient of Trie(w) as a subgraph. Proof. Let O be an oracle and define a relation on the nodes of Trie(w) by u ≡ O v iff the paths labeled u and v in O end in the same node . We claim that O must contain as a subgraph the quotient Trie(w)| ≡O . First, it is clear that ≡ O is an equivalence relation with |w| + 1 classes. No two prefixes of w are in the same ≡ O -class and denote the ≡ O -class of the prefix of length i by i. Therefore, Trie(w)| ≡O has the nodes 0, 1, . . . , n. Consider an edge i a -→ j of Trie(w)| ≡O . There must be then an edge u a -→ ua in Trie(w) such that u ≡ O w[1..i] and ua ≡ O w[1..j]. Therefore, reading u in O from 0 leads to i whereas reading ua from 0 leads to j. As O is deterministic, there must be an edge i a -→ j in O, proving the claim.

  d

Fig. 6 .Fig. 7 .

 67 Fig. 6. Factor Oracle(abcacdaceacf )

M. Crochemore, L. Ilie, and E. Seid-Hilmi

b Our suffix function s is called suffix link in[START_REF] Crochemore | Automata for matching patterns[END_REF] but we already used that term with a different meaning.

supported in part by CNRS. supported in part by NSERC and CNRS.

The results in Lemma 3, Corollaries 4 and 6 and Proposition 7 hold also for Trie Oracle 2(w). The proof of the next lemma is similar to the one of Lemma 3.

Lemma 10. In Trie Oracle 2(w), if j ∈ S ′′ * (i), then L(i) ⊆ L(j).

Lemma 11. For any w, we have: (i) Trie Oracle 2(w) recognizes at least all factors of w; (ii) the set of strings recognized by Trie Oracle 2(w) is closed under taking factors.

Proof. For (i) there is nothing to prove as Trie Oracle 2(w) is obtained by merging Trie 2(w). Lemma 10 implies (ii).

Proposition 12. For any w, Trie Oracle 2(w) is an oracle for Fact(w).

Proof. We have that Trie Oracle 2(w) fulfils all five conditions in the definition of an oracle: (o 1 ) comes from (i) of Lemma 11, (o 2 ), (o 3 ), and (o 5 ) are clear, and (o 4 ) follows from Lemma 5.

For our string baababbabc, the differences between Trie 2 and Trie are: (i) time 2(bab) = 4 = 6 = time(bab) and (ii) S ′′ (9) = 4 = 6 = S ′ (9). Therefore, the two graphs Trie Oracle 2(baababbabc) and Factor Oracle(baababbabc) are identical. The next theorem says that this is always the case.

Theorem 13. For any string w, we have (i) for any i, S ′′ (i) = S(i); (ii) Factor Oracle(w) and Trie Oracle 2(w) are the same.

Proof. The proof is similar to the one of Theorem 8 but simpler. We show the two assertions to be true for each prefix of length n of w by induction on n. They hold for n = 1. Let us assume they are true for n and prove them for n + 1. Denote w[n + 1] = a. The path (4) of S-links from n to the first node with an a-son is here

Denote by m the a-son of n k ; if there is no node with an a-son on this path, then we set m = 0. The steps 3-7 in the algorithm ACR factor oracle(w)

The corresponding path (5) of time 2 values starting from the deepest node in Trie 2(w[1..n]) is n 0 , . . . , n 0 , n 1 , . . . , n 1 , n 2 , . . . , n 2 , . . . , n k , . . . , n k .

(

The last n k corresponds to the shallowest node with that time value. It will have an a-son or else it is the root. Also, S ′′ (n i ) = n i+1 , for all 0 ≤ i ≤ n k-1 .

The steps 5-7 in the algorithm Ukkonen trie 2(w) will create a-sons for all nodes corresponding to the time values in (5) which do not have one. Moreover, if there is more than one n k in [START_REF] Crochemore | Automata for matching patterns[END_REF], then all the a-sons of such nodes will have time 2 value m. This can happen only when m = 0.

It is clear that Trie 2(w[1..n + 1])| time 2 produces Factor Oracle[1..n + 1]) and so (ii) is proved.

For (i), we have S ′′ (n + 1) = m = S(n + 1).

A direct construction of the factor oracle from the trie has been shown in [START_REF] Cleophas | Constructing factor oracles[END_REF]. However the algorithm presented there is less eficient than our method.

Properties of the factor oracle

The properties of the factor oracle from [START_REF] Allauzen | Factor oracle: a new structure for pattern matching[END_REF][START_REF] Allauzen | Efficient experimental string matching by weak factor recognition[END_REF] can be very easily deduced using Theorem 13. In Proposition 12 we proved that Factor Oracle(w) is an oracle for the set of factors of w. Also Lemma 11 shows that the set of strings recognized by Factor Oracle(w) is closed under taking factors.

Denote, for u factor of w, poccur(u, w) = min{|z| | z = xu, w = zy}.

Lemma 14. The shortest string recognized by Factor Oracle(w) in i is a factor of w and is unique.

Proof. This is the string labelling the shallowest (closest to root) node with time 2 value i in Trie 2(w).

Denote the string in the above lemma by min(i). The next property is also clear.

Lemma 15. poccur(min(i), w) = i.

Proof. We know that poccur(min(i), w) = time 2(min(i)) = i.

Lemma 16. min(i) is a suffix of any string recognized by Factor Oracle(w) in i.

Proof. The shallowest node with time 2 value i, corresponding to min(i), is on the suffix path of any node with time 2 i.

Lemma 17. Any factor u of w is recognized by Factor Oracle(w) in j ≤ poccur(u, w).

Proof. We have in Trie 2(w), time 2(u) ≤ poccur(u, w).

Lemma 18. Any path in Factor Oracle(w) whose label ends with min(i) leads to j ≥ i.

Proof. Such a path in Trie 2(w) leads to a node v such that the shallowest node of time 2 value i is on v's suffix path. It follows that j = time 2(v) ≥ i.


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

Lucian Ilie
email: ilie@csd.uwo.ca

Computing Longest Previous Factor in linear time and applications ⋆

Keywords: algorithms design, strings, suffix array, longest common prefix, longest previous factor, Lempel-Ziv factorization, repetitions, runs MSC: 68W05, 68W40, 68R15

We give two optimal linear-time algorithms for computing the Longest Previous Factor (LPF) array corresponding to a string w. For any position i in w, LPF [i] gives the length of the longest factor of w starting at position i that occurs previously in w. Several properties and applications of LPF are investigated. They include computing the Lempel-Ziv factorization of a string and detecting all repetitions (runs) in a string in linear time independently of the integer alphabet size.

Introduction

Given a string w, we introduce the Longest Previous Factor (LPF) array defined as follows. For any position i in w, LPF [i] gives the length of the longest factor of w starting at position i that occurs previously in w. Formally, if w[i] denotes the ith letter of w and w[i . . j] is the factor w[i]w[i + 1] . . . w[j], then

LPF[i] = max {ℓ | w[i..i + ℓ -1] is a factor of w[0..i + ℓ -2]} ∪ {0} .
We give two linear-time (optimal) algorithms for computing LPF using suffix arrays. The first uses no additional information whereas the second uses the longest common prefix array which is often part of the suffix array data structure. Previously such algorithms involved computing the suffix trees, which are more complex and take a lot of space. Also, a logarithmic factor of the size of the alphabet often appears in the complexity. Our algorithms use suffix arrays, are much simpler, and their complexity is alphabet independent.

One important application is computing the Lempel-Ziv factorization [START_REF] Lempel | On the complexity of finite sequences[END_REF]. Recently [START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF] gave a suffix-array-based algorithm for computing Lempel-Ziv factorization. However, their algorithm is essentially a simulation of the suffix tree using the suffix array. The description in [START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF] is very brief but it seems that their approach can be used to achieve similar goals with ours, nevertheless in a significantly more complicated way.

Simultaneously and independently of our work, [START_REF] Chen | Fast and practical algorithms for computing all runs in a string[END_REF] gave an algorithm that is similar with our second one. Our first algorithm is more general and our approach for the second gives a clearer explanation as well as more insight into the structure of LPF.

Suffix arrays

We recall in this section briefly the notions of suffix array and longest common prefix. Consider a string w = w[0 . . n -1] of length n over an alphabet A that is an integer interval of size no more than n c , for some constant c. The suffix of w starting at position i is denoted by

suf i = w[i..n -1], for 0 ≤ i ≤ n -1.
The suffix array of w, [START_REF] Manber | Suffix arrays: a new method for on-line search[END_REF], denoted SA, gives the suffixes of w sorted ascendingly in lexicographical order, that is,

suf SA[0] < suf SA[1] < • • • < suf SA[n-1]
. The suffix array of the string abbaabbbaaabab is shown in the second column of Fig. 1.

Often the suffix array is used in combination with another array, the Longest Common Prefix (LCP) which gives the length of the longest common prefix between consecutive suffixes of SA, that is, LCP[i] is the length of the longest common prefix of suf SA[i] and suf SA[i-1] ; see the third column of Fig. 1 for an example.

i SA[i] LCP[i] suf SA[i] prev < [SA[i]] prev > [SA[i]] LPF[SA[i]] PrevOcc[SA[i]] 0 8 0 aaabab -1 3

A direct algorithm

We give first a direct algorithm for computing LPF from the suffix array. We compute also, for each i, a position PrevOcc[i] < i where the longest previous factor at i occurs.1 (If LPF[i] = 0, then PrevOcc[i] = -1.) Both arrays for our example are shown in the last two columns in Fig. 1. The idea of the algorithm is as follows. For any position i, the longest factor starting at i that occurs also to the left of i in w is the longest common prefix between the suffix suf i and the suffixes starting to the left of i in w, that is, suf j , 0 ≤ j ≤ i -1. However, given SA, we need only consider those which are closest to suf i in SA. We shall therefore compute, for each i, the closest positions in SA that are smaller than i; in most cases there will be two such positions, one before and one after i in SA. Denote them by prev < [i] and prev > [i], respectively. If one of them does not exists, then we assign the value -1; see columns 5 and 6 in Fig. 1. Rephrasing the above, LPF[i] is obtained as the length of the longest common prefix between suf i and either suf prev < [i] or suf prev > [i] , whichever is longer.

After prev < and prev > are found, LPF is computed for all values of i in increasing order, using the property that

LPF[i] ≥ LPF[i -1] -1. Thus, we already know that w[i . . i + LPF[i -1] -2]
occurred to the left of i and need only try to extend it. A problem appears because we do not know whether we should compare suf i to suf prev < [i] or suf prev > [i] . We shall therefore compute two arrays, LPF < [0 . . n -1] and LPF > [0 . . n -1]; they have the same meaning as LPF except that they consider only positions corresponding to suffixes lexicographically smaller, resp. larger, than suf i . Formally, we have

LPF < [i] = max {j | ∃k < i, w[i . . i+j-1] = w[k . . k+j-1] and suf k < suf i }∪{0}
and LPF > [i] is defined identically except for the last condition which becomes suf k > suf i . Consider one of them, say LPF < . We still have that

LPF < [i] ≥ LPF < [i -1] -1. This is because, if w[i -1] = w[k -1]
, then the order between suf i and suf k is the same as between suf i-1 and suf k-1 . That means, we already know that suf i and suf prev < [i] have a common prefix of length LPF < [i -1] -1 and we check only the following letters. This explains why our algorithm runs in O(n) time. Finally, LPF[i] is the maximum between LPF < [i] and LPF > [i]. The algorithm is given in Fig. 2.

Computing the arrays prev < and prev > is a matter of manipulating data structures. We can construct a doubly linked list with the elements of SA and two extra elements at the beginning and at the end with value -1, for the case prev < [i] or prev > [i] do not exist. The values are computed in decreasing order of i, from n to 0, and each i is removed once the values for i have been computed. When i is considered, it is the largest left in the list and therefore the one before and the one after in the list will give the values of prev < [i] and prev > [i]. In fact pointers can be avoided, and arrays used instead, because after the doubly linked list is created only deletions are performed. The details are omitted.

Compute LPF(w, prev < , prev > ) 1. LPF[0] ← LPF<[0] ← LPF>[0] ← 0 2. for i from 1 to n -1 do 3. j ← max(LPF<[i -1] -1, 0); k ← max(LPF>[i -1] -1, 0) 4. if (prev < [i] = -1) then LPF<[i] ← 0 5. else while (w[i + j] = w[prev < [i] + j]) do j ← j + 1 6. LPF<[i] ← j 7. if (prev > [i] = -1) then LPF>[i] ← 0 8. else while (w[i + k] = w[prev > [i] + k]) do k ← k + 1 9. LPF>[i] ← k 10. LPF[i] ← max(LPF<[i], LPF>[i]) 11. if (LPF[i] = 0) then PrevOcc[i] ← -1 12. else if (LPF<[i] > LPF>[i]) then PrevOcc[i] ← prev < [i] 13.
else PrevOcc[i] ← prev > [i] 14. return LPF and PrevOcc Fig. 2. Algorithm for computing LPF directly from the SA via arrays prev < and prev > .

It should be clear from the above discussion that the arrays prev < and prev > can be computed in time O(n). The algorithm Compute LPF uses O(n) space. Using the fact that the suffix array of a string of length n over an integer alphabet can be computed in O(n) time by any of the algorithms in [START_REF] Farach | Optimal suffix tree construction with large alphabets[END_REF][START_REF] Kärkkäinen | Simple linear work suffix array construction[END_REF][START_REF] Kim | Constructing suffix arrays in linear time[END_REF][START_REF] Ko | Space efficient linear time construction of suffix arrays[END_REF], we obtain: Theorem 1. Given a string of length n over an integer alphabet, the LPF and PrevOcc arrays can be computed in time and space O(n).

An algorithm using LCP

Our second algorithm for computing LPF uses the LCP array. Its advantage over the previous algorithm is that it processes the suffix array in one pass and requires less memory space. The idea is similar to the one above. Assuming we know the longest common prefixes between suf i and either suf prev

< [i] or suf prev > [i] ,
it is enough to take the maximum of the two.

Using this idea, we give a space-efficient algorithm for computing LPF. For a better understanding, it is useful to arrange the SA and LCP arrays in a graph. The vertices are labelled by the SA values and the edges by the LCP values. The vertices are arranged in the left-to-right order corresponding to their order in SA and are placed at a height corresponding to their starting position in the string. In other words, if SA[i] = j, then the vertex labelled j is plotted with abscissa i and ordinate j. An example if shown by the graph in Fig. 3(i) consisting of the solid edges only. Now consider the vertices in decreasing order of their labels, that is, vertices that are highest in the graph ("peaks") are considered first. For vertex 13, the two adjacent edges are labelled 0 and 1, corresponding to the longest common prefixes of suf 13 with suf prev < [i] = suf 4 and suf prev > [i] = suf 7 , respectively. Therefore, the maximum of the two gives LPF[13] = 1. On the other hand, the minimum of the two gives the longest common prefix of suf 4 and suf 7 ; we remove the vertex 13 and add a (dotted) edge between 4 and 7, labelled 0. Notice that prev < [7] = 4 and prev > [7] = 2, so this property is an invariant of the graph. Next we consider the vertex 12 and so on. Fig. 3(ii) shows the graph after having considered the vertices 13, 12, and 11.

It is clear that we need not consider the vertices in this order. For instance, we can compute LPF [START_REF] Duval | Linear-Time Computation of Local Periods[END_REF] right away. Precisely, any vertex which is a "peak" in our graph can have its LPF value computed. In the algorithm in Fig. 4 we consider the vertices in the order they appear in the SA (that is, left to right in the graph) and use a stack to store unprocessed vertices. The vertices in the stack will be in increasing order from bottom to top. Whenever a vertex with a smaller label than the one on top of the stack is encountered, the top of the stack is processed and popped. For instance, vertex 4 has to wait for 13 and 7 to be processed. In order to process all vertices uniformly, we assume a last (virtual) vertex with label n and height -1. The stack contains pairs of the form (x.len, x.pos), where x.pos is a position (in SA) and x.len stores the longest common prefix between suf x.pos and the suffix corresponding to the node right below x in the stack (or 0 if none). For instance, when the vertex 7 is considered, 13 is processed and removed from the stack. The top of the stack becomes 4 and 7 is then pushed on top of it: top(S ).len ← 0 and top(S ).pos ← 7.

The correctness of the algorithm follows from the above discussion. It runs in O(n) time because each element of SA is pushed only once on to the stack. Also, [START_REF] Kasai | Linear-time longestcommon-prefix computation in suffix arrays and its applications[END_REF] gives a very simple linear time algorithm to compute the LCP array.

Compute LPF using LCP(w, SA, LCP)

1. SA[n] ← -1; LCP[n] ← 0 2. push((0, SA[0]), S ) 3. for i from 1 to n do 4. lcp ← LCP[i] 5.
while (S = ∅) and (SA[i] < top(S ).pos) ¡

6.

LPF[top(S ).pos] ← max(top(S ).len, lcp) 7.

lcp ← min(top(S ).len, lcp) 8.

v ← top(S ) 9.

pop(S ) 10.

if

(LPF[v.pos] = 0) then PrevOcc[v.pos] ← -1 11. else if (v.len > lcp) then PrevOcc[v.pos] ← top(S ).pos 12.
else

PrevOcc[v.pos] ← SA[i] 13.
if (i < n) then push((lcp, SA[i]), S ) 14. return LPF Fig. 4. Algorithm for computing LPF using LCP.

The spaced used by the stack is at most n pairs of integers, which is reached for the string a n-1 b. However, the expected size of the stack is much less.

There is an interesting consequence of the above discussion, namely that the array LPF is a permutation of LCP. This is shown by analyzing the graph in Fig. 3(i). The labels of the solid edges form the LCP array. When removing a "peak" from the graph, the maximum of the two labels of the adjacent edges becomes an LPF value whereas the minimum becomes the label of the newly formed (dotted) edge. Each value will eventually become an LPF value which proves the statement. Proposition 1. LPF is a permutation of LCP.

Remark 1. Note that [START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF] suggests a bottom-up computation of the LPF array on the lcp-interval tree (isomorphic with the suffix tree) and therefore leads to a similar result with ours. However, our approach is much simpler.

Application 1: computing the Lempel-Ziv factorization

The Lempel-Ziv factorization of w [START_REF] Lempel | On the complexity of finite sequences[END_REF] is the decomposition w = u 0 u 1 • • • u k , where each u i (except possibly u k ) is the longest prefix of u i u i+1 • • • u k that has another occurrence to the left in w or a single letter in case this prefix is empty. For our example the Lempel-Ziv factorization is a.b.b.a.abb.baa.ab.ab.

The Lempel-Ziv factorization is a basic and powerful technique for text compression [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF]. It has many variants used in gzip or PKzip software, and more generally in dictionary compression methods.

The Lempel-Ziv factorization is easily computed from LPF. The algorithm is shown in Fig. 5. For the example text abbaabbbaaabab in Fig. 1, the algorithm outputs lz = [0, 1, 2, 3, 4, 7, 10, 12].

Lempel-Ziv factorization(w, LPF)

1. lz[0] ← 0; i ← 0 2. while (lz[i] < n) do 3. lz[i + 1] ← lz[i] + max(1, LPF[lz[i]]) 4.
i ← i + 1 5. return lz Fig. 5. Algorithm for computing Lempel-Ziv factorization using LPF.

Theorem 2. The Lempel-Ziv factorization of a string of length n over an integer alphabet can be computed in O(n) time.

The experimental results of [START_REF] Chen | Fast and practical algorithms for computing all runs in a string[END_REF] may be explained by the fact that suffix-treebased algorithms computing the Lempel-Ziv factorization usually have complexity O(log(|A|)n), where |A| is the cardinality of the alphabet.

Also, note that suffix trees allow online computation of the Lempel-Ziv factorization. However, this comes with the extra log(|A|) factor. It remains open whether true linear-time online computation is possible.

Application 2: computing runs in linear time

Repetitions are a fundamental topic in stringology and appear in many applications such as text algorithms, data compression, or analysis of biological sequences. The simplest repetition is a square ww, where w is any string. A general repetition has the form w e , for any rational exponent e ≥ 2 such that e|w| is an integer; e.g., (aabab) 7 5 = aababaa. Particularly important turned out to be maximal repetitions [START_REF] Main | Detecting lefmost maximal periodicities[END_REF] or runs. A run is an occurrence of a repetition that cannot be extended. As an example, the string aababaabba contains the runs aa at positions 0 and 5, ababa, and bb. Runs allow the encoding of all repetitions in linear space [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF].

An element of the Lempel-Ziv factorization carries information already processed by any online algorithms computing repetitions. Therefore it is not surprising that the Lempel-Ziv factorization plays a central part in the algorithm of [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF] as well as in all efficient computations of repetitions in strings. Their running time is then O(n log(|A|)). Using a suffix array and the algorithms described in previous sections leads to linear-time computations on integer alphabets. This applies to: testing square freeness of a string [START_REF] Crochemore | Transducers and repetitions[END_REF], computing all leftmost maximal periodicites [START_REF] Main | Detecting lefmost maximal periodicities[END_REF], computing all runs [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF], computing of all local periods of a string [START_REF] Duval | Linear-Time Computation of Local Periods[END_REF], and computing all primitively-rooted squares occurring in a string [START_REF] Gusfield | Linear time algorithm for finding and representing all the tandem repeats in a string[END_REF]. In particular, we get: Theorem 3. The runs of a string of length n over an integer alphabet can be computed in O(n) time.

Fig. 3 .

 3 Fig. 3. (i) Solid edges form the graph representing SA and LCP for the text abbaabbbaaabab; dotted edges show the (conceptual) transformation of the graph during the algorithm Compute LPF using LCP. (ii) The graph after the vertices 13, 12, and 11 were considered.

  The arrays SA, LCP, and LPF for the string abbaabbbaaabab.

						2	3
	1	9	2 aabab	8	3	3	3
	2	3	3 aabbbaaabab	-1	0	1	0
	3 12	1 ab	3	10	2	10
	4 10	2 abab	3	0	2	0
	5	0	2 abbaabbbaaabab	-1	-1	0	-1
	6	4	3 abbbaaabab	0	2	3	0
	7 13	0 b	4	7	1	7
	8	7	1 baaabab	4	2	3	2
	9	2	3 baabbbaaabab	0	1	1	1
	10 11	2 bab	2	6	2	2
	11	6	1 bbaaabab	2	1	4	1
	12	1	4 bbaabbbaaabab	0	-1	0	-1
	13	5	2 bbbaaabab	1	-1	2	1
		Fig. 1.

Note that a suffix-tree-based algorithm would compute the leftmost such position in the string whereas our algorithm might produce a different one. For instance, in our example, PrevOcc[START_REF] Ko | Space efficient linear time construction of suffix arrays[END_REF] = 10 but the left most occurrence of ab starts at 0.

Acknowledgements

We warmly thank Bill Smyth and Simon Puglisi for interesting discussions related to the present subject during the "String Masters" meeting held in Hamilton in July 2007.

Also, we would like to thank the anonymous referees for comments that helped improving the presentation.

⋆ This work has been presented at the AutoMathA'07 conference, see [5]. ⋆⋆ Research supported in part by CNRS. ⋆ ⋆ ⋆ Research supported in part by NSERC.