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

Costas S Iliopoulos
email: costas.iliopoulos@kcl.ac.uk

Tomasz Kociumaka
email: [kociumaka@mimuw.edu.pl

Ritu Kundu
email: ritu.kundu@kcl.ac.uk

Solon P Pissis
email: solon.pissis]@kcl.ac.uk

Jakub Radoszewski

Wojciech Rytter
email: rytter@mimuw.edu.pl

Tomasz Waleń
email: walen]@mimuw.edu.pl

Longest common extension queries (LCE queries) and runs are ubiquitous in algorithmic stringology. Linear-time algorithms computing runs and preprocessing for constant-time LCE queries have been known for over a decade. However, these algorithms assume a linearlysortable integer alphabet. A recent breakthrough paper by Bannai et. al. (SODA 2015) showed a link between the two notions: all the runs in a string can be computed via a linear number of LCE queries. The first to consider these problems over a general ordered alphabet was Kosolobov (Inf. Process. Lett., 2016), who presented an O(n(log n) 2/3 )-time algorithm for answering O(n) LCE queries. This result was improved by Gawrychowski et. al. (accepted to CPM 2016) to O(n log log n) time. In this work we note a special non-crossing property of LCE queries asked in the runs computation. We show that any n such non-crossing queries can be answered on-line in O(nα(n)) time, which yields an O(nα(n))time algorithm for computing runs.

Introduction

Runs (also called maximal repetitions) are a fundamental type of repetitions in a string as they represent the structure of all repetitions in a string in a succinct way. A run is an inclusion-maximal periodic factor of a string in which the shortest period repeats at least twice. A crucial property of runs is that their maximal number in a string of length n is O(n). This fact was already observed by Kolpakov and Kucherov [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF][START_REF] Kolpakov | On maximal repetitions in words[END_REF] who conjectured that this number is actually smaller than n, which was known as the runs conjecture. Due to the works of several authors [START_REF] Crochemore | Analysis of maximal repetitions in strings[END_REF][START_REF] Crochemore | Maximal repetitions in strings[END_REF][START_REF] Crochemore | Towards a solution to the "runs" conjecture[END_REF][START_REF] Giraud | Not so many runs in strings[END_REF][START_REF] Puglisi | How many runs can a string contain?[END_REF][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] more precise bounds on the number of runs have been obtained, and finally in a recent breakthrough paper [START_REF] Bannai | The "runs" theorem[END_REF] Bannai et al. proved the runs conjecture, which has since then become the runs theorem (even more recently in [START_REF] Fischer | Beyond the runs theorem[END_REF] the upper bound of 0.957n was shown for binary strings).

Perhaps more important than the combinatorial bounds is the fact that the set of all runs in a string can be computed efficiently. Namely, in the case of a linearly-sortable alphabet Σ (e.g., Σ = {1, . . . , σ} with σ = n O (1) ) a linear-time algorithm based on Lempel-Ziv factorization [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF][START_REF] Kolpakov | On maximal repetitions in words[END_REF] was known for a long time. In the recent papers of Bannai et al. [START_REF] Bannai | The "runs" theorem[END_REF][START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF] it is shown that to compute the set of all runs in a string, it suffices to answer O(n) longest common extension (LCE) queries. An LCE query asks, for a pair of suffixes of a string, for the length of their longest common prefix. In the case of σ = n O (1) such queries can be answered on-line in O(1) time after O(n)-time preprocessing that consists of computing the suffix array with its inverse, the LCP table and a data structure for range minimum queries on the LCP table; see e.g. [START_REF] Crochemore | Algorithms on Strings[END_REF]. The algorithms from [START_REF] Bannai | The "runs" theorem[END_REF][START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF] use (explicitly and implicitly, respectively) an intermediate notion of Lyndon tree (see [START_REF] Barcelo | On the action of the symmetric group on the Free Lie Algebra and the partition lattice[END_REF][START_REF] Hohlweg | Lyndon words, permutations and trees[END_REF]) which can, however, also be computed using LCE queries.

Let T LCE (n) denote the time required to answer on-line n LCE queries in a string. In a very recent line of research, Kosolobov [START_REF] Kosolobov | Computing runs on a general alphabet[END_REF] showed that, for a general ordered alphabet, T LCE (n) = O(n(log n) 2/3 ), which immediately leads to O(n(log n) 2/3 )-time computation of the set of runs in a string. In [START_REF] Gawrychowski | Faster longest common extension queries in strings over general alphabets[END_REF] a faster, O(n log log n)-time algorithm for answering n LCE queries has been presented which automatically leads to O(n log log n)-time computation of runs.

Runs have found a number of algorithmic applications. Knowing the set of runs in a string of length n one can compute in O(n) time all the local periods and the number of all squares, and also in O(n + T LCE (n)) time all distinct squares provided that the suffix array of the string is known [START_REF] Crochemore | Extracting powers and periods in a word from its runs structure[END_REF]. Runs were also used in a recent contribution on efficient answering of internal pattern matching queries and their applications [START_REF] Kociumaka | Internal pattern matching queries in a text and applications[END_REF].

Our Results

We observe that the computation of a Lyndon tree of a string and furthermore the computation of all the runs in a string can be reduced to answering O(n) LCE queries that are non-crossing, i.e., no two queries LCE(i, j) and LCE(i , j ) are asked with i < i < j < j or i < i < j < j. Let T ncLCE (n) denote the time required to answer n such queries on-line in a string of length n over a general ordered alphabet. We show that T ncLCE (n) = O(nα(n)), where α(n) is the inverse Ackermann function. As a consequence, we obtain O(nα(n))time algorithms for computing the Lyndon tree, the set of all runs, the local periods and the number of all squares in a string over a general ordered alphabet.

Our solution relies on a trade-off between two approaches. The results of [START_REF] Gawrychowski | Faster longest common extension queries in strings over general alphabets[END_REF] let us efficiently compute the LCEs if they are short, while LCE queries with similar arguments and a large answer yield structural properties of the string, which we discover and exploit to answer further such queries.

Our approach for answering non-crossing LCE queries is described in three sections: in Section 3 we give an overview of the data structure, in Section 4 we present the details of the implementation, and in Section 5 we analyse the complexity of answering the queries. The applications including runs computation are detailed in Section 6. The appendix contains some supporting examples.

Preliminaries

Strings Let Σ be a finite ordered alphabet of size σ. A string w of length |w| = n is a sequence of letters w [START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF] . . . w[n] from Σ. By w[i, j] we denote the factor of w being a string of the form w Lyndon Words and Trees By ≺=≺ 0 we denote the order on Σ and by ≺ 1 we denote the reverse order on Σ. We extend each of the orders ≺ r for r ∈ {0, 1} to a lexicographical order on strings over Σ. A string w is called an r-Lyndon word if w ≺ r u for every non-empty proper suffix u of w. The standard factorization of an r-Lyndon word w is a pair (u, v) of r-Lyndon words such that w = uv and v is the longest proper suffix of w that is an r-Lyndon word.

[i] . . . w[j]. A factor w[i, j] is called proper if w[i, j] = w. A factor is called a prefix if i = 1 and a suffix if j = n. We say that p is a period of w if w[i] = w[i + p] for all i = 1, . . . , n -p. If p is a period of w, the prefix w[1, p] is
The r-Lyndon tree of an r-Lyndon word w, denoted as LTree r (w), is a rooted full binary tree defined recursively on w[1, n] as follows:

-LTree r (w[i, i]) consists of a single node labeled with [i, i] -if j -i > 1 and (u, v) is the standard factorization of w[i, j], then the root of LTree r (w) is labeled by [i, j],
has left child LTree r (u) and right child LTree r (v).

See Fig. 5 for an example. We can also define the r-Lyndon tree of an arbitrary string. Let $ 0 , $ 1 be special characters smaller than and greater than all the letters from Σ, respectively. We then define LTree r (w) as LTree r ($ r w); note that $ r w is an r-Lyndon word.

LCE Queries For two strings u and v, by lcp(u, v) we denote the length of their longest common prefix. Let w be a string of length n. An LCE query LCE(i, j)

computes lcp(w[i, n], w[j, n]
). An -limited LCE query Limited-LCE ≤ (i, j) computes min(LCE(i, j), ). Such queries can be answered efficiently as follows; see Lemma 6.3 in [START_REF] Gawrychowski | Faster longest common extension queries in strings over general alphabets[END_REF].

Lemma 1 ([11]

). A sequence of q queries Limited-LCE ≤ p (i p , j p ) can be answered on-line in O((n+ q p=1 log p )α(n)) time over a general ordered alphabet. The following observation shows a relation between LCE queries and periods in a string that we use in our data structure; for an illustration see Fig. 1. Non-Crossing Pairs For a positive integer n, we define the set of pairs

Observation 2. Assume that the factors w[a, d A -1] and w[b, d B -1] have the same string period, but neither w[a, d A ] nor w[b, d B ] has this string period. Then LCE(a, b) = min(d A -a, d B -b) if d A -a = d B -b, d A -a + LCE(d A , d B ) otherwise.
P n = {(a, b) ∈ Z 2 : 1 ≤ a ≤ b ≤ n}. Pairs (a, b) and (a , b ) are called crossing if a < a < b < b or a < a < b < b. A subset S ⊆ P n is called non-crossing if it does not contain crossing pairs.
A graph G is called outerplanar if it can be drawn on a plane without crossings in such a way that all vertices belong to the unbounded face. An outerplanar graph on n vertices has less than 2n edges (at most 2n -3 for n ≥ 2). Fact 3. A non-crossing set of pairs S ⊆ P n has less than 3n elements.

Proof. We associate S \ {(a, a) : 1 ≤ a ≤ n} with a plane graph on vertices {1, . . . , n} drawn on a circle in this order, and edges represented as straight-line segments. The non-crossing property of pairs implies that these segments do not intersect. Thus, the graph drawing is outerplanar, and therefore the number of edges is less than 2n. Accounting for the pairs of the form (a, a), we get the claimed upper bound.

For a set of pairs S = {(a i , b i ) : 1 ≤ i ≤ k} and a positive integer t, by S/t we denote the set {( ai t , bi t ) : 1 ≤ i ≤ k}. Observation 4. If S is non-crossing, then S/t is also non-crossing.

High-Level Description of the Data Structure

We say that a sequence of LCE(a, b) queries, for a ≤ b, is non-crossing if the underlying collection of pairs (a, b) is non-crossing. In this section, we give an overview of our data structure, which answers a sequence of q non-crossing LCE queries on-line in O(q + n • α(n)) total time.

The data structure is composed of log n levels. Function LCE (i) (a, b) corresponds to the level i and returns LCE(a, b). In the computation it may make calls to LCE (i+1) (a, b). However, we make sure that the total number of such calls is bounded. Each original LCE(a, b) query is first asked at the level 0.

The implementation of LCE

(i) (a, b) consists of two phases. If LCE(a, b) ≥ 3 • 2 i ,
then this LCE (i) query is called relevant; otherwise it is called short. In the first phase, we check the type of the query via a Limited-LCE ≤3•2 i (a, b) query. This lets us immediately answer short queries. In the second phase, we know that the query is relevant, and we try to deduce the answer based on data gathered while processing similar queries or to learn some information useful for answering future similar queries by asking LCE (i+1) queries.

We shall say that

LCE (i) queries for (a, b) and (a , b ) are similar if a 2 i = a 2 i and b 2 i = b 2 i .
Each equivalence class of this relation is processed by an independent component, called a block-pair, identified by a pair of blocks (A, B), which are intervals of the form [x • 2 i + 1, (x + 1) • 2 i ] containing indices a and b, respectively. If a relevant LCE (i) (a, b) query satisfies a ∈ A and b ∈ B for some block-pair (A, B), we say that the block-pair is responsible for the query or that the query concerns the block-pair. As we show in Section 5, the pairs of interval right endpoints of block-pairs at each level are non-crossing (whereas LCE (i) queries that will be asked for i ≥ 1 are non necessarily non-crossing).

The implementation of a block-pair, summarized in the lemma below, is given in Section 4.

Lemma 5. Consider a sequence of relevant LCE (i) queries concerning a blockpair (A, B). The block-pair can answer these queries on-line in worst-case constant time plus the time to answer at most four LCE (i+1) (a, b) queries, such that each either corresponds to the currently processed LCE (i) query or satisfies a < b ≤ a + 2 i+1 .

Structural conditions stated in Lemma 5 let us characterize the set of queries passed to the next level. The complexity analysis in Section 5 relies on this characterization.

Block-Pair Implementation

Our aim in this section is to prove Lemma 5. Information stored by a block-pair changes through the course of the algorithm, and the implementation of the query algorithm depends on what is currently stored. We distinguish four states of a block pair (A, B) at level i. Fig. 2 illustrates two of the states.

state(A, B) description initial

No auxiliary data is stored.

visited(a 0 , b 0 , L) a 0 ∈ A, b 0 ∈ B, L = LCE(a 0 , b 0 ) ≥ 3 • 2 i . full(d A , d B ) ∃ p∈[1,2 i+1 ] : w[max A, d A -1]

Initial State

In this state, we simply forward the query to the level i + 1, return the obtained LCE(a, b) value, and change the state to visited(a, b, LCE(a, b)).

Algorithm 1: Initial-LCE (i) (A,B) (a, b) Require: LCE (i) (a, b) concerns (A, B), whose state is initial L ← LCE (i+1) (a, b);
higher level call transform (A, B) to state visited(a, b, L); return L;

Visited State

In state visited(a 0 , b 0 , L), we can immediately determine LCE(a, b) if (a, b) is a shift of (a 0 , b 0 ). Otherwise, we apply Lemma 6 to move to state full. Proof. We shall first prove that LCE(a, a + q) ≥ 3

• 2 i -(b -b ) where q = (b -b ) -(a -a ). First, observe that a + q = a + (b -b ), and thus LCE(a + q, b) = LCE(a + (b -b ), b + (b -b )) ≥ 3 • 2 i -(b -b ) because LCE (i) (a , b ) is relevant. Since LCE (i) (a, b) is also relevant, we have LCE(a, b) ≥ 3 • 2 i ≥ 3 • 2 i - (b -b ). Combining these two inequalities, we immediately get LCE(a, a + q) ≥ min(LCE(a, b), LCE(a + q, b)) ≥ 3 • 2 i -(b -b ), as claimed.
If q > 0, we have q = p, and thus LCE(a, a+p)

≥ 3•2 i -(b-b ). Since the two LCE (i) queries are similar, we have 3•2 i -(b-b ) ≥ 2 i+1
, so LCE(a, a+p) ≥ 2 i+1 . See Fig. 3 for an illustration of this case.

Otherwise, q = -p, and we have LCE(a, a -p) ≥ 3

• 2 i -(b -b ), which implies LCE(a + p, a) ≥ 3 • 2 i -(b -b ) + q = 3 • 2 i -(a -a ).
Again, the fact that the queries are similar yields 3

• 2 i -(a -a ) ≥ 2 i+1 , and consequently LCE(a, a + p) ≥ 2 i+1 . a a p = q ≥ 2 i+1 b -b b b LCE(a , b ) ≥ 3 • 2 i LCE(a, b) ≥ 3 • 2 i
Fig. 3. Illustration of Lemma 6: case q > 0. We assume that LCE(a+q, b) ≤ LCE(a, b).

The marked fragments correspond to LCE(a, a + q) = LCE(a + q, b).

In the query algorithm, we first check if a-a 0 = b-b 0 . If so, let us denote the common value by ∆. Note that |∆| ≤ 2 i , LCE(a, b) ≥ 3 • 2 i , and LCE(a 0 , b 0 ) ≥ 3 • 2 i . This clearly yields LCE(a, b) = LCE(a 0 , b 0 ) + ∆, which lets us compute the result in constant time. implies that these queries satisfy the condition of Lemma 5. The answer to the initial LCE (i) (a, b) query is computed by the routine for state full, which we give below.

Algorithm 2: Visited-LCE (i) (A,B) (a, b) Require: LCE (i) (a, b) concerns (A, B), whose state is visited(a 0 , b 0 , L) if a -a 0 = b -b 0 then return L + a -a 0 ; else p ← |(a -a 0 ) -(b -b 0 )|; a ← max A; b ← max B; d A ← a + p + LCE (i+1) (a , a + p); higher level call d B ← b + p + LCE (i+1) (b , b + p); higher level call transform (A, B) to state full(d A , d B ); return Full-LCE (i) (A,B) (a

Full States

In state full + we can answer every relevant query in constant time. In state full we can either answer the query in constant time or make the final query at level i + 1 to transform the state to full + ; see the following lemma.

Algorithm 3: Full-LCE (i) (A,B) (a, b) Require: LCE (i) (a, b) concerns (A, B), whose state is full(d A , d B ) or full + (d A , d B , L ) if d A -a = d B -b then return min(d A -a, d B -b); else if (A, B) is in state full(d A , d B ) then L ← LCE (i+1) (a, b) -(d A -a); higher level call transform (A, B) to state full + (d A , d B , L ); return d A -a + L ;
4.4 Proof of Lemma 5 Lemma 5. Consider a sequence of relevant LCE (i) queries concerning a blockpair (A, B). The block-pair can answer these queries on-line in worst-case constant time plus the time to answer at most four LCE (i+1) (a, b) queries, such that each either corresponds to the currently processed LCE (i) query or satisfies a < b ≤ a + 2 i+1 .

Proof. Algorithms 1 to 3 answer queries concerning the block-pair (A, B), and use constant time. The level i + 1 call is only made when the state changes. The original query is forwarded during a shift from state initial to visited and from state full to full + , while during a shift from visited to full two LCE queries are asked, both with arguments at distance p ≤ 2 i+1 , as claimed.

Consequently, Fact 3 proves that the number of block-pairs responsible for a query at level i -1 is bounded by 3n 2 i-1 . Each of them yields at most 4 queries at level i. This leads straight to the following bound. Observation 9. |S i | ≤ 24n 2 i for i ≥ 1. If we stored the block-pairs using a hash table, we could retrieve the internal data of the block-pair responsible for (a, b) in randomised constant time. However, in the case of non-crossing LCE queries we can make this time worst-case.

Recall from Fact 3 that for a set S ⊆ P n of non-crossing pairs we can identify S \ {(a, a) : 1 ≤ a ≤ n} with an outerplanar graph on vertices {1, . . . , n}. We say that a simple undirected graph has arboricity at most c if it can be partitioned into c forests. Outerplanar graphs have arboricity at most 2 (see [START_REF] Nash-Williams | Decompositions of finite graphs into forests[END_REF]) which lets us use the following theorem to store S \ {(a, a) : 1 ≤ a ≤ n}. Membership queries for pairs (a, a) are trivial to support using an array.

Theorem 10 ([4]

). Consider a graph of arboricity c with vertices given in advance and edges revealed on-line. One can support adjacency queries, asking to return the edge between two given vertices or nil if it does not exist, in worst-case O(c) time, with edge insertions processed in amortized constant time.

The following corollary shows, by Fact 8, that indeed the block-pairs at each level can be retrieved in worst-case constant time.

Corollary 11. Consider a set S ⊆ P n of non-crossing pairs arriving on-line. One can support membership queries (asking if (a, b) ∈ S and, if so, to return data associated with this pair) in worst-case constant time with insertions processed in amortized constant time.

Theorem 12. In a string of length n, a sequence of q non-crossing LCE queries can be answered in total time O(q + n • α(n)).

Proof. For i > 0, an LCE (i) query, excluding the LCE (i+1) queries called, requires O(i•α(n)) time for answering a Limited-LCE ≤3•2 i query by Lemma 1 plus O(1) additional time by Lemma 5. For i = 0 we may compute Limited-LCE ≤3 naïvely in constant time, so the running time is constant.

The number of LCE (0) queries is q, while the number of LCE (i) queries for i ≥ 1 is O( n 2 i ) by Observation 9. The total running time is therefore

O q + n • α(n) • ∞ i=1 i 2 i = O(q + n • α(n)).

Computing Runs

Bannai et al. [START_REF] Bannai | The "runs" theorem[END_REF][START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF] presented an algorithm for computing all the runs in a string of length n that works in time proportional to answering O(n) LCE queries on the string or on its reverse. As main tool they used Lyndon trees. We note here that the LCE queries asked by their algorithm can be divided into a constant number

  called a string period of w. By an interval [ , r] we mean the set of integers { , . . . , r}. If w is a string of length n, then an interval [a, b] is called a run in w if 1 ≤ a < b ≤ n, the shortest period p of w[a, b] satisfies 2p ≤ b -a + 1 and none of the factors w[a -1, b] and w[a, b + 1] (if it exists) has the period p. An example of a run is shown in Fig. 4.

Fig. 1 .

 1 Fig. 1. In this example figure dA -a = 14, dB -b = 18, and p = 4. We have LCE(a, b) = 14 and LCE(a , b ) = 8 + LCE(dA, dB).

Fig. 2 .

 2 Fig. 2. Block-pair (A, B) in states visited(a0, b0, L) and full + (dA, dB, L ).

Lemma 6 .

 6 Let LCE (i) (a, b), LCE (i) (a , b ) be similar and relevant queries and let p = |(b -b ) -(a -a )|. If p = 0 and b ≤ b, then LCE(a, a + p) ≥ 2 i+1 , i.e., p is a (not necessarily shortest) period of the factor w[a, a + 2 i+1 + p -1].

  , b); recursive call on state full Otherwise, our aim is to change the state of the block-pair to full. Lemma 6 lets us deduce that LCE(ā, ā+p) ≥ 2 i+1 for some ā ∈ {a, a 0 } and (by symmetry) LCE( b, b + p) ≥ 2 i+1 for some b ∈ {b, b 0 }, where p = |(a -a 0 ) -(b -b 0 )| (ā and b depend on the relative order of b, b 0 and a, a 0 , respectively). Let a = max A and b = max B. We have LCE(a , a + p) ≥ 2 i and LCE(b , b + p) ≥ 2 i because a -2 i < ā ≤ a and b -2 i < b ≤ b . Such a situation allows for a move to state full. The exact values of d A and d B are computed using a higher level call, which lets us determine LCE(a , a + p) and LCE(b , b + p). Note that p ≤ 2 i+1

Lemma 7 .

 7 Consider a relevant LCE (i) (a, b) query concerning a block-pair (A, B)in state full(d A , d B ) or full + (d A , d B , L ). Then LCE(a, b) = min(d A -a, d B -b) if d A -a = d B -b, d A -a + LCE(d A , d B ) otherwise.Proof. Let a 0 = max A, b 0 = max B and let p be the witness period of the state of (A, B).Let us define ∆ = max(a 0 -a, b 0 -b), a = a + ∆, and b = b + ∆. Observe that ∆ ≤ 2 i , a 0 ≤ a ≤ a 0 + 2 i , and b 0 ≤ b ≤ b 0 + 2 i . The fact that the query is relevant yields LCE(a, b) ≥ 3•2 i ≥ p+∆, so LCE(a, b) = ∆+LCE(a , b ) and LCE(a , b ) ≥ p. Moreover, d A ≥ p + 2 i + a 0 and d B ≥ p + 2 i + b 0 implies that fragments w[a , d A -1] and w[b , d B -1] have length at least p, and thus they are right-maximal with period p. Consequently, the fragments w[a , d A -1] and w[b , d B -1] have the same string period of length p. This lets us apply Observation 2, which gives LCE(a , b ) = min(d A -a , d B -b ) if d A -a = d B -b , d A -a + LCE(d A , d B ) otherwise. Since a = a + ∆, b = b + ∆, and LCE(a, b) = ∆ + LCE(a , b ), this is clearly equivalent to the claimed formula for LCE(a, b).

Fig. 4 .Fig. 5 .

 45 Fig. 4. Example of a run w[3, 10] in the string w = ababaabaabbbaa.

  and w[max B, d B -1] have common period p and length at least p + 2 i , but neither w[max A, d A ] nor w[max B, d B ] has period p.

full + (d A , d B , L ) As in full(d A , d B ) plus L = LCE(d A , d B ).

Supported by Polish budget funds for science in 2013-2017 as a research project under the 'Diamond Grant' program. The author is a Newton International Fellow. Supported by the Polish National Science Center, grant no 2014/13/B/ST6/00770.

Complexity Analysis

Algorithm 4 summarizes the implementation of the LCE (i) (a, b) function. As mentioned in Section 3, we first compute Limited-LCE ≤3•2 i (a, b), which might immediately give us the sought value LCE(a, b). Otherwise the query is relevant, and we refer to the block-pair (A, B) which is responsible for the query. Initial-LCE Proof. We proceed by induction on i. The base case is trivial from the assumption on the input sequence. Lemma 5 proves that

The first component is non-crossing by the inductive hypothesis combined with Observation 4. Pairs of the form (a, a) and (a, a + 1) do not cross any other pair, so adding them to a non-crossing family preserves this property.

of groups, each consisting of non-crossing LCE queries. Roughly speaking, this is based on the obvious fact that intervals in a Lyndon tree form a laminar family, i.e., for every two they are either disjoint or one of them contains the other.

In the first phase, given a string w, the algorithm of [START_REF] Bannai | The "runs" theorem[END_REF][START_REF] Bannai | A new characterization of maximal repetitions by Lyndon trees[END_REF] constructs LTree 0 (w) and LTree 1 (w). For each r ∈ {0, 1}, the construction of LTree r (w) goes from right to left. Before the k-th step (for k = n, . . . , 1), we store on a stack the roots of subtrees of LTree r (w) that correspond to w[k + 1, n]. Hence, the intervals corresponding to the roots on the stack are disjoint and cover the interval Proof. In the k-th step of the algorithm we only ask LCE(i, j) queries for i = k. Suppose towards contradiction that in the course of the algorithm we ask two LCE queries with (i, j) and (i , j ) such that i < i < j < j . The latter is asked at step i , and at that moment [i , j -1] is a root of a subtree of LTree r (w). Then the former is asked at step i, and then [i, j -1] is a root of a subtree of LTree r (w). This contradicts the fact that the intervals in LTree r (w) form a laminar family.

In the second phase, for each node [a, b] of each Lyndon tree LTree r (w) we check if there is a run with period p = b -a + 1 that contains w[a, b]. To this end we check how long does the periodicity with period p extend to the right and to the left of w[a, b]. The former obviously reduces to an LCE(a, b + 1) query and the latter to an LCE query in the reverse of w, which is totally symmetric. As the intervals in LTree r (w) form a laminar family, we arrive at the following. Observation 14. The LCE queries asked when right-extending the periodicity of the intervals from LTree r (w) are non-crossing.

By Observations 13 and 14, Theorem 12 yields the following result and its immediate corollary.

Theorem 15. The Lyndon tree and the set of all runs in a string of length n over a general ordered alphabet can be computed in O(nα(n)) time. Tree-Structured Interpretation of the Algorithm We show on an example an alternative graphical illustration of the behaviour of the query algorithm. To answer an LCE(a, b) query we traverse a sequence of block-pairs that we call here a working sequence (A 0 , B 0 ), (A 1 , B 1 ), . . . Note that the blocks form a tree-like structure, which lets us depict them using a binary tree; see Fig. 6. The behaviour of the algorithm depends on the states of the block-pairs. For example, if all the block-pairs are in state initial, their state becomes visited and the sequence of queries is interrupted at the first level i for which the query is short (i.e., LCE(a, b) < 3 • 2 i ). On the other hand, if a block-pair (A i , B i ) is in state visited(a 0 , b 0 , L), then the query may be answered immediately if a 0 -a = b 0 -b, and otherwise two additional LCE (i+1) queries are triggered and the state of the block-pair becomes full.


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

Costas Iliopoulos

Marcin Kubica
email: [kubica@mimuw.edu.pl

Jakub Radoszewski

Wojciech Rytter
email: rytter@mimuw.edu.pl

Krzysztof Stencel
email: stencel@mimuw.edu.pl

Tomasz Waleń
email: walen]@mimuw.edu.pl

New Simple Efficient Algorithms Computing Powers and Runs in Strings

Keywords: run, repetition, square, cube (in a string), Dictionary of Basic Factors

Three new simple O(n log n) time algorithms related to repeating factors are presented in the paper. The first two algorithms employ only a basic textual data structure called the Dictionary of Basic Factors. Despite their simplicity these algorithms not only detect existence of powers but also find all primitively rooted cubes (as well as higher powers) and all cubic runs. Our third O(n log n) time algorithm computes all runs and is probably the simplest known efficient algorithm for this problem. It uses additionally the Longest Common Extension function, however, due to relaxed running time constraints, a simple O(n log n) time implementation can be used. At the cost of logarithmic factor (in time complexity) we have novel algorithmic solutions for several classical string problems which are much simpler than (usually quite sophisticated) linear time algorithms.

Introduction

In this paper, we present algorithms finding various types of repetitions in a string: powers (e.g. squares or cubes), cubic runs and runs. Finding repetitions is a fundamental problem in text processing and has numerous applications. Examples of such applications, an explanation of the motivation and related topics can be found in the survey [START_REF] Crochemore | Repetitions in strings: Algorithms and combinatorics[END_REF].

Various problems related to finding repetitions in a string have already been studied. For the problem of finding all distinct squares, a linear time algorithms are known [START_REF] Gusfield | Linear time algorithms for finding and representing all the tandem repeats in a string[END_REF][START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF][START_REF] Kolpakov | On maximal repetitions in words[END_REF]. It is also known, that the maximal number of distinct squares in a string is linear [START_REF] Fraenkel | How many squares can a string contain?[END_REF].

Multiple approaches to searching for squares in a string can be found in the literature, however most of the existing algorithms are rather complex. The first approach, is to check if a string is square-free. O(n log n) time algorithms for this problem have been presented in [START_REF] Main | Linear time recognition of squarefree strings[END_REF][START_REF] Rabin | Discovering repetitions in strings[END_REF] (the latter one is randomized). The optimal O(n) time algorithms are described in [START_REF] Crochemore | Transducers and repetitions[END_REF][START_REF] Main | Linear time recognition of squarefree strings[END_REF].

Another approach is to find all occurrences of primitively rooted squares in a string. A number of O(n log n) time algorithms reporting all such occurrences can be found in [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF][START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF][START_REF] Kosaraju | Computation of squares in a string (preliminary version)[END_REF][START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF][START_REF] Slisenko | Detection of periodicities and string matching in real time[END_REF][START_REF] Stoye | Simple and flexible detection of contiguous repeats using a suffix tree[END_REF]. Due to the lower bound shown in [START_REF] Crochemore | Bounds on powers in strings[END_REF] these algorithms are optimal.

Yet another approach is to report all occurrences of squares in a string. If we denote the number of such occurrences by z, then both O(n log n+z) time algorithms [START_REF] Landau | An algorithm for approximate tandem repeats[END_REF][START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF][START_REF] Stoye | Simple and flexible detection of contiguous repeats using a suffix tree[END_REF] and O(n + z) time algorithms [START_REF] Gusfield | Linear time algorithms for finding and representing all the tandem repeats in a string[END_REF][START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF][START_REF] Kolpakov | On maximal repetitions in words[END_REF] are known for this problem.

Finally, there are recent results related to on-line square detection (that is, when letters of u are given one by one), improving the time complexity from O(n log 2 n) [START_REF] Leung | An efficient online algorithm for square detection[END_REF] to O(n log n) [START_REF] Jansson | Online and dynamic recognition of squarefree strings[END_REF] and O(n) [START_REF] Chen | An optimal algorithm for online square detection[END_REF].

Let u be a string of length n over a bounded alphabet. In Section 3 a very simple O(n log n) time algorithm checking whether u contains any kth string power is presented. The algorithm reports all occurrences of primitively rooted kth powers for any k ≥ 3, in particular, primitively rooted cubes. As a by-product we obtain an alternative, algorithmic proof of the fact [START_REF] Crochemore | Bounds on powers in strings[END_REF] that the maximal number of such occurrences is O(n log n). The output of the algorithm is later on used to list all cubic runs in u, within the same time complexity.

From the aforementioned literature, the papers [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF][START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF][START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF] deal also with powers of arbitrary (integer) exponent, however the techniques used there (e.g., suffix trees, Hopcroft's factor partitioning) are much more sophisticated than the techniques applied in this paper. The O(n log n) time algorithm for a single square detection from [START_REF] Main | Linear time recognition of squarefree strings[END_REF] is in some sense similar to the algorithm presented in this paper. However it is less versatile than ours: we see no simple modification adapting it to detect all occurrences of primitively rooted higher powers.

In Section 4, we present an application of the algorithm finding all occurrences of primitively rooted cubes to find all cubic runs. This algorithm also runs in O(n log n) time and it does not use any additional advanced techniques.

Finally, in Section 5, we give an algorithm reporting all runs in a string, in O(n log n) time. It is significantly simpler than all known O(n log n) time algorithms present implicitly in [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF][START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF][START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF] and than the optimal O(n) time algorithm [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF][START_REF] Kolpakov | On maximal repetitions in words[END_REF]. The only non-trivial technique used in our algorithm is the Longest Common Extension function. It can be either implemented as described in [START_REF] Crochemore | Efficient algorithms for two extensions of LPF table: The power of suffix arrays[END_REF][START_REF] Ilie | Practical algorithms for the longest common extension problem[END_REF] -very efficiently, but using quite sophisticated machinery, or less efficiently, but in a much simpler way, what is sufficient to obtain O(n log n) time complexity.

Preliminaries

We consider words (strings) over a bounded alphabet Σ, u ∈ Σ * . The empty word is denoted by ε. The positions in u are numbered from 1 to |u|. For u = u 1 u 2 . . . u n , by u[i . . j] we denote a factor of u equal to u i . . . u j (in particular u

[i] = u[i . . i]). Words u[1 . . i] are called prefixes of u, words u[i .
. n] suffixes of u, whereas words that are both a prefix and a suffix of u are called borders of u.

We say that a positive integer p is a period of the word u = u 1 . . . u n if u i = u i+p holds for all i, 1 ≤ i ≤ np. Periods and borders correspond to each other, i.e. u has a period p if and only if it has a border of length np, see e.g. [START_REF] Crochemore | Algorithms on Strings[END_REF][START_REF] Crochemore | Jewels of Stringology[END_REF].

A run (also called a maximal repetition) in a string u is such an interval [i . . j], that:

-the shortest period p of the associated factor u[i . . j] satisfies 2p ≤ ji + 1, -the interval can be extended neither to the left nor to the right, without violating the above property, that is,

u[i -1] = u[i + p -1] and u[j -p + 1] = u[j + 1],
provided that the respective characters exist.

A cubic run is a run [i . . j] for which the shortest period p satisfies 3p ≤ ji + 1. We identify a run (or a cubic run) with a corresponding triple (i, j, p).

If w k = u (k is a positive integer) then we say that u is the kth power of the word w. A square (cube) is the 2nd (3rd) power of some nonempty word.

Dictionary of Basic Factors

Dictionary of Basic

[i . . i + 2 t -1] ≤ u[j . . j + 2 t -1] if and only if N ame t [i] ≤ N ame t [j]
. DBF has a variety of known applications in the field of text and sequence algorithms, see e.g. [START_REF] Crochemore | Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays[END_REF].

DBF(u) requires O(n log n) space and can be constructed in O(n log n) time [START_REF] Crochemore | Jewels of Stringology[END_REF]. N ame 0 [ ] contains information about consecutive characters of u. So, N ame 0 [ ] can be computed in O(n) time, by sorting all the letters appearing in u and mapping characters of u to numbers from 1 on. Having computed

N ame t [ ], one can easily compute N ame t+1 [ ] in O(n) time. Factor u[i . . i + 2 t+1 -1] is a concatenation of factors u[i . . i + 2 t -1] and u[i + 2 t . . i + 2 t+1 -1].
Hence, it can be represented by a pair (N ame t [i], N ame t [i + 2 t ]). Then, all such pairs can be sorted lexicographically (in O(n) time) and mapped onto their ranks, that is integers from 1 on. Figure 1 shows the DBF for an example string. Using DBF, one can compare factors of arbitrary length, as given in the following Lemma, see [START_REF] Crochemore | Jewels of Stringology[END_REF]. Proof. Let u[i . . j] and u[i ′ . . j ′ ] be the two factors that should be compared. We can assume, that ji = j ′i ′ , since otherwise they have different lengths, cannot be equal and can be compared by trimming the longer factor.

Text a b b a a b b a b b a N ame 0 [ ] 1 2 2 1 1 2 2 1 2 2 1 (1, 2) (2, 2) (2, 1) (1, 1) (1, 2) (2, 2) (2, 1) (1, 2) (2, 2) (2, 1) N ame 1 [ ] 2 4 3 1 2 4 3 2 4 3 (2, 3) (4, 1) (3, 2) (1, 4) (2, 3) (4, 2) (3, 4) (2, 3) N ame 2 [ ] 2 5 3 1 2 6 4 2 (2, 2) (5, 6) (3, 4) (1, 2) N ame 3 [ ] 2 4 3 1
Let t be such an integer, that 2 t ≤ ji < 2 t+1 . Then, it is enough to compare u

[i . . i + 2 t -1] with u[i ′ . . i ′ + 2 t -1], and u[j -2 t + 1 . . j] with u[j ′ -2 t + 1 . . j ′ ]. This however can be done by comparing N ame t [i] with N ame t [i ′ ], and N ame t [j -2 t + 1] with N ame t [j ′ -2 t + 1]. ⊓ ⊔
Later on, we show, that the memory complexity of the presented algorithm can be reduced to O(n), although it uses DBF(u). To do this, we cannot store all the arrays N ame t [ ]. Instead, we should store just a fixed number (e.g. one) of such arrays, and design the algorithm in such a way, that are used in the ascending order of t. Then, new arrays can be computed when needed, replacing previously used arrays. Still, it is possible to compare factors in O(1) time, provided that the ratio between the length of the compared factors and 2 t is bounded, as expressed by the following Lemma.

Lemma 2. Let t be a fixed number between 0 and ⌊log n⌋, and let N ame t [ ] be one of the arrays constituting DBF(u). It is possible to compare factors of u of length l, using just N ame t [ ], in constant time, provided that: l ≥ 2 t and l 2 t = O(1). Proof. The proof is similar to the proof of the previous Lemma. The compared factors can be covered using O(1) factors of length 2 t . Hence, it is enough to compare O(1) pairs of elements of N ame t [ ].

⊓ ⊔

Detecting String Powers

Let u be a word of length n. The following algorithm tests if u contains a kth power, for k ≥ 2. It exploits DBF(u) and two other auxiliary data-structures, denoted by POWERS and P rev. POWERS is a list on which the result is accumulated. Each occurrence of a power of the form (u[pos . . pos+root-1]) k (i.e. kth power of a factor of length root, starting at position pos) is represented by a pair (root, pos). The output of the algorithm is a list of pairs denoting kth powers. We allow the same power to be inserted multiple times -at the end the list is sorted and the repetitions are removed.

P rev [1 . . n] is an array of positions in the text, such that P rev[N ame t [j]] is the most recent occurrence of u[j . . j + 2 t -1] preceding j, or -1 if there is none.

For all values of t, the algorithm scans the text, and for each position j it checks (in constant time) if factors of u of length 2 t , starting at P rev[N ame t [j]] and j generate a power. Examples of how the algorithm works can be found in Fig. 2 Table 1. For the Thue-Morse word of length 32 the algorithm reports the following squares (pairs (root, pos)): t = 0: (1, 2), (2, 3), [START_REF]Combinatorial Algorithms on Words[END_REF][START_REF] Crochemore | Bounds on powers in strings[END_REF], [START_REF]Combinatorial Algorithms on Words[END_REF][START_REF] Crochemore | Repetitions in strings: Algorithms and combinatorics[END_REF], [START_REF]Combinatorial Algorithms on Words[END_REF][START_REF] Crochemore | Efficient algorithms for two extensions of LPF table: The power of suffix arrays[END_REF], [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF][START_REF] Crochemore | Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays[END_REF], [START_REF]Combinatorial Algorithms on Words[END_REF][START_REF] Gusfield | Linear time algorithms for finding and representing all the tandem repeats in a string[END_REF], [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF][START_REF] Ilie | Practical algorithms for the longest common extension problem[END_REF], [START_REF]Combinatorial Algorithms on Words[END_REF][START_REF] Kolpakov | On maximal repetitions in words[END_REF], [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF][START_REF] Kosaraju | Computation of squares in a string (preliminary version)[END_REF], [START_REF]Combinatorial Algorithms on Words[END_REF][START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF], [START_REF]Combinatorial Algorithms on Words[END_REF][START_REF] Rabin | Discovering repetitions in strings[END_REF], [START_REF]Combinatorial Algorithms on Words[END_REF][START_REF] Stoye | Simple and flexible detection of contiguous repeats using a suffix tree[END_REF], [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF]27), (1, 30); t = 1: (4, 5), [START_REF] Chen | An optimal algorithm for online square detection[END_REF][START_REF] Crochemore | Jewels of Stringology[END_REF], [START_REF] Chen | An optimal algorithm for online square detection[END_REF][START_REF] Jansson | Online and dynamic recognition of squarefree strings[END_REF], [START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF][START_REF] Leung | An efficient online algorithm for square detection[END_REF]; t = 2: (8, 9). In particular, the algorithm reports all squares in the Thue-Morse words.

In the analysis of the algorithm we use some combinatorics of primitive words. The primitive root of a word u is the shortest word w, such that w k = u for some positive integer k. We call a word u primitive if it equals its primitive root, otherwise it is called non-primitive. Primitive words admit a so-called synchronizing property, as given in the following Lemma, see [START_REF] Crochemore | Algorithms on Strings[END_REF].

Lemma 3 (Synchronizing property of primitive words).

A nonempty word is primitive if and only if it occurs as a factor in its square only as a prefix and a suffix. Proof. Obviously, all positions reported by the algorithm represent kth powers. Thus we only need to show that no non-primitively-rooted powers are reported.

Consider lines 7-12 of the algorithm, for some t and j. Assume that pos = 0. To conclude the proof of the theorem, it suffices to show that the word w def = u[pos . . j -1] is always primitive.

Assume to the contrary, that w = v m , for some v and m ≥ 2. Let z = u[j . . j + 2 t -1] = u[pos . . j + 2 t -1]. There are two cases (see Fig. 3): a) Let us assume, that |w| ≥ 2 t . Then z is a prefix of of w and |v| is a period of z. b) Let us assume, that |w| < 2 t . Then w is a prefix of z and u[j . . j + 2 t -|w| -1] is a border of z.

In both cases z appears also at position j-|v|. Hence, P rev[N ame t [j]] ≥ j-|v| > pos, this contradiction concludes the proof.

⊓ ⊔

The following two theorems conclude that the algorithm correctly checks if the word contains any kth power (i.e., whether the word is kth-power-free or not), and also reports (among others) all kth powers of specific type, depending on the value of parameter k (2 or ≥ 3). Proof. Let v 2 be any shortest square occurring in u at position i. Note that v must be primitive. Let s be such an integer, that 2 s ≤ |v| < 2 s+1 . Consider the step of the algorithm in which t = s, j = i + |v|. We show that the algorithm reports the square v 2 in this step, i.e., pos = i. Obviously pos ≥ i, hence it suffices to show that this value cannot be greater than i. If this was the case, the factor w def = u[j . . j + 2 t -1] would occur in u at positions i, pos and j, thus forming an overlap, see Fig. 4. However, an overlap of a string of length 2 t corresponds to a square in u with primitive root shorter than 2 t , what contradicts the fact that v 2 is the shortest square in u.

⊓ ⊔ Theorem 6. For a given k ≥ 3, the DetectPowers algorithm finds all occurrences of primitively rooted kth powers in u.

Proof. Assume that there is an occurrence of v k , for v primitive, which starts at position i in u. Let integer s be defined as 2 s-1 < |v| ≤ 2 s . Let us consider the step of the algorithm in which t = s, j = i + |v|. We show that in this step pos = i, this concludes that the considered power is reported by the algorithm. Let us note that pos ≥ i, since 2 t < 2|v|, and therefore:

u[i . . i + 2 t -1] = u[j . . j + 2 t -1] def = w,
see Fig. 5a. We prove the inequality pos ≤ i by contradiction. Assume that i < pos < j. Then the prefix of w of length |v|, that is the word v, would occur in u at positions: i, pos and j (see Fig. 5.b). This is not possible, however, due to the synchronizing property of primitive words (Lemma 3).

⊓ ⊔

Remark. It is easy to see that the stronger claim (from Theorem 6) does not hold in the case of k = 2 (Theorem 5). That is, not all primitively rooted squares are detected by the algorithm. Among others, the squares for which the primitive root admits a very long border, e.g., ((ab) m a) 2 , may not be reported.

Finally, let us consider the complexity of the algorithm DetectPowers.

Theorem 7. The time complexity of the DetectPowers algorithm is O(n log n). Moreover, for k = O(1) the algorithm can be modified to require only O(n) space and still satisfy the properties from Theorems 4-6.

Proof. The analysis of the time complexity is straightforward -the outer loop of the algorithm makes O(log n) iterations and in each iteration the inner loop runs in O(n) time.

The space complexity of the presented implementation is also O(n log n) due to the space requirements of the DBF, however it can be reduced to O(n) if only two consecutive rows of the table N ame are stored in the memory.

This causes a difficulty only in the kth-power-test in line 8, since the value of root can be arbitrary. However, along with the proofs of Theorems 5 and 6, we can immediately return f alse in the test if the parameter root is not in the interval [2 t , 2 t+1 ) (for squares) or the interval (2 t-1 , 2 t ] (for higher powers), and still the output of the algorithm will fulfill the requirements.

Thus the predicate reduces to testing equality of words of length (k -1)

• root = c•2 t-1 , where 1 ≤ c = O(1) for k = O(1), thus can be performed using only N ame t-1 [ ] in constant time (Lemma 2).
⊓ ⊔

Application of the DetectPowers Algorithm for Cubic Runs

In this section we show how to use the output of the DetectPowers algorithm to compute, in a simple manner, all cubic runs in a string u of length n in O(n log n) time. Cubic runs [START_REF] Crochemore | On the maximal number of cubic runs in a string[END_REF] are special type of runs in which the period is at least 3 times shorter than the run, hence they characterize strong periodic properties of a word. Let L be the output of the DetectPowers algorithm for u and k = 3. It is a sorted list of pairs with repetitions removed. Moreover, without the loss of generality, we can assume, that it is sorted in ascending lexicographical order of pairs. Let us define a special sublist of L as a maximal continuous subsequence of L of the form (per, i), (per, i + 1), . . . , (per, i + s). Note, that such a sublist corresponds to a cubic run (i, i + s + 3 • per -1, per).

Example 8. For the following list of pairs (root, pos): L = (2, 3), [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF][START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF], [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF][START_REF] Crochemore | Transducers and repetitions[END_REF], [START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF][START_REF] Crochemore | Repetitions in strings: Algorithms and combinatorics[END_REF], [START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF][START_REF] Crochemore | On the maximal number of cubic runs in a string[END_REF], (4, 28), (4, 29), (4, 30), (4, 31), [START_REF] Crochemore | Transducers and repetitions[END_REF][START_REF] Kolpakov | On maximal repetitions in words[END_REF] the corresponding cubic runs are:

(3, 10, 2), [START_REF] Crochemore | Repetitions in strings: Algorithms and combinatorics[END_REF][START_REF] Landau | An algorithm for approximate tandem repeats[END_REF][START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF], (28, 42, 4), [START_REF] Kolpakov | On maximal repetitions in words[END_REF]32,[START_REF] Crochemore | Transducers and repetitions[END_REF].

Thus we obtain:

Restriction 9. There is a bijection between special sublists of L and cubic runs.

The following algorithm scans the list of cubes and glues together its special sublists into cubic runs, utilizing Observation 9. Due to Theorems 4 and 6, the list L contains all occurrences of all primitively rooted cubes in the word u. In the for-all-loop (lines 6-12) the algorithm glues together cubes forming special sublists of L, thus forming the same cubic run. Hence, the output of the algorithm comprises exactly all the cubic runs in u.

⊓ ⊔

Detecting Runs

In this section we describe a different, however still very simple algorithm which reports all (ordinary) runs in a string u of length n in O(n log n) time. In the following pseudocode, in the for-loop we consider candidates for runs with period per. Verification of existence of runs is performed using the longest common prefix (lcpref in short) and the longest common suffix (lcsuf in short) queries, also called longest common extension queries (see also Fig. 6). Here, lcpref The obtained list of candidates RUNS may contain the same run listed several times and additionally with periods being multiples of its shortest period. Therefore, in the end (lines 11-14) we remove such repetitions, leaving at most one triple (i, j, per) for given i, j, with the smallest corresponding value of period per. if prev = (i, j) then RUNS.delete((i, j, per)); else prev ← (i, j) 15: return RUNS

The following theorem shows correctness of the DetectRuns algorithm, i.e., that it computes exactly all distinct runs in a string.

Theorem 11.

(a) Each run (a, b, q) in the word u is inserted to the list RUNS (line 9) at least once. (b) Every triple (a, b, p) inserted to RUNS in line 9 of the algorithm corresponds to a run (a, b, q) in u with q | p.

Proof. (a) Let a + r, for 0 ≤ r < q, be any of the first q positions of the run. Then, by the definition of a run, the following inequalities hold, see Fig. 6:

lcsuf (a + r, a + r + q) = r + 1 lcpref (a + r, a + r + q) ≥ q -r.
Hence, if per = q and pos = a + r then the condition in line 8 of the algorithm is true and the run (a, b, q) is reported. However, this happens for r ≡ -a (mod per), i.e., in the mth step of the while-loop, where m = ⌈a/per⌉. (b) Clearly any triple (a, b, p) inserted into the list RUNS in line 9 of the algorithm corresponds to an interval [a . . b] in u with period (not necessarily shortest) equal to p and repeating at least twice within the interval, i.e., 2p ≤ ba + 1. Moreover, this interval is not extendable to either side without violating this periodicity.

Let q be the shortest period of the factor u[a . . b]. Note that q | p, since otherwise, by Fine & Wilf's Periodicity Lemma [START_REF] Crochemore | Algorithms on Strings[END_REF][START_REF] Crochemore | Jewels of Stringology[END_REF], gcd(p, q) would be a shorter period of this factor. To show that [a . . b] is a run with period q, it suffices to prove that this interval is not extendable to either size with regard to the period q. for a run (a, b, q) and 0 ≤ r < q Assume to the contrary that the interval is extendable to the left (the other case is analogical). Then we have:

u[a -1] = u[a -1 + q] = u[a -1 + q + (p/q -1) • q] = u[a -1 + p]
and consequently [a . . b] would be extendable to the left w.r.t. the period p, a contradiction.

⊓ [START_REF] Crochemore | Efficient algorithms for two extensions of LPF table: The power of suffix arrays[END_REF]. Techniques used in the efficient implementation of these data structures are rather complex. However, without increasing overall time complexity of the algorithm, we can compute the Suffix Array and preprocess RMQ in O(n log n) time. Hence, we can use much simpler machinery. The Suffix Array of u can be computed in O(n log n) time using DBF(u) -all the suffixes are sorted lexicographically and can be compared in O(1) time using DBF(u). Then, the LCP array can be simply computed in O(n) time using the Suffix Array.

Preprocessing of RMQ data-structure in O(n log n) time resembles computation of DBF a lot. The main difference is that instead of computing ranks of factors we compute positions of minimal elements in ranges. Then, we can find a minimum in the given range by covering the given range by two ranges whose size is a power of two, and comparing their minimal elements. Hence, O(1) query time is preserved.

Thus we obtain O(n log n) preprocessing time and O(1) query time for the lcpref and lcsuf queries, what yields the time complexity of the algorithm specified in the following theorem. ⊓ ⊔

Figure 1 .

 1 Figure 1. Example of DBF computation for word abbaabbabba. Factor abba appears three times in this word and is represented in N ame 2 [ ] by 2.

Lemma 1 .

 1 Having precomputed DBF(u), any two factors of u can be compared in O(1) time.

Figure 2 .

 2 Figure 2. The basic factor cacb of rank t = 2 at position j = 13 generates a cube (cacbcab) 3 starting at position pos = 6. The same cube is generated for t = 3 and j = 13, for the basic factor cacbcabc. a b b a b a a b b a a b a b b a b a a b a b b a a b b a b a a b 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Theorem 4 .

 4 DetectPowers algorithm reports only primitively rooted powers in the word u.

Figure 3 .

 3 Figure 3. Illustration of the proof of Theorem 4; case (a): |z| ≤ |w|, case (b): |z| > |w| .

Figure 4 .

 4 Figure 4. Illustration of the proof of Theorem 5. (a) If posi < 2 t then the occurrences of w at positions i and pos overlap. (b) If pos-i ≥ 2 t then the occurrences of w at positions pos and j overlap.

Figure 5 .

 5 Figure 5. Illustration of the proof of Theorem 6

Algorithm 6 :

 6 DetectCubicRuns(u, n) 1: {list all cubic runs in the word u, |u| = n} 2: L ← DetectPowers(u, n, 3) 3: L.append((-1, -1)) 4: CRUNS ← ∅ 5: prev root ← prev pos ← start ← -1 for all (root, pos) ∈ L do 7: if (root, pos) = (prev root, prev pos + 1) then 8: prev pos ← pos 9: else if start ≥ 0 then 10: CRUNS.insert((start, prev pos + 3 • prev root -1, prev root)) 11: start ← prev pos ← pos 12: prev root ← root 13: return CRUNS Theorem 10. The DetectCubicRuns algorithm computes all cubic runs in a string u of length n in O(n log n) time. Proof. Due to Theorem 7, line 2 of the algorithm runs in O(n log n) time. The time complexity of the rest of the algorithm is + n), where |L| denotes the number of elements in the list L. Time complexity of lines 6-13 is clearly O(|L|). Finally, again due to Theorem 7, |L| = O(n log n), which yields O(n log n) total time complexity of the DetectCubicRuns algorithm.

  (a, b) denotes the length of the longest common prefix of suffixes u[a . . n] and u[b . . n], similarly lcsuf (a, b) denotes the length of the longest common suffix of prefixes u[1 . . a] and u[1 . . b].

Figure 6 .

 6 Figure 6. Graphical interpretation of lcsuf (a+r, a+r+q) and lcpref (a+r, a+r+q) for a run (a, b, q) and 0 ≤ r < q

Theorem 12 .

 12 The time complexity of the DetectRuns algorithm is O(n log n).Proof. For a given value of per, the while-loop performs at most n/per steps, each in constant time. The time complexity of the for-loop is therefore (n log n) and this is also the maximum size of the list RUNS.All remaining operations in the algorithm are: lcpref /lcsuf preprocessing which is performed in O(n log n) time, and sorting and removing duplicates from RUNS, both performed in O(|RUNS|) = O(n log n) time. In total, we obtain the aforementioned time complexity of the algorithm.

  Factors is a simple, yet powerful data-structure. It is widely used in this paper. For a word u of length n, the Dictionary of Basic Factors of u (denoted by DBF(u)) consists of a sequence of arrays N ame t [ ], for 0 ≤ t ≤ ⌊log n⌋. Array N ame t [ ] contains information about factors of u of length 2 t -N ame t [i] contains information about word u[i . . i + 2 t -1], for 1 ≤ i ≤ n -2 t + 1. More precisely, value of N ame t [i] is the rank of u[i . . i + 2 t -1] among other factors of length 2 t . Hence, values of elements of all the arrays N ame t [ ] are in the range from 1 to n. The important property of DBF(u), that we exploit, is that u

  and Table1.

	5:	P rev ← (0, 0, . . . , 0)
	6:	for j ← 1 to n -2 t + 1 do
	7:	name ← N ame t [ j ]
	8:	pos ← P rev[ name ]
	9:	root ← j -pos
	10:	if u[pos . .

Algorithm DetectPowers(u, n, k) 1: {detect kth string powers in a word u, |u| = n} 2: N ame ← DBF(u) 3: POWERS ← ∅ 4: for t ← 0 to ⌊log n⌋ do pos + k • root -1] is (really) a kth power {constant time test due to DBF} then 11: POWERS.insert((root, pos)) 12: P rev[ name ] ← j 13: RadixSort(POWERS) with repetitions removed 14: return POWERS

⊔

  Now let us analyze the time complexity of the algorithm. It mostly depends on the time complexity of the lcpref and lcsuf queries. Their efficient implementation involves the Longest Common Prefix (LCP) and Suffix Arrays (SUF) (computed in O(n) time), and Range Minimum Queries (RMQ) (with O(n) preprocessing time and O(1) query time)

Proceedings of the Prague Stringology Conference 2010

Acknowledgements

The authors thank Tomasz Kociumaka for the idea of the proof of Theorem 6.


Maxime Crochemore

Lucian Ilie ⋆ ⋆ ⋆

Costas S Iliopoulos

Marcin Kubica

Wojciech Rytter

Tomasz Waleń

Computing the Longest Previous Factor ⋆,⋆⋆

Keywords: longest previous factor, suffix array, longest common prefix, Ziv-Lempel factorization, text compression, string repetitions

The Longest Previous Factor array gives, for each position i in a string y, the length of the longest factor (substring) of y that occurs both at i and to the left of i in y. The Longest Previous Factor array is central in many text compression techniques as well as in the most efficient algorithms for detecting motifs and repetitions occurring in a text. Computing the Longest Previous Factor array requires usually the Suffix Array and the Longest Common Prefix array. We give the first time-space optimal algorithm that computes the Longest Previous Factor array, given the Suffix Array and the Longest Common Prefix arrays. We also give the first linear-time algorithm that computes the permutation that applied to the Longest Common Prefix array produces the Longest Previous Factor array.

Introduction

The Longest Previous Factor array gives, for each position i in a string y, the length of the longest factor (substring) of y the occurs both at i and to the left of i in y. For example, for the string y = abbaba, the Longest Previous Factor corresponding to position 3 is 2 because ab is the longest factor at position 3 that appears before (at position 0). The Longest Previous Factor array is central in many text compression techniques as well as in the most efficient algorithms for detecting motifs and repetitions occurring in a text. The problem of computing the Longest Previous Factor array may be regarded as an extension of the Ziv-Lempel factorization (LZ77) of a string as defined in [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF].

The LZ77 factorization is used in several adaptive compression methods which encode carefully re-occurrences of phrases by pointers or integers (see [START_REF] Storer | Data compression via textual substitution[END_REF][START_REF] Witten | Managing Gigabytes[END_REF]). It yields more powerful compressors than the factorization in [START_REF] Ziv | Compression of individual sequences via variable-rate coding[END_REF] (called LZ78) where a phrase is an extension by a single letter of a previous phrase. But the LZ77 factorization is more difficult to compute. One remarkable application of the Longest Previous Factor array is that the LZ77 factorization can be easily computed from it (see [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF]). This implies a linear-time solution for LZ77 factorization on integer alphabets. Previous solutions, using a Suffix Tree [START_REF] Rodeh | Linear algorithm for data compression via string matching[END_REF] or a Suffix Automaton [START_REF] Crochemore | Transducers and repetitions[END_REF] of the string, not only run in time O(n log |A|) (n is the length of the string and |A| is the size of the alphabet) but also the data structures they use are more space-expensive than the Suffix Array which is used for computing the Longest Previous Factor array.

A slight variant of string parsing, whose relation with the LZ77 factorization is analyzed in [START_REF] Berstel | Crochemore factorization of Sturmian and other infinite words[END_REF], plays an important role in String Algorithms. The intuitive reason is that, when processing a string on-line, the work done on an element of the factorization can usually be skipped because it was done already on one of its previous occurrences. A typical application of this idea resides in algorithms to compute repetitions in strings (see [START_REF] Crochemore | Transducers and repetitions[END_REF][START_REF] Main | Detecting leftmost maximal periodicities[END_REF][START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF]). For example, the algorithm in [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF] reports all maximal repetitions (called runs) occurring in a string of length n in O(n log |A|) time. It runs in linear time if a Suffix Array is used instead of a Suffix Tree [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF]. Indeed, this seems to be the only technique that leads to linear-time algorithms, independently of the alphabet size, for this type of question.

The Suffix Arrays provide an ideal data structure to solve many questions requiring an index on all the factors of a string. Introduced by Manber and Myers [START_REF] Manber | Suffix arrays: a new method for on-line string searches[END_REF], the structure can be built in linear-time by different methods [START_REF] Kärkkäinen | Simple linear work suffix array construction[END_REF][START_REF] Kim | Linear-time construction of suffix arrays[END_REF][START_REF] Ko | Space efficient linear time construction of suffix arrays[END_REF][START_REF] Nong | Linear Time Suffix Array Construction Using D-Critical Substrings[END_REF] for sorting the suffixes of the string, possibly adding the method of [START_REF] Kasai | Linear-time longestcommon-prefix computation in suffix arrays and its applications[END_REF] to compute the Longest Common Prefix array. The result holds if the string is drawn from an integer alphabet, that is, if the alphabet of the string can be sorted in linear time (otherwise the Ω(n log n) lower bound for sorting applies).

The notion of Longest Previous Factor has been introduced in [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF], however an array with the same definition appears already in [START_REF] Franek | Computing quasi suffix arrays[END_REF], as part of the concept of a Quasi Suffix Array (their π array is the Longest Previous Factor). In [START_REF] Franek | Computing quasi suffix arrays[END_REF], the authors presented a direct computation running in O(n log n) average time. A naive computation of the Longest Previous Factor array, either on the string itself or on its Suffix Array, as done by the algorithm LPF-naive in Section 5, leads to quadratic effective running time on many inputs.

The first linear-time algorithm for computing the Longest Previous Factor array appears in [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF] where the application to computing the LZ77 factorization (in linear time) is given as well. An improved version, running on-line on the Suffix Array of the string and requiring only

O( √ n)
extra memory space, is shown in [START_REF] Crochemore | A simple algorithm for computing the Lempel-Ziv factorization[END_REF].

In this article we intensively use the Suffix Array of the string to be processed, and we consider only linear-time solutions. A graphical representation of the Suffix Array structure helps understand the design of the algorithms.

We improve on the previous results and show that the computation of the Longest Previous Factor array of a string from its Suffix Array can be implemented to run in linear time with only a constant amount of additional memory space. Thus, the method is time-space optimal.

The next section introduces the necessary material for the design of Longest Previous Factor computations. An algorithm similar to the one of [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF] is described in Section 3. Section 4 shows how the computation can be done on-line on the Suffix Array and Section 5 describes the timespace optimal algorithm for constructing the Longest Previous Factor array. Finally, the Longest Previous Factor array can be obtained as a permutation of the Longest Common Prefix array and we give in Section 6 a linear-time algorithm for that. Alternatively, this an be viewed as a sorting network transforming the Longest Common Prefix array into the Longest Previous Factor array. We conclude by discussing a couple of important research directions.

Basic definitions

We consider a string y of length n over an alphabet A. The ith letter of y is denoted by y

[i] and y[i . . j] = y[i]y[i + 1] • • • y[j].
If, for a string x and two positions i and j in y we have x = y[i . . j], then we say that x occurs at position i in y. We index y's letters from 0 to n-1, that is, y = y[0 . . n-1]. The suffix of y that starts at position i is suf i (y) = y[i . . n -1]. The length of y is denoted by |y| = n.

In the LZ77 factorization, a string y is decomposed into factors, called phrases, u 0 , u 1 , . . . , u k , such that

(i) y = u 0 u 1 • • • u k , (ii) u 0 = y[0] and, (iii) for i ≥ 1, u i is either a new letter or, otherwise, the longest prefix of u i u i+1 • • • u k occurring both at position |u 0 u 1 • • • u i-1
| and before it (that is, to its left) in y; see Example 1.

The Longest Previous Factor array is defined by LPF[0] = 0 and, for 1 ≤ i ≤ n -1, by

LPF[i] = max{k | y[i . . i + k -1] = y[j . . j + k -1], for some 0 ≤ j < i} .
Given the LPF array, the LZ77 factorization is easily computed by the following algorithm (see [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF]): The LPF array corresponding to y is given in the third row of Table 1; the other two arrays, prev and next, will be defined in Section 3. The Suffix Array of the string y is a data structure used for indexing its content. It comprises two arrays that we denote SA and LCP (from Longest Common Prefix) and that are defined as follows.

LZ77(y, LPF) 1 u 0 ← y[0] 2 k ← 0 3 while ((ℓ ← |u 0 u 1 • • • u k |) < n) do 4 u k+1 ← y[ℓ . . ℓ + max{1, LPF[ℓ]} -1] 5 k ← k + 1 6 return u 0 , u 1 , . . . , u k
[i] 0 0 1 3 2 4 3 2 1 4 3 2 2 1 prev[i] -1 -1 1 2 3 4
The array SA stores the list of positions of y associated with the sorted list of its suffixes in increasing lexicographic order. That is, the array is such that

suf SA[0] (y) < suf SA[1] (y) < • • • < suf SA[n-1] (y) .
Thus, SA is indexed by the ranks of the suffixes in their sorted list.

The second array, LCP, is also indexed by the ranks of suffixes and stores the longest common prefixes between consecutive suffixes in the sorted list. Let lcp(i, j) be the longest common prefix of suf i (y) and suf j (y), for two positions i and j of y. Then, LCP[0] = 0 and, for 0 < r < n, we have

LCP[r] = |lcp(SA[r -1], SA[r])|.
We shall use sometimes the array ISA, the inverse of SA, that provides the rank of a position.

Example 2. For our running example y = abaabababbabbb, the SA and LCP arrays are shown in Table 2. It is natural to define the LPF array indexed on positions in the string and the SA and LCP arrays indexes on ranks rather than positions. We show in the last column of Table 2 the LPF array indexed also by rank, that is, LPF[SA [•]]. This duality, of indexing by position or by rank, will appear a number of times throughout the paper.

rank SA[r] suf SA[r] (y) LCP[r] LPF[SA[r]] 0 2 aabababbabbb 0 1 1 0 abaabababbabbb 1 0 2 3 abababbabbb 3
The computation of the Suffix Array can be done in time O(n log n) in the comparison model [START_REF] Manber | Suffix arrays: a new method for on-line string searches[END_REF] (see [START_REF] Crochemore | Algorithms on Strings[END_REF][START_REF] Crochemore | Jewels of Stringology[END_REF][START_REF] Gusfield | Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology[END_REF]). If the string is over an alphabet of integers in the range [0, n c ] for some constant c, then the Suffix Array can be built in time O(n) [START_REF] Kärkkäinen | Simple linear work suffix array construction[END_REF][START_REF] Kim | Linear-time construction of suffix arrays[END_REF][START_REF] Ko | Space efficient linear time construction of suffix arrays[END_REF][START_REF] Nong | Linear Time Suffix Array Construction Using D-Critical Substrings[END_REF] (see also [START_REF] Crochemore | Algorithms on Strings[END_REF]). An elegant algorithm for building the LCP array in linear time is given in [START_REF] Kasai | Linear-time longestcommon-prefix computation in suffix arrays and its applications[END_REF].

Graphic representation

The Suffix Array of the string y has a nice graphic representation that helps understand the algorithms computing the LPF array.

Figure 1 shows the Suffix Array representation for the string y = abaabababbabbb. The abscissa axis refers to ranks of suffixes and the ordinate axis refers to their positions. The sorted list of suffixes is plotted by their positions, and consecutive ranks are linked by an edge whose label is the associated LCP value.

LPF[SA[r]] = max{ |lcp(SA[r], SA[prev[r]])|, |lcp(SA[r], SA[next[r]])| } ,
where undefined LCP values are assumed to be 0. In particular, if a position i is a "peak" at rank r in the graphic representation of the Suffix Array (SA[r] = i) we get

LPF[i] = max{LCP[r], LCP[r + 1]}.
Also, the minimum of the two values is the length of the lcp between positions at ranks r -1 and r +1, if defined, that is, |LCP(SA[r -1], SA[r + 1])|. This gives the idea underlying the algorithm LPF-simple, which is similar to the one of [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF].

LPF-simple(SA, LCP, n) 1 LCP-store ← LCP 2 LCP[n] ← 0 3 ISA ← inverse SA 4 for r ← 0 to n -1 do 5 prev[r] ← r -1 6 next[r] ← r + 1 7 for i ← n -1 downto 0 do 8 r ← ISA[i] 9 LPF[i] ← max{LCP[r], LCP[next[r]]} 10 LCP[next[r]] ← min{LCP[r], LCP[next[r]]} 11 if prev[r] ≥ 0 then 12 next[prev[r]] ← next[r] 13 if next[r] < n then 14 prev[next[r]] ← prev[r] 15 return LPF
The algorithm computes the two arrays prev and next at the same time as computing the LPF array. Steps 9 and 10 implement the earlier discussion and it is enough to explain why the prev and next arrays are correctly computed. The initialization in steps 4-6 gives the correct values for the peaks only. However, in the for cycle at step 7, the peaks are considered in decreasing order of their height (that is, position) and hence the updates in steps 11-14 will provide the correct values.

For instance, the algorithm starts with the highest peak in the graph. The LPF value can already be computed for this position. In Figure 1, the highest peak has position 13 and rank 6, that is, SA[6] = 13. Neighboring positions are lower and therefore prev[6] = 5 and next [START_REF] Crochemore | A simple algorithm for computing the Lempel-Ziv factorization[END_REF] = 7 are correct. Using the above formula for LPF, we have LPF [START_REF] Kim | Linear-time construction of suffix arrays[END_REF] = max{0, 1} = 1. Once this value is set, we remove the node from the graph by adding an edge between its neighbors, 10 and 1, labeled by the minimum of the two LCP values, min{0, 1} = 0. The values next[5] = 7 and prev [START_REF] Crochemore | Jewels of Stringology[END_REF] = 5 are also set, the former being already the correct value (due to the peak position 10 at rank 5).

The algorithm LPF-simple runs in linear time but requires the extra arrays prev, next and ISA in addition to its input and output. Since the LCP array is modified during the algorithm, it can be stored (step 1) in case it is needed later.

Figure 2 illustrates several steps of the algorithm when the input is our running example abaabababbabbb.

Proposition 1. The algorithm LPF-simple computes the LPF array of a string of length n from its Suffix Array in linear time and space. It requires 3n + O(1) integer cells in addition to its input and output.

An alternative algorithm

The array next can alternatively be pre-computed by the following procedure Next whose linear-time behavior is an interesting exercise left to the reader. Only the code in black is needed for the computation of next.

When all code (black and gray) is used, the procedure computes also the array LPF > (defined in [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF]) that is similar with LPF but accounts for larger ranks only. It is defined, for r = 0, . . . , n -1, by Positions 6 and 8 will be linked, through the prev and next arrays on their ranks, with an edge of weight min{4, 1} = 1, which is indeed LPF [START_REF] Franek | Computing quasi suffix arrays[END_REF].

LPF > [r] = |lcp(SA[r], SA[next[r]])|.
Next(SA, LCP,n)

1 next[n -1] ← n 2 LPF > [n -1] ← 0 3 for r ← n -2 downto 0 do 4 t ← r + 1 5 ℓ ← LCP[t] 6 while t < n and SA[t] > SA[r] do 7 ℓ ← min{ℓ, LPF > [t]} 8 t ← next[t] 9 next[r] ← t 10 LPF > [r] ← ℓ 11 return next, LPF >
The computation of the dual prev array is done symmetrically. Also, the array LPF < is symmetrically defined and computed. When both arrays LPF < and LPF > are available, the computation of the LPF array is done using the following equality:

LPF[i] = max{LPF > [r], LPF < [r]}.

On-line computation

Techniques of the previous sections to compute the LPF array are simple but space consuming. In this section and the next one we address this issue. We show that a computation on-line on the Suffix Array using a stack reduces the memory space to only O( √ n) for a string of length n.

This algorithm is similar with the one of [START_REF] Crochemore | A simple algorithm for computing the Lempel-Ziv factorization[END_REF] with some differences in view of our time-space optimal algorithm in the next section.

The design of the on-line computation still relies on the property used for the algorithm of Section 2 and related to "peaks" (see lines 6-8 below). It relies additionally on another straightforward property that we describe now. Assume that a position SA[r] at rank r satisfies LCP[r] ≥ LCP[r + 1]. Then, no position after it in the list can provide a larger LCP value and therefore we get LPF[SA[r]] = LCP[r]. This is implemented in lines 10-11 of the algorithm LPF-on-line.

Note that lines 15 to 18 may be removed from the algorithm LPF-on-line if the Suffix Array can be extended to rank n and initialised to SA[n] = -1 and LCP[n] = 0. But we prefer the present design that is compatible with the algorithm of the next section.

LPF-on-line(SA, LCP, n)

1 EmptyStack(S) The extra memory space used by the algorithm LPF-on-line to compute the LPF array of a string is occupied by the stack and a constant number of integer variables. To evaluate the total size required by the algorithm it is then important to determine the maximal size of the stack for a string of length n. It is proved in [START_REF] Crochemore | A simple algorithm for computing the Lempel-Ziv factorization[END_REF] that this quantity is O(

2 for r ← 0 to n -1 do 3 r-lcp ← LCP[
√ n).
For most values of n there are plenty of strings for which the stack reaches its maximal size. But if n is of the form k(k + 1)/2, that is, if it is the sum of the first k positive integers, then there is a unique string on the alphabet {a, b} (with a < b) giving the maximal size stack. This word is aabab 2 • • • ab k-1 and the maximal stack size is k.

The maximal stack sizes for strings of lengths 4 to 22 are given in Table 3.

Time-space optimal algorithm

In this section we show that the computation of the LPF array of a string can be implemented with only constant memory space in addition to the SA, LCP, and LPF arrays. The underlying property used for this purpose is the O( √ n) stack size reported in the previous section. The property allows an implementation of the stack inside the LPF array for a sufficiently large part of the string. The rest of the computation for the remaining positions is done in a more time-expensive manner but for a small part of the string. This preserves the linear running time of the whole computation.

LPF-optimal(SA, LCP, n) 1 ⊲ it is assumed that n ≥ 8 2 K ← ⌊n -2 √ 2n⌋ 3 ⊲ next three procedures share the same LPF array 4 LPF-on-line(SA, LCP, K) 5 LPF-naive(SA, LCP, K, n) 6 LPF-anchored(SA, LCP, K, n) 7 return LPF It is rather clear that only constant extra memory space is required to implement the strategy retained by the algorithm LPF-optimal. The choice of the parameter K is a result of the previous section and is done to let enough space in the LPF array to implement the stack used by the algorithm LPF-on-line.

Although not done here, the choice of the parameter K can be dynamic and done during the algorithm LPF-on-line as n-2k-1, where k is the size of the stack just before executing line 15. This certainly reduces the actual running time but does not improve its asymptotic evaluation.

In the algorithm LPF-optimal, the stack of the procedure LPF-on-line is implemented in the LPF array. Access to the array is done via the SA array. Doing so, the stack is treated like a continuous space LPF[SA[K . . n-1]]. Elements are stored sequentially so that the elementary stack operations (empty, top, push, pop) are all executed in constant time. Therefore, the running time of the first step is O(n) (indeed O(K)) as for the algorithm LPF-on-line.

Example 3. Table 4 shows the content of the LPF array at two stages of the run of the procedure LPF-on-line on Example 2: (i) immediately after processing rank 5 and (ii) at the end of the first step. The row (i) shows that LPF values of positions 2, 3, 5 at respective ranks 0, 2, 3 have already been computed. The part LPF[SA [8 . . 13]] of the array stores the content of the stack: ((1, 0), (4, 2), [START_REF] Crochemore | LPF computation revisited[END_REF][START_REF] Crochemore | Algorithms on Strings[END_REF]).

The row (ii) shows that values have already been computed for positions at ranks 0 to 6. The content of the stack is ((7, 0), (8, 2)). On this example, K could have been set dynamically to 5.

Naive computation

The second step of the algorithm LPF-optimal processes the Suffix Array from rank K. For each rank r, the values prev[r], next[r] and the corresponding LCP values are computed starting from r and going backward and forward, respectively. The code is given below for the sake of completeness.

LPF-naive(SA, LCP, K, n) 1 LCP[n] ← 0 2 for r ← K to n -1 do 3 left ← LCP[r] 4 s ← r -1 5 while s ≥ K and SA[s] > SA[r] do 6 left ← min{left, LCP[s]} 7 s ← s -1 8 if s = K -1 then 9 left ← 0 10 t ←
((n -K) 2 ), which is O(n) since K = n -2 √ 2n.

Completing the computation

The first two steps of the algorithm LPF-optimal process independently two segments of the Suffix Array. The last step consists in joining their results, which requires updating some LPF values. Indeed, for a rank r, r < K, next[r] can be in [K, n -1], which implies that the computation of LPF[SA[r]] might not be achieved. The same phenomenon happens for a rank in the second part, whose associated prev rank is smaller than K.

The next algorithm updates all LPF values and completes the whole computation. It assumes that the LPF calculation has been done independently on parts LPF[SA[0 . . K -1]] and LPF[SA[K . . n -1]] of the array, which is realised by the first two steps on the algorithm LPF-optimal.

LPF-anchored(SA, LCP, K, n) The running time of this last step LPF-anchored is obviously linear, O(n), as are the other steps of the algorithm LPF-optimal.

1 s ← K -1 2 t ← K 3 ℓ ← LCP[K] 4
The first conclusion of the section is the following statement. The algorithm LPF-optimal uses the Suffix Array of the input string in a read-only manner but does not use the LPF array in a write-only manner. If this last condition is to be satisfied, the question remains of whether there exists a linear-time LPF array construction running with constant extra space. We get this feature if the algorithm LPF-anchored is applied recursively by dividing the Suffix Array into two equal parts. The running time becomes O(n log n) in the model of computation allowing priority writes. Proposition 3. The Longest Previous Factor array of a string of length n on an integer alphabet can be built from its read-only Suffix Array and Longest Common Prefix array in time O(n log n) (independently of the alphabet size) with a constant amount of extra memory space and with a write-only output.

Despite the use of the output as auxiliary storage in the ultimate linear-time algorithm, the series of algorithms described in the article provide a large range of efficient solutions that meet many practical needs.

6 Computing LPF by permuting LCP It has been noticed in [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF] that the content of the LPF array is the same as that of the LCP array up to some permutation. Then the following questions arise:

-Can this permutation be computed efficiently? -Does it depend on the string, its Suffix Array or maybe just its Longest Common Prefix array?

It turns out that, for fixed SA and LCP arrays, it does not depend on the actual string. It is possible to construct such a sorting network, whose shape depends only on the Suffix Array, that transforms the LCP array into the LPF array. This observation leads to the algorithm LPF-by-permuting-LCP, producing LPF by permuting the elements of LCP.

In the algorithm LPF-by-permuting-LCP below we assume that the array next has been pre-computed by the procedure Next from Section 3.1 (in which the gray instructions, related to LPF > , are removed, as well as the parameter LCP).

The array next has been defined as the next rank with a smaller suffix. It helps defining another array, nextPos, that behaves similarly but positions instead of ranks. More precisely, it computes, for each position i, the next closest position nextPos[i] in the Suffix Array that is smaller than i, that is,

nextPos[SA[r]] = SA[min{t | t > r and SA[t] < SA[r]}] = SA[next[r]] .
Equivalently, if we set the position i = SA[r], then

nextPos[i] = SA[next[ISA[i]]] .
Initially, the LPF array is a copy of the LCP array permuted according to the SA array. The algorithm permutes the elements of the array to get the correct LPF array. This involves a modification of the "peaks" idea used previously. If we look again at Figure 1, the highest peak (position 13) has the two adjacent edges labeled 0 and 1. The higher of the two values becomes LPF [START_REF] Kim | Linear-time construction of suffix arrays[END_REF] whereas the smaller one is the length of the lcp between suffixes at ranks 5 and 7. Another way to do this is by permuting the labels 0 and 1 such that each goes to the right place, that is, 1 is on the edge to the left of 13 (and will remain there as the correct LPF value) and 0 goes on the edge to the left of 1, as the new LCP value.

LPF-by-permuting

-LCP(SA, LCP, n) 1 SA[n] ← -1 2 π ← SA 3 for r ← 0 to n -1 do 4 LPF[SA[r]] ← LCP[r] 5 nextPos[SA[r]] ← SA[next[r]] 6 for i ← n -1 downto 0 do 7 if (nextPos[i] ≥ 0) and (LPF[i] < LPF[nextPos[i]]) then 8 Exchange(LPF[i], LPF[nextPos[i]]) 9 π ← π • (LPF[i], LPF[nextPos[i]]) 10 return LPF, π
Note that the algorithm LPF-by-permuting-LCP computes also explicitly the permutation π to transform the LCP array into the LPF array, that is, the permutation that satisfies LPF[π

[i]] = LCP[i].
The final permutation is obtained by composing the SA (which is a permutation) with the transpositions produced in step 8. For our example, this process is shown in Figure 3 The algorithm LPF-by-permuting-LCP uses only one integer array in addition to its input and output since the next array it uses is substituted for the nextPos array. We proved the following result: Theorem 2. The algorithm LPF-by-permuting-LCP computes the LPF array of a string of length n from its Suffix Array in linear time and space. It requires n + O(1) integer cells in addition to its input and output.

Note that the elements of LPF are exchanged (lines 7-9) only if they are not in increasing order. Which elements are compared, depends on values in nextPos, and this in turn depends only on the Suffix Array. So, for a given Suffix Array, one can construct a sorting network implementing lines 6-9 of the algorithm LPF-by-permuting-LCP. Hence, the following proposition holds: Proposition 4. For a given Suffix Array of a string, there exists a sorting network processing a sequence of n numbers in such a way that it transforms the LCP array into the LPF array. Moreover, the shape of the sorting network depends only on the Suffix Array, but not on its LCP array nor on the actual string.

Conclusion

A number of interesting problems remain open. First, it is easy to compute the LZ77 factorization using the LPF array. However, no way of doing the opposite computation is known. The LZ77 factorization contains less information and therefore, it may not be of great use in constructing the LPF array.

Second, our algorithm LPF-optimal is time-space optimal assuming the SA and LCP arrays are used for computing the LPF array. It is of great interest to find fast algorithms that compute the LPF array without such information or, more generally, without using any string indexes.

Example 1 .

 1 For the string y = abaabababbabbb, the LZ77 factorization is y = a.b.a.aba.bab.babb.b .

position i 0 1 2 3 4 5 6 7 8 9

 9 10 11 12 13 y[i] a b a a b a b a b b a b b b LPF

Fig. 1 .

 1 Fig. 1. Graph of the permutation of positions of abaabababbabbb (Example 2) in the lexicographic order of the corresponding suffixes. Labels of edges are Longest Common Prefix lengths between consecutive suffixes.

Fig. 2 .

 2 Fig.2. Illustration of the run of the algorithm LPF-simple on the string abaabababbabbb (see Figure1) after processing positions 13, 12, 11, 10. Gray positions and gray edges are no longer considered. The next step is to process position 9 at rank 10. According to the weights of edges pending from 9, we have LPF[START_REF] Nong | Linear Time Suffix Array Construction Using D-Critical Substrings[END_REF] = max{4, 1} = 4. Positions 6 and 8 will be linked, through the prev and next arrays on their ranks, with an edge of weight min{4, 1} = 1, which is indeed LPF[START_REF] Franek | Computing quasi suffix arrays[END_REF].

Theorem 1 .

 1 The Longest Previous Factor array of a string of length n on an integer alphabet can be built from the read-write Suffix Array and Longest Common Prefix array in time O(n) (independently of the alphabet size) with a constant amount of extra memory space.

Fig. 3 .

 3 Fig. 3. The permutation of LCP that gives LPF, as computed by the algorithm LPF-by-permuting-LCP.

Table 1 .

 1 The LPF, prev, and next arrays for the string y = abaabababbabbb.

	5 1 7 8 9 10 9 12
	next[i] 1 14 7 7 7 7 7 14 14 14 12 12 14 14

Table 2 .

 2 The

	3

SA and LCP arrays for the string y = abaabababbabbb. The last column gives the lpf array indexed by ranks of suffixes instead of positions.

3

  Computing LPF using SA and LCPThe LCP array satisfies the following simple property, a consequence of the lexicographic ordering of suffixes in the SA: the length of the lcp value between two positions at ranks r and t, r < t, that is,|lcp(SA[r], SA[t])| is the minimal value in LCP[r + 1 . . t].For a rank r, let us define prev[r] as the largest rank s < r, for which SA[s] < SA[r], if it exists, and as -1 otherwise. Let us also define the dual notion, next[r], as the smallest rank t > r for which SA[t] < SA[r], if it exists, and as n otherwise. The two arrays prev and next for our running example are shown in Table1.The above property of the LCP array implies that to compute LPF[SA[r]] there is no need to look at ranks smaller than prev[r] or greater than next[r], that is,

Table 3 .

 3 Maximum stack size for various string lengths.

Proposition 2. The algorithm LPF-on-line computes the LPF array of a string of length n from its Suffix Array in linear time and O( √ n) space. It requires less than 2 √ 2n + O(1) integer cells in addition to its input and output.

Table 4 .

 4 The content of the LPF table during the procedure LPF-on-line.

  The process takes O(n-K) time per rank, and hence the total running time of the step is O

		r + 1
	11 12	right ← LCP[t] while t < n and SA[t] > SA[r] do
	13 14 15 16 return LPF t ← t + 1 right ← min{right , LCP[t]} LPF[SA[r]] ← max{left, right }

Acknowledgements

Authors warmly thank German Tischler for his careful inspection of the algorithms described in the article.

⋆ A preliminary version of this paper has been presented at IWOCA'09; see [5]. ⋆⋆ Research supported in part by the Royal Society, UK. ⋆ ⋆ ⋆ Research supported in part by NSERC.

† Supported by grant N206 004 32/0806 of the Polish Ministry of Science and Higher Education.