Maxime Crochemore

Christophe Hancart

Automata for Matching Patterns

Pattern matching and automata

This chapter describes several methods of word pattern matching that are based on the use of automata.

Pattern matching (in words) is the problem of locating occurrences of a pattern in a text le. The le is just a string of symbols, but the pattern can be speci ed in various ways. Here, we only consider patterns described by regular expressions or weaker mechanisms.

. This leads a posteriori to a good solution regarding the e ciency of the algorithms of this chapter. When the text le is static (if it is a dictionary, for example) the preprocessing applied to the text builds an index that can later support e ciently several series of queries (see Section 7).

We present solutions in which the search phase is based on automata as opposed to solutions based on combinatorial properties of words. Thus, the algorithms perform on-line searches with a bu er on the text that does not need to store more than one letter at a time. The solutions are adequate for processing sequential-access les or streams of symbols.

The main algorithms of this chapter solve special instances of the determinization or minimization problems of automata. Basically, given an automaton that recognizes the language X on the alphabet A, algorithms build a deterministic, and sometimes minimal, automaton for the language A X, which is applied afterwards to search e ciently for words of X.

The time complexity of algorithms is given as a function of the input, and is typically linear in the length of the input. This takes into account the set of letters actually occurring in the input. But the running time may depend on the output as well. So, a careful statement of each problem is necessary, to avoid for example quadratic-size outputs that would obviously imply quadratic-time algorithms.

The complexity of algorithms is analyzed in a model of a machine in which the basic operation on letters is comparison in the form less-equal-greater. The implicit ordering on the alphabet is exploited in several algorithms. The assumption on the model makes it possible to process words over a potentially unbounded alphabet. Some algorithms for the simplest pattern-matching problem (searching for only one word) operates in a weaker model (comparison in the form equal-unequal). We also mention how the running times of most algorithms are a ected when branchings in automata are performed by looking up a transition table (see Section 3). This is valid if the alphabet is known in advance and if the letters can be assimilated to indices on a table. Otherwise, a straightforward simulation implies that the running times are multiplied by O(logcard(A)), while in the comparison model the running times of some algorithms are independent of the alphabet.

. The mechanism is one of the basic features of the UNIX operating system and of its tools.

When the language described by the pattern reduces to a nite set of words (Section 5), called a dictionary, the pattern-matching algorithm runs in linear time (on a xed alphabet) instead of quadratic time for the general solution. Moreover, when the pattern is only one word (Section 6), the same running time holds, independently of the alphabet.

The su x automata presented in Section 7 serve as indexes. They provide a solution to the patternmatching instance where the searched text has to be preprocessed. The main point of the section is

the linear-time construction of su x automata (on a xed alphabet), which results partially from their linear size.

The e ciency of pattern-matching algorithms based on automata strongly relies on particular representations of these automata. This is why a review of several techniques is given in Section 3. The regular-expression-matching problem, the dictionary-matching problem, and the string-matching problem are treated respectively in Sections 4, 5, and 6. Section 7 deals with su x automata and their applications.

Notations

This section is devoted to a review of the material used in this chapter: alphabet, words, languages, regular expressions, nite automata, algorithms for matching patterns.

Alphabet and words

Let A be a nite set, called the alphabet. Its elements are called letters, and, for convenience, we denote them by a, b, c, and so on. Furthermore, we assume that there is an ordering on the alphabet.

A word is a nite-length sequence of letters. The length of a word u is denoted by juj, and its j-th letter by u j . The set of all words is denoted by A , the empty word by ", and A + stands for A nf"g.

The product of two words u and v, denoted by u v or uv, is the word obtained by writing sequentially the letters of u then the letters of v. Given a word u, the product of k words identical with u is denoted by u k , setting u 0 = ". Denoted respectively by uw 1 and v 1 u are the words v and w when u = vw.

A word v is said to be a factor of a word u if u = u 0 vu 00 for some words u 0 and u 00 ; it is a proper factor of u if v 6 = u, a pre x of u if u 0 = ", and a su x of u if u 00 = ".

Languages

A language is any subset of A . The product of two languages U and V , denoted by U V or UV , is the language fuv j (u; v) 2 U V g. Denoted by U k is the set of words obtained by making products of k words of U. The star of U, denoted by U , is the language S k>0 U k . By convention, the order of decreasing precedence for language operations in expressions denoting languages is star or power, product, union. By misuse, a language reduced to only one word u may be denoted by u itself if no confusion arises (with further notations).

The sets of pre xes, of factors, and of su xes of a language U are denoted respectively by Pref (U), Fact(U), and Su (U). If U is nite, jU j stands for P u2U juj (therefore, note that card(A) = jAj). The right context of a word u according to a language W is the language fu 1 w j w 2 Wg. The equivalence generated over A by the relations u 1 W = v 1 W; u; v 2 A is denoted by W ; it is the right syntactic congruence associated with the language W.

Regular expressions

Regular expressions and the languages they describe, the regular languages, are de ned inductively as follows:

{ 0, 1, and a are regular expressions and describes respectively ? (the empty set), f"g, and fag, for each a 2 A; { if u and v are regular expressions describing respectively the regular languages U and V , then u + v, u v, and u are regular expressions describing respectively the regular languages U V , U V , and U .

By convention, the order of decreasing precedence for operations in regular expressions is star ( ), product ( ), sum (+). The dot is often omitted. Parenthesizing can be used to change the precedence order of operators.

The language described by a regular expression u is denoted by Lang(u). The length juj of a regular expression u is the length of u reckoned on the alphabet A f0; 1; +; g (parentheses and product operator are not reckoned).

Finite automata

A ( nite) automaton (with one initial state) is given by a nite set Q, whose elements are called states, an initial state i, a subset T Q of terminal states, and a set E Q A Q of edges.

An edge (p; a; q) of the automaton (Q; i; T; E) is an outgoing edge for state p and an ingoing edge for state q; state p is the source of this edge, letter a its label, and state q its target. The number of edges outgoing a state p is called the (outgoing) degree of p. We say that there is a path labeled by u from state p to state q if there is a nite sequence (r j 1 ; a j ; r j ) 16j6n of edges such that n = juj, a j = u j for each j 2 f1; : : :; ng, r 0 = p and r n = q. One agrees to de ne a unique path labeled by " from each state p to itself.

A word u is recognized by the automaton A = (Q; i; T; E) if there exists a path labeled by u from i to some state in T. The set of all words recognized by A is denoted by Lang(A). A language X is recognizable if there exists an automaton A such that X = Lang(A).

As an example, the automaton depicted in Figure 2.1 recognizes the language fa; bg abaaab. Its initial state is 0, and its only terminal state is 6. The automaton (Q; i; T; E) is deterministic if for each (p; a) 2 Q A there is at most one state q such that (p; a; q) 2 E. It is complete if for each (p; a) 2 Q A there is at least one state q such that (p; a; q) 2 E. It is normalized if card(T ) = 1, the initial state has no ingoing edge, and the terminal state has no outgoing edge. It is minimal if it is deterministic and if each deterministic automaton recognizing the same language maps onto it; it has the minimalnumber of states. The minimal automaton recognizing the language U is denoted by M(U). It can be de ned with the help of right contexts by: u 1 U j u 2 A ; U ; u 1 U j u 2 U ; (u 1 U; a; (ua) 1 U) j u 2 A ; a 2 A In case A = (Q; i; T; E) is a deterministic automaton, it is convenient to consider the transition function : Q A ! Q of A de ned for each (p; a) 2 Q A such that there is an outgoing edge labeled by a for p by (p; a) = q () (p; a; q) 2 E (notice that is a partial function). Equivalently, the quadruple (Q; i; T; ) denotes the automaton A.

In a natural way, the transition function extends to a function mapping from Q A to Q and also denoted by setting (p; u) = 8 > < > : p; if u = ", ( (p; a); v); if (p; a) is de ned and u = av for some (a; v) 2 A A , unde ned; otherwise, for each (p; u) 2 Q A .

In algorithms that manipulate automata, we constantly use the function State-Creation described in Figure 2.2 (+ stands for the union of sets). This avoids going into details of the implementation of automata that is precisely the subject of Section 3.

State-Creation 1 chose a state q out of Q 2 Q Q + fqg 3 return q Fig. 2.2. Creation of a new state and adjunction to the set of states Q.

Algorithms for matching patterns

The pattern matching problem is to search and locate occurrences of patterns in words (or textual data, less formally speaking). A pattern represents a language and is described either by a word, by a nite set of words, or more generally, by a regular expression. We do not consider patterns described by other mechanisms.

Let y be the searched word. An occurrence in y of a pattern represented by the language X is a triple (u; x; v) where u; v 2 A , x 2 X, and such that y = uxv. The position of the occurrence (u; x; v) of x in y is the length juj; it is sometimes more convenient to consider the end-position of the same occurrence, which is de ned as the length juxj. Observe that searching y for words in a language X is equivalent to search for pre xes of y that belong to the language A X; the language of most automata considered in this chapter is of this form.

According to a speci c matching problem, the input of an algorithm is a language X described by a word, by a nite set of words, or by a regular expression, and a word y. The output can have several forms. To implement an algorithm that tests whether the pattern occurs in the word or not, the output is just the boolean value true or false respectively. In an on-line search, what is desired is the word, say z, on the alphabet f0; 1g that encodes the existence of end-positions of the pattern; the length of z is jyj + 1, and its j + 1-th letter is 1 exactly when an occurrence of the pattern ends at position j in y. The output can also be the set, say P, of positions (or end-positions) in y of the pattern. To avoid presenting several variants of algorithms, we introduce the statement occurrenceif e where e is an appropriate predicate. It can be translated by if e then return true in the rst case, if e then z z 1 else z z 0 in the second case, and if e then P P + fthe current position in yg Matcher(X;y)

Preprocessing phase 1 built an automaton (Q; i; T; E) recognizing A X Search phase let be the transition function of (Q; i; T; E) 2 p i 3 occurrenceif p 2 T 4 for letter a from rst to last letter of y 5 loop p (p; a) 6 occurrenceif p 2 T Fig. 2.3. Given a regular language X and a word y, locate all occurrences of words in X that are factors of y.

in the third case. In the rst case, the \return false" statement has to be included correspondingly at the end of the algorithm; and in the other cases, word z and set P should be initialized at the beginning of the algorithm and returned at the end of the algorithm. From now on, the standard algorithm for matching patterns in words can be written as in Figure 2.3.

The asymptotic time and space complexities of algorithm Matcher depend on the representation of the automaton, and more speci cally, on the representation of the transition function (see Section 3). More generally, the complexities of algorithms, functions or procedures developed in this chapter are expressions of the size of the input. They include the size of the language, the length of the searched word, and the size of the alphabet. We assume that the \occurrenceif e" statement is performed in constant time. Nevertheless, an ad hoc output often underlies the complexity result.

Representations of deterministic automata

Several pattern matching algorithms rely on a particular representation of the deterministic automaton underlying the method. Implementing a deterministic automaton (Q; i; T; E) remains to implement the transition function of the automaton, which is the general problem of realizing partial functions. Five methods are described in this section: transition matrix, adjacency lists, transition list, failure function, and table-compression.

The choice of the representation of the automaton in uence the time needed to compute a transition, i.e. the time to evaluate (p; a), for any state p and any letter a. This time is called the delay, in that it is also the time spent on letter a before moving to the next letter of the input word. Basically: on the one hand, the time to evaluate (p; a) is constant in a model where branchings are allowed and a transition matrix implements ; on the other hand, if comparison of letters is the only operation allowed on them, the time to evaluate (p; a) is O(log card(A)), assuming that any two letters can be compared in one unit of time (using binary operations =, 6 =, < or >). In the following, we give the memory space and the delay associated to each type of representation. There is an obvious trade-o between these two quantities.

In the chapter, having a representation R of the transition function , the automaton is indi erently denoted by (Q; i; T; E), (Q; i; T; ), and (Q; i; T; R).

Transition matrix

The simplest method to implement the transition function is to store its values in a Q A-matrix. This is a method of choice for a complete deterministic automaton on a small alphabet and when letters can be assimilated to indices on an array. The space required is O(card(Q) card(A)) and the delay is O [START_REF] Aho | Algorithms for nding patterns in strings[END_REF].

When the automaton is not complete, the representation still works except that the searching procedure can stop on an unde ned transition. The matrix can even be initialized in time proportional to the number of edges of the automaton with the help of a sparse matrix representation technique. The above complexities are still valid in this situation.

This kind of representation implicitly assumes that the working alphabet is xed and known by advance. This contrasts with the representations of Sections 3.2 and 3.4 for which the basic operation on the alphabet is comparing letters.

Adjacency lists

A traditional way of implementing graphs is to use adjacency lists. This applies to automata as well. Doing so, the set of couples (a; (p; a)), whenever (p; a) is de ned, is associated with each state p 2 Q. The space required to represent the card(Q) adjacency lists of the automaton is O(card(Q) + card(E)). Contrary to the previous method, this one works even if the only possible elementary operation on letters is comparison. Denoting by d the maximum degree of states of the automaton, the delay is O(log d), which is also O(logminfcard(Q); card(A)g), using an e cient implementation of sets based for instance on balanced trees.

The space complexity may be further reduced by considering a default (target) state associated to each adjacency list (the most frequently occurring target of a given adjacency list is an obvious choice as default for this adjacency list). The delay can even be improved at the same time because adjacency lists become smaller.

When implementing the automaton, each adjacency list is stored in an array G indexed by Q. If the deterministic automaton is complete and if the initial state i is the uniform default state (i as default state ts in perfectly with pattern matching applications), the computation of a transition from any state p by any letter a, that is, the computation of (p; a), is done by the function of Figure 3

Transition list

The transition list method consists in implementing the list of triples (p; a; q) of edges of the automaton. The space required by the implementation is only O(card(E)). Doing so, it is assumed that the list is stored in a hashing table to provide fast computations of transitions. The corresponding hashing function is de ned on couples (p; a) from Q A. Then, given a couple (p; a), the access to the transition (p; a; q), if it appears in the list, is performed in constant time on the average under usual hypotheses on the technique.

Failure function

The main idea of the failure function method is to reduce the space needed by , by deferring, in most possible cases, the computation of the transition from the current state to the computation of the transition from an other given state with the same input letter. It serves to implement deterministic automata in the comparison model. Its main advantage is that, in general, it provides a linear-space representation, and, simultaneously, gives a linear-time cost for a series of transitions, though the time to compute one transition is not necessarily constant.

We only consider the case where the deterministic automata is complete and where i is the default state (extensions of the following statement are not needed in the chapter).

Let be a function from Q A to Q, and let f be a function from Q into itself. We say that the couple ( ; f) represents the transition function if is a subfunction of and if (p; a) = are respectively said to be a subtransition function and a failure function, according to . However, this representation is correct if we assume that f de nes an order on Q.

Assuming a representation of by adjacency lists, the space needed to represent by the couple ( ; f) is O(card(Q) + card(E 0 )), where E 0 = f(p; a; q) j (p; a; q) 2 E and (p; a) is de nedg); which is of course O(card(Q) + card(E)) since E 0 E. (Notice that is the transition function of the automaton (Q; i; T; E 0 ).) If d is the maximum degree of states of the automaton (Q; i; T; E 0 ), the delay is typically O(card(Q) log d), that is also O(card(Q) log card(A)).

When implementing the automaton, the values of the failure function f are stored in an array F indexed by Q. The computation of a transition is done by the function of Figure 3.2. The function always stops if we assume that f de nes an order on Q.

Table-compression

The latest method is a mix of the previous ones that provides fast computations of transitions via arrays and a compact representation of edges via failure function.

Four arrays, denoted here by fail, base, target, and check, are used. The fail and base arrays are indexed by Q, and, for each (p; a) 2 Q A, base p]+a is an index on target and check arrays, assimilating letters to integers. The computation of the transition from some state p with some input letter a proceeds as follows: let k = base p] + a; then, if check k] = p, target k] is the target of the edge of source p and label a; otherwise, this statement is repeated recursively with state fail p] and letter a. (Notice that it is correct if fail de nes an order on Q, as in Section 3.4, and if the targets from the smallest element are all de ned.) The corresponding function is given in Figure 3.3. In the worst case, the space needed is O(card(Q) card(A)) and the delay is O(card(Q)). However the method can reduce the space to O(card(Q)+card(A)) with an O(1) delay in best possible situation. A well-known solution to the above problem is composed of two phases. First, transform the regular expression x into a nondeterministic automaton that recognizes the language described by x, following a construction due to Thompson. Second, simulate the obtained automaton with input word y in such a way that it recognizes each pre x of y that belongs to A Lang(x).

Main Theorem 4.1. The regular expression-matching problem for x and y can be achieved in the following terms: { a preprocessing phase on x building an automaton of size O(jxj), performed in time O(jxj) and O(jxj) extra-space; { a search phase executing the automaton on y performed in time O(jxj jyj) and O(jxj) space, the time spent on each letter of y being O(jxj).

The construction of the automaton is given in Section 4.2. In Section 4.3, we rst show how to solve the membership test, namely, \does y belongs to Lang(x)?"; we then present the solution to the search phase of the regular-expression-matching problem as a mere transformation of the previous test. Finally, in Section 4.4, we discuss a possible use of a deterministic automaton to solve the problem.

In the whole section, we assume that the regular expression contains no redundant parentheses, because otherwise the parsing of the expression would not be necessarily asymptotically linear in the length of the expression.

Regular-expression-matching automata

In order to solve the problem in space linear in the length of the regular expression, we consider special nondeterministic automata.

We say that an automaton is extended if it is de ned on the extended alphabet A f"g. Observe that a transition from a state to another in an extended automaton may either result of the reading of a letter from the input word, or not ("-transition). Theorem 4.2. Let x be a regular expression. There exists a normalized extended automaton recognizing Lang(x) satisfying the following conditions:

(i) the number of states is bounded by 2jxj; (ii) the number of edges labeled by letters of A is bounded by jxj, and the number of edges labeled by " is bounded by 4jxj; (iii) for each state the number of ingoing or outgoing edges is at most 2, and it is exactly 2 only when the edges are labeled by ". Proof. The proof is by induction on the length of regular expressions.

The regular expressions of length equal to 1 are 0, 1, and a, for each a 2 A. Now, let (Q 0 ; i 0 ; ft 0 g; E 0 ) and (Q 00 ; i 00 ; ft 00 g; E 00 ) be normalized extended automata recognizing respectively the regular expressions u and v, assuming that Q 0 \ Q 00 = ?. (II) Fig. 4.2. Normalized extended automata recognizing the regular expressions u + v (I), u v (II), and u (III), obtained from normalized extended automata (Q 0 ; i 0 ; ft 0 g; E 0 ) and (Q 00 ; i 00 ; ft 00 g; E 00 ) recognizing respectively the regular expressions u and v.

The above construction clearly proves the existence of a normalized extended automaton recognizing the language described by any given regular expression. It remains to check that the automaton satis es conditions (i) to (iii). Condition (i) holds since exactly two nodes are created for each letter of a regular expression accounting for its length. Condition (ii) is easy to establish, using similar arguments. And the last condition follows from construction. u t

The previous result proves one half of the theorem of Kleene (the second half of the proof may be found in any standard textbook on automata or formal language theory). Theorem 4.3 (Kleene, 1956). A language is recognizable if and only if it is regular.

We denote by E (x) the normalized extended automaton constructed in the proof of Theorem 4.2 from the regular expression x, and we call it the regular-expression-matching automaton of x.

To evaluate the time complexity of the above construction, it is necessary to give some hints about the data structures involved in the representation of regular-expression-matching automata. Due to the conditions stated in Theorem 4.2, a special representation of regular-expression-matching automata is possible providing an e cient implementation of the construction function. States are simply indices on an array that store edges; each cell of the array has to store at most two edges whose ingoing state is its index. Indices of the initial state and of the terminal state are stored separately. This shows that the space required to store E (x) is linear in its number of states, which is linear in the length of x according to Theorem 4.2.

Hence, each of the operations induced by +, or can be implemented to work in constant time. This proves that the time spent on each letter of x is constant. In addition, the function which builds the regular-expression-matching automaton corresponding to a given regular expression is driven by a parser of regular expressions. Then, if parenthesizing in x is not redundant, the time and the space needed for the construction of E (x) is linear in the length of x.

We have established the following result:

Theorem 4.4. Let x be a regular expression. The space needed to represent E(x) is O(jxj). The computation of the automaton is performed in time and space O(jxj).

Searching with regular-expression-matching automata

The search for end-positions of words in Lang(x) is performed with a simulation of a deterministic automaton recognizing A Lang(x). Indeed, the determinization is avoided because it may lead to an automaton with a number of states which is exponential in the length of the regular expression (see Section 4.4). But the determinization via the subset construction is just simulated: at a given time, the automaton is not in a given state, but in a set of states. This subset is recomputed whenever necessary in the execution of the search.

As for the determinization of automata with "-transitions, the searching procedure needs the notion of closure of a set of states: if S is a set of states, its closure is the set of states q such that there exists a path labeled by " from a state of S to q. From the closure of a set of states, it is possible to compute e ectively the transitions induced by any input letter.

The simulation of a regular-expression-matching automaton consists in repeating the two operations closure and computation of transitions on a set of states. for each state q such that (p; "; q) is in E 8 loop if q is not in R 9 then R R + fqg 10 Enqueue(#; q) 11 return R Fig. 4.3. Computation of the closure of a set S of states, with respect to a set E of edges.

Transitions(E; S; a) 1 R ? 2 for each state p in S 3 loop for each state q such that (p; a; q) is in E 4 loop R R + fqg 5 return R Fig. 4.4. Computation of the transitions by a letter a from states of a set S, with respect to a set E of edges.

A basic use of an automaton consists in testing whether it recognizes some given word. Testing whether y is in the language described by x is implemented by the algorithm of Figure 4.5. The next proposition states the complexity of such a test. Proposition 4.1. Given a regular expression x, testing whether a word y belongs to Lang(x) can be performed in time O(jxj jyj) and space O(jxj).

Proof. The proof is given by algorithm Tester of Figure 4.5 for which we analyze the complexity.

According to Theorem 4.4, the regular-expression-matching automaton (Q; i; ftg; E) of x can be built in time and space O(jxj).

Each computation of functions Closure and of Transitions requires time and space O(card(Q)), which is O(jxj) from Theorem 4.2. This is repeated jyj times. This gives O(jxj jyj) time. We now come back to our main problem. It is slightly di erent than the previous one, because the answer to the test has to be reported for each factor of y, and not only on y itself. But no transformation of E (x) is necessary. A mere transformation of the search phase of the algorithm is su cient: at each iteration of the closure computation, the initial state is integrated to the current set of states. Doing so, each factor of y is tested. Moreover, the \occurrenceif t 2 C" instruction is done at each stage. The entire algorithm is given in

Time-space trade-o

The regular-expression-matching problem for a regular expression x and a word y admits a solution based on deterministic automata. It proceeds as follow: build the automaton E (x); built an equivalent deterministic automaton; search with the deterministic automaton. The drawback of this approach is that the deterministic automaton can have a number of states exponential in the length of x. This is the situation, for example, when

x = a m 1 times z }| { (a + b) (a + b)
for some m > 1; here, the minimal deterministic automaton recognizing A Lang(x) has exactly 2 m states since the recognition process has to memorize the last m letters read from the input word y. However, all states of the deterministic automaton for A Lang(x) are not necessarily met during the search phase. So, a lazy construction of the deterministic automaton during the search is a possible compromise for practical purposes.

Matching nite sets of words

5.1 Outline Problem 5.1. (Dictionary-matching problem.) Given a nite set of words X, the dictionary, preprocess it in order to locate words of X that occur in any given word y.

The classical solution to this problem is due to Aho and Corasick. It essentially consists in a linearspace implementation of a complete deterministic automaton recognizing the language A X. The implementation uses both adjacency lists and an appropriate failure function.

Main Theorem 5.1 [START_REF] Aho | E cient string matching: an aid to bibliographic search[END_REF]. The dictionary-matching problem for X and y can be achieved in the following terms: { a preprocessing phase on X building an implementation of size O(jXj) of an automaton recognizing A X, performed in time O(jXj logcard(A)) and O(card(X)) extra-space; { a search phase executing the automaton on y performed in time O(jyj log card(A)) and constant extra-space, the delay being O(jXj logcard(A)).

If we allow more extra-space, the asymptotic time complexities can be reduced. This is achieved, for instance, by using techniques of Section 3 for representing deterministic automata with a sparse matrix, and assuming that O(jXj card(A)) space is available. The time complexities of the preprocessing and search phases are respectively reduced to O(jXj) and O(jyj), and the delay to O(jXj). Nevertheless, notice that the times complexities given in the above theorem are still linear in jXj or jyj if we consider xed alphabets.

The method behind Theorem 5.1 is based on a speci c automaton recognizing A X: its states are the pre xes of words in X (their number is nite as X is). The automaton is not minimal in the general case. It is presented in Section 5.2, and its implementation with a failure function is given in Section 5.3. Section 5.4 is devoted to the search for X with the automaton.

Dictionary-matching automata

We give a complete deterministic automaton that recognizes A X. In order to formalize this automaton, we introduce for each language U the mapping h U : A ! Pref (U) de ned for each word v by h U (v) = the longest su x of v that belongs to Pref (U): (In the whole Section 5, U refers to an ordinary language, and X refers to a nite language.) Proposition 5.1. Let X be a nite language. Then the automaton Pref (X); "; Pref (X) \ A X; (p; a; h X (pa)) j p 2 Pref (X); a 2 A recognizes the language A X. This automaton is deterministic and complete.

In the following, we denote by D(X) the automaton of Proposition 5.1 applied to X, and we call it the dictionary-matching automaton of X.

The proof of Proposition 5.1 relies on the following result.

Lemma 5.1.

Let U A . Then (i) v 2 A U i h U (v) 2 A U, for each v 2 A . Furthermore, h U satis es the relations: (ii) h U (") = "; (iii) h U (va) = h U (h U (v)a), for each (v; a) 2 A A.
Proof. If v 2 A U, then v is in the form wu where w 2 A and u 2 U; by de nition of h U , u is necessarily

a su x of h U (v); therefore h U (v) 2 A U. Conversely, if h U (v) 2 A U, we have also v 2 A U, because h U (v) is a su x of v. Which proves (i).
Property (ii) clearly holds. It remains to prove (iii). Both words h U (va) and h U (v)a are su xes of va, and therefore one of them is a su x of the other. Then we distinguish two cases according to which word is a su x of the other.

First case: h U (v)a is a proper su x of h U (va) (hence h U (va) 6 = "). Consider the word w de ned by w = h U (va)a 1 . Thus we have: h U (v) is a proper su x of w, w is a su x of v, and since h U (va) 2 Pref (U), w 2 Pref (U). Whence w is a su x of v that belongs to Pref (U), but strictly longest than h U (v). This contradicts the maximality of jh U (v)j. So this case is impossible.

Second

case: h U (va) is a su x of h U (v)a. Then, h U (va) is a su x of h U (h U (v)a). Now, since h U (v)a is a su x of va, h U (h U (v)a) is a su x of h U (va). Both properties implies h U (va) = h U (h U (v)a)
, and the expected result follows. u t Proof of Proposition 5.1. Let v 2 A . It follows from properties (ii) and (iii) of Lemma 5.1 that h X (v 1 v 2 v j 1 ); v i ; h X (v 1 v 2 v j ) 16j6jvj is a path labeled by v from the initial state " to the state h X (v).

If v 2 A X, we get h X (v) 2 A X from (i) of Lemma 5.1; which shows that h X (v) is a terminal state, and nally that v is recognized by the automaton.

Conversely, if v is recognized by the automaton, we have h X (v) 2 A X by de nition of the automaton. This implies that v 2 A X from (i) of Lemma 5.1 again. u t

We show how to implement the automaton D(X ) in the next section.

Linear dictionary-matching automata

The automaton D(X ) is implemented with a failure function. The aim is to get a representation that does not depend on the size of the alphabet.

For each language U, let f U : Pref (U) ! Pref (U) be the function de ned for each nonempty word u in Pref (U) by f U (u) = the longest proper su x of u that belongs to Pref (U):

Lemma 5.2. Let U A . For each (u; a) 2 Pref (U) A, we have:

h U (ua) = 8 < : ua; if ua 2 Pref (U), h U (f U (u)a); if u 6 = " and ua 6 2 Pref (U), "; otherwise.
Proof. The identity clearly holds when ua 2 Pref (U) or when ua 6 2 Pref (U) but u = ".

It remains to examine the case where ua 6 2 Pref (U) and u 6 = ". Here, f U (u)a is a proper su x of ua. What is more, h U (f U (u)a) is the longest su x of ua that belongs to Pref (U). Indeed, if we assume the existence of a su x v of ua satisfying v 2 Pref (U) and jvj > jf U (v)aj, we get that va 1 is a proper su x of u belonging to Pref (U); then va 1 = f U (u) because of the maximality of jf U (u)j. Which achieves the proof.

u t

We introduce for each language U the function U : Pref (U) A ! Pref (U) associating with each (u; a) 2 Pref (U) A such that ua 2 Pref (U) the word ua. Thus, with conventions of Section 3.4, we have: Proposition 5.2. For each nite language X, the couple ( X ; f X ) represents the transition function of D(X ); function X is a subtransition function and function f x a failure function, according to the transition function of D(X ). Proof. Follows from Lemma 5.2. u t Now, let us observe that function X is exactly the transition function of the deterministic automaton Pref (X); "; X; (p; a; pa) j p 2 Pref (X); a 2 A; pa 2 Pref (X) : This automaton recognizes the language X, and is classically called the trie of X, as a reference to \information retrieval". It is built by function Trie of Figure 5.1. Proposition 5.3. Function Trie applied to any nite language X builds the trie of X. If the edges of the automaton are implemented via adjacency lists, the size of the trie is O(jXj), and the construction is performed in time O(jXj log d) within constant extra-space, d being the maximum degree of states. When X = fab; babb; bbg, the trie of X is as depicted in Figure 5.2. This example shall be considered twice in the following.

To achieve the goal of implementing D(X) in linear size, we use Proposition 5.2. Then, it remains to give methods for computing f X and for marking the set of terminal states. This can be done by a breadth rst search on the graph underlying the trie starting at the initial state, as shown by the two following lemmas. Lemma 5.3. Let U A . For each (u; a) 2 Pref (U) A, we have: f U (ua) = h U (f U (u)a); if u 6 = ", ";

otherwise.

Proof. Similar to the proof of Lemma 5.2. u t Lemma 5.4. Let U A . For each u 2 Pref (U), we have: u 2 A U () (u 2 U) or (u 6 = " and f U (u) 2 A U):

Proof. It is clearly su cient to prove that u 2 (A U)nU =) f U (u) 2 A U: So, let u 2 (A U)nU.
The word u is in the form vw where v 2 A and w is a proper su x of u belonging to U. Then, by de nition of f U , w is a su x of f U (u). Therefore f U (u) 2 A U. Which ends the proof. u t The complete function constructing the representation of D(X) with the subtransition X and the failure function f X is given in Figure 5.3. Let us recall that the transition function of D(X) is assumed to be computed by function FailureFunction-Transition of Section 3.4. The next theorem states the correctness of the construction and its time and space complexities. We call this representation of D(X) the linear dictionary-matching automaton of X. The term \linear" (in jXj is understood) is suitable if we work with a xed alphabet, since degrees are upper-bounded by card(A). LinearDictionaryMatchingAutomaton(X) let be the transition function of (Q; i; T; E 0 ) let be the transition function of (Q; i; T; ( ; F )) 1 (Q; i; T; E 0 ) Trie(X) 2 F i] nil 3 # EmptyQueue 4 Enqueue(#; i) 5 while not QueueIsEmpty(#) 6 loop p Dequeue(#) 7

for each letter a such that (p; a) 6 = nil 8 loop q (p; a) 9

F q] (F p]; a) 10 if F q] is in T 11 then T T + fqg 12 Enqueue(#; q) 13 return (Q; i; T; ( ; F )) Fig. 5.3. Construction of the linear dictionary-matching automaton of a nite set of words X.

Theorem 5.2. The linear dictionary-matching automaton of any nite language X is built by function LinearDictionaryMatchingAutomaton. The size of this representation of D(X) is O(jXj). The construction is performed in time O(jXj log d) within O(card(X)) extra-space, d being the maximum degree of states of the trie of X.

Proof. The correctness of the function and the order of the size of the representation is consecutive to Propositions 5.1, 5.2, and 5.3, and Lemmas 5.2, 5.3, and 5.4. The extra-space is linear in the size of the queue #, which has always less than card(X) elements.

In order to prove the announced time complexity, we shall see that the last test of the loop of function FailureFunction-Transition (for computing (F p]; a); see Section 3.4) is executed less than 2jXj times. To avoid ambiguity, the state variable p of function FailureFunction-Transition is renamed r.

First. We remark that less tests are executed on the trie than if the words of X were considered separately.

Second. Considering separately each word x of X, and assimilating variables p and r with the pre xes of x they represent, the quantity 2jpj jrj grows of at least one unity between two consecutive tests \ (r; a) = nil". When jxj 6 1, no test is performed. But when jxj > 2, this quantity is equal to 2 before the execution of the rst test (jpj = 1, jrj = 0), and is less than 2jxj 2 after the execution of the last test (jpj = jxj 1, jrj > 0); which shows that less than 2jxj 3 tests are executed in this case.

This proves the expected result on the number of tests. Now, since each of these tests is performed in time O(log d), the loop of lines 5{12 of function LinearDictionaryMatchingAutomaton is performed in time O(jXj logd). This is also the time complexity of the whole function, since line 1 is also performed in time O(jXj logd) according to Proposition 5.3. u t Figure 5.4 displays the linear dictionary-matching automaton of X when X = fab; babb; bbg. The failure function f X is depicted with non-labeled discontinuous edges. To be complete, we add that f U can be expressed independently of h U for any language U. Lemma 5.5. Let U 2 A . For each (u; a) 2 Pref (U) A, we have:

f U (ua) = 8 < : f U (u)a;
if u 6 = " and ua 2 Pref (U), f U (f U (u)a); if u 6 = " and ua 6 2 Pref (U), ";

if u = ". Proof. This follows from Lemmas 5.2 and 5.3.

u t

However interesting this result is, it does not lead to another computation of linear dictionarymatching automata than the computation performed by the function of Figure 5.3.

Searching with linear dictionary-matching automata

We prove in this section that matching a nite set of words can be performed in linear time on xed alphabets. This is stated in the following theorem.

Theorem 5.3. Let X be a nite set of words and y be a word. Let `be the maximum length of words of X and d be the maximum degree of states of the trie of X. Using the linear dictionary-matching automaton of X, searching for all occurrences of words of X as factors of y (search phase of algorithm Matcher) is performed in time O(jyj logd), constant extra-space, within a delay of O(` log d).

Proof. The proof is similar to the proof of Theorem 5.2.

Here, instead of the quantity 2jpj jrj, we consider the quantity 2jy 0 j jpj where y 0 is the already read pre x of y. We obtain that less than 2jyj 1 tests \ (p; a) = nil" are executed. This proves that the total time is O(jyj log d). For the delay, the test \ (p; a) = nil" cannot be executed strictly more than `times on each input letter a, which gives a time O(` log d).

u t

The search phase can be improved to prevent unnecessary calls to the failure function as far as it is possible.

Assume for instance that during the search state 5 of Figure 5.4 has been reached, and that the next letter of the input word, say c, is not b. The failure function has to be iterated at least twice since neither X (5; c) nor X (2; c) are de ned. It is clear that the test on state 2 is useless, whatever c is. The next attempt is to compute X (3; c). Here, state 3 plays its role because c might be equal to a. But now, if X (3; c) is unde ned, it is needless to iterate again the failure function on state 0, since c is then neither a nor b.

Following a similar reasoning for each states of the linear dictionary-matching automaton of X when X = fab; babb; bbg leads to consider the representation depicted in Figure 5.5. More generally, given a nite language X and the failure function f X , the representation of D(X) can be optimized by considering another failure function, denoted here by fX . Introducing the notation Follow U (u) to denote the set de ned for each language U and for each word u in Pref (U) by Follow U (u) = fa j a 2 A; ua 2 Pref (U)g; it is set that fX (p) = 8 < :

f X (p); if p 6 = " and Follow X (f X (p)) * Follow X (p), fX (f X (p)); if p 6 = " and Follow X (f X (p)) Follow X (p), unde ned; otherwise, for each p 2 Pref (X). The couple ( X ; fX ) represents clearly the transition function of D(X). New failure states can be computed during a second breadth rst search, and this can be done directly on array F X .

However, substituting fX to f X does not a ect the maximum delay of the searching algorithm that still remains O(l log d). To show this point, we give a worst case example. Let '(m) be the language de ned for each m > 1 by: '(m) = fa m 1 bg fa 2j 1 ba j 1 6 j < dm=2eg fa 2j bb j 0 6 j < bm=2cg: If X = '(m) for some m > 1, and if a m 1 bc is the already read pre x of the input, m accesses to the failure function of the linear dictionary-matching automaton of X are made when reading letter c, whatever function f X or fX is chosen. (See the example given in Figure 5.6.) Let us rst observe that this problem can be viewed as a particular case of the dictionary-matching problem (see Section 5). Here, the dictionary has only one element. Moreover, the dictionary-matching automaton D(fxg), which recognizes the language A x, has the minimum number of states required to recognize A x, i.e. jxj + 1 states. Therefore, the minimal automaton recognizing A x, denoted by M(A x), can be identi ed with D(fxg). Since the maximum degree of states of the trie of fxg is upperbounded by one, implementing this automaton with the help of the optimized failure function described Section 5.4 leads to the following results. Theorem 6.1 [START_REF] Knuth | Fast pattern matching in strings[END_REF]. The string-matching problem for x and y can be performed in time O(jxj + jyj) and space O(jxj), the delay being (log jxj) in the worst-case.

We just have to hark back to the order of the delay for the algorithm of Knuth, Morris and Pratt. It is proved that the number of times the transition function of the trie of fxg is performed on any input letter cannot exceed blog (jxj + 1)c where = 1 + p 5 =2 is the golden ratio. This upper bound is a consequence of a combinatorial property of words due to Fine and Wilf (known as the \periodicity lemma"). But it is closed to the worst-case bound, obtained when x is a pre x of the in nite Fibonacci word (see Chapter \Combinatorics of words").

However, as we shall see, implementing M(A x) with adjacency lists solves the string-matching problem with the additional feature of having a real-time search phase on xed alphabets, i.e. with a delay bounded by a constant. Main Theorem 6.2. The string-matching problem for x and y can be achieved in the following terms: { a preprocessing phase on x building an implementation of M(A x) of size O(jxj), performed in time O(jxj) and constant extra-space; { a search phase executing the automaton on y performed in time O(jyj) and constant extra-space, the delay being O(logminf1 + blog 2 jxjc; card(A)g).

Underlying the above result are indeed optimal bounds on the complexity of string-matching algorithms for which the search phase is on-line with a one-letter bu er. Relaxing the on-line condition leads to another theorem stated below. But its proof is based on combinatorial properties of words unrelated to automata and not considered in this chapter. Theorem 6.3 [START_REF] Galil | Time-space optimal string matching[END_REF]). The string-matching problem for x and y previously stored in memory can be performed in time O(jxj + jyj) and constant extra-space.

In Section 6.2, we describe an on-line construction of M(A x). The linear implementation via adjacency lists is discussed in Section 6.3. We establish in Section 6.4 properties of M(A x) that are used in Section 6.5 to prove the asymptotic bounds of the search phase claimed in Theorem 6.2.

String-matching automata

We give a method to build the automaton M(A x). The feature of this method is that it is based on an on-line construction and that it does not use the usual procedures of determinization and minimization of automata.

In the remainder of Section 6 we identify M(A x) with D(fxg), which is the automaton Pref (x); "; x ; (p; a; h x (pa)) j p 2 Pref (x); a 2 A ; h x (v) being the longest su x of v which is a pre x of x, for each v 2 A . We call this automaton the string-matching automaton of x.

An example of string-matching automaton is given in Figure 2.1: the depicted automaton is M(A abaaab) assuming that A = fa; bg. We introduce the notions of \border" as follows. A word v is said to be a border of a word u if v is both a pre x and a su x of u. The longest proper border of a nonempty word u is said to be the border of u and is denoted by Bord(u). As a consequence of de nitions, we have:

h x (pa) = pa;
if pa is a pre x of x, Bord(pa); otherwise, for each (p; a) 2 Pref (x) A.

In order to build M(A x), the construction of the set of edges of the string-matching automaton of x is to be settled. The construction is on-line, as suggested by the following lemma. Lemma 6.1. Let us denote by E u the set of edges of M(A u) for any u 2 A . We have:

E " = ("; b; ") j b 2 A : Furthermore, for each (u; a) 2 A A we have: E ua = E 0 ua E 00 ua with E 0 ua = E u n (u; a; h u (ua)) (u; a; ua) and E 00 ua = (ua; b; w) j (h u (ua); b; w) 2 E 0 ua : Proof. The property for E " clearly holds. Now, let u 2 A and a 2 A, let E 0 ua and E 00 ua be as in the lemma, and set v = h u (ua). Each edge in E ua outgoing a state no longer than juj belongs to E 0 ua . The converse is also true. It remains to prove that each edge in E ua outgoing state ua belongs to E 00 ua , and that the converse holds. This is to prove that for each b 2 A, the targets w and w 0 of the edges (v; b; w) and (ua; b; w 0 ), both in E ua , are identical.

Since v is a border of ua, w is both a su x of uab and a pre x of ua. Which implies that w is shorter than w 0 .

Conversely. We have that jw 0 j 6 jvbj. (Assuming the contrary leads to consider that w 0 b 1 is a border of ua contradicting the maximality of v.) Since w 0 and vb are both su xes of uab, w 0 is a su x of vb. Now w 0 is also a pre x of ua. This shows that w 0 is shorter than w, and ends the proof. u t

The construction of M(A ua) from M(A u) can be interpreted in a visual point of view as the \unfolding" of the edge (u; a; h u (ua)) of the automaton M(A u). An example is given in Figure 6.1 that depicts four steps related to the construction of M(A abaaab). During the construction of the string-matching automaton of abaaab, unfolding of the edge ("; a; ") from step \"" (I) to step \a" (II), of the edge (a; b; ") from step \a" to step \ab" (III), and of the edge (ab; a; a) from step \ab" to step \aba" (IV). It is assumed that A = fa; bg.

A function that builds the string-matching automaton of x following the method suggested by Lemma 6.1 is given in Figure 6.2. This can be used straightforwardly to implement the automaton via its transition matrix. Following the same scheme, we describe in the next section an implementation of the string-matching automaton of x which size is both linear in jxj and independent of the alphabet.

Linear string-matching automata

We show in this section that implementing string-matching automata via adjacency lists gives representations that are time-linear and space-linear in the length of the pattern. Indeed, the property comes from the fact: with " as default state in the adjacency lists (see Section 3.2), the total length of these lists is linear. This representation reduces the automaton to its signi cant part. Another way of saying it, is to consider \signi cant edges" as follows.

An edge (p; a; q) of a given string-matching automaton is signi cant if q 6 = ", and null otherwise; if the edge is signi cant, it is forward if q = pa and backward otherwise.

StringMatchingAutomaton(x)

let be the transition function of (Q; i; ?; E) 1 (Q; E) (?; ?) 2 i State-Creation 3 for each letter b in A 4 loop E E + f(i; b; i)g 5 t i 6 for letter a from rst to last letter of x 7 loop r (t; a) 8 q State-Creation 9 E E f(t;a; r)g + f(t;a; q)g 10 for each letter b in A 11 loop E E + f(q; b; (r; b))g 12 t q 13 return (Q; i; ftg; E) Fig. 6.2. Construction of the string-matching automaton of a word x.

Picking up again the case x = abaaab, the string-matching automaton of x has 6 forward edges and 5 backward edges (see the automaton given in Figure 2.1). Proposition 6.1. The number of signi cant edges of the string-matching automaton of any word x is upper-bounded by 2jxj; more precisely, its number of forward edges is exactly jxj, and its number of backward edges is upper-bounded by jxj. The bounds are reached for instance when the rst letter of x occurs only at the rst position in x.

In order to prove Proposition 6.1, we shall establish the following result.

Lemma 6.2. Let (p; a; q) and (p 0 ; a 0 ; q 0 ) be two distinct backward edges of the string-matching automaton of some word u. Then jpj jqj 6 = jp 0 j jq 0 j. Proof. Suppose for a contradiction the existence of two distinct backward edges (p; a; q) and (p 0 ; a 0 ; q 0 ) of M(A u) satisfying jpj jqj = jp 0 j jq 0 j.

In case p = p 0 , we have that q = q 0 . Since the two edges are signi cant, this implies that a = a 0 . Which is impossible. Thus, we can assume without loss of generality that jpj > jp 0 j, thus, jqj > jq 0 j. Since qa 1 is a border of p (jpj jqa 1 j is a period of p) and since q 0 is a proper pre x of q, we have a 0 = p jq 0 j = p jq 0 j+jpj jqa 1 j = p jq 0 j+jp 0 j jq 0 j+1 = p jp 0 j+1 : Which contradicts the fact that (p 0 ; a 0 ; q 0 ) is a backward edge. u t Proof of Proposition 6.1. The number of forward edges of the automaton is obviously jxj.

Let us prove the upper bound on the number of backward edges. Since the number jpj jqj associated to the backward edge (p; a; q) ranges from 0 to jxj 1, Lemma 6.2 implies that the total number of backward edges is bounded by jxj.

We show that the upper bound on the number of backward edges is optimal. Consider that the rst letter of x occurs only at the rst position in x. The edge (p; x 1 ; x 1 ) is an outgoing edge for each state p of non-zero length of the automaton, and this edge is a backward edge. So, the total number of backward edges is jxj in this case.

u t Figure 6.3 displays a string-matching automaton which number of signi cant edges is maximum for a word of length 7.

From the previous proposition, an implementation of M(A x) via adjacency lists with the initial state " as uniform default state has a size linear in jxj, since the edges represented in the adjacency lists are the signi cant edges of the automaton. We call this representation of the string-matching automaton of x the linear string-matching automaton of x. It is constructed by the function given in Figure 6.4. This function is a mere adaptation of the general function given in Figure 6.2. Recall that the transition function of the linear string-matching automaton of x is assumed to be computed by function AdjacencyLists-Transition of Section 3.2. LinearStringMatchingAutomaton(x) let be the transition function of (Q; i; ?; G) 1 Q ? The time required to build the set of all signi cant edges outgoing a given state is linear in their number (the operations executed on the adjacency list associated to a given state p 6 = x are the operations occurring in Figure 6.4 at line 3 if p = i and at line 11 otherwise, then at line 9 if necessary, then nally at line 10; the corresponding operations for state x are at line 3 if x = " and at line 11 otherwise). Hence, the total time is O(jxj) from Proposition 6.1.

8 if r 6 = i 9 then G t] G t] f(a; r)g 10 G t] G t] + f(a; q)g 11 G q] G r]

u t

We show in Section 6.5 that the linear representation of the string-matching automaton of x described above yields a search for occurrences of x in y that runs in time linear in jyj. Before that, we establish combinatorial properties of string-matching automata in the next section.

Properties of string-matching automata

We establish in this section some upper bounds for the number of signi cant edges of string-matching automata. These bounds complete the global bound given in Proposition 6.1, by focusing on the number of outgoing signi cant edges. The two main results, namely Propositions 6.2 and 6.3, are intensively used in Section 6.5.

Given a word u, we denote by se u (p) the number of signi cant edges outgoing the state p of the string-matching automaton of u; if p is a pre x of u and q a pre x of p, the notation se u (p; q) stands for the number of signi cant edges which sources range in the set of pre xes of u from q to p, i.e. the number se u (q) + se u (q p jqj+1 ) + + se u (q p jqj+1 p jpj 1 ) + se u (p): By way of illustration, we consider the case where x = abacabad. Given a state p of M(A x) (see Figure 6.5), the 1 + blog 2 (jpj + 1)c bound for the number of signi cative edges outgoing p is reached when jpj = 0, 1, 3, or 7. Proposition 6.3. Let u 2 A . For each backward or null edge (p; a; q) of M(A u), we have: se u (p; q) 6 2jpj 2jqj + 2 (p = u) (q = "): Proof. The property clearly holds when u is the power of some letter. The remainder of the proof is by induction.

So, let u 2 A , b 2 A, and let (p; a; q) be a backward or null edge of M(A ub). If jpj 6 juj, (p; a; q) is also an edge of M(A u). By application of Lemma 6.3, we obtain that se ub (p; q) 6 se u (p; q) + (p = u): Otherwise p = ub. Let r be the border of ub. We only have to examine the case where r is a proper pre x of u (if r = u, then u 2 b ). Thus (r; a; q) is an edge of M(A u) and of M(A ub). If it is a forward edge, i.e. if q = ra, we obtain from Lemma 6.3 that se ub (p; q) = se u (u; r) + (r = "); and if it is a backward edge we obtain that se ub (p; q) = se u (r; q) + se u (u; r) + (r = "):

The result now follows by applying of the induction hypothesis to u. u t The previous result is illustrated by the example given in Figure 6.3, i.e. when x = abbbbbb. In this case, the 2jpj 2jqj+2 (p = x) (q = ") bound is reached for any backward or null edge of M(A x).

Observe that Proposition 6.3 provides another proof of the 2jxj bound given in Proposition 6.1 as follows. We consider a null edge outgoing state x (possibly extending the alphabet by one letter). For this edge, with the notation of Proposition 6.3, we have p = u = x and q = ". Thus, se x (x; "), which is the total number of signi cant edges of M(A x), is not greater than 2jxj 2j"j + 2 1 1 = 2jxj.

Searching with linear string-matching automata

Our proof of Theorem 6.2 consists in considering linear string-matching automata for matching words. We then consider the model of computation where none ordering on the alphabet is assumed, and give some optimal bounds for string-matching algorithms for which the search phase is on-line with a one-letter bu er.

Consider the search phase of algorithm Matcher using the linear string-matching automaton of a given word x. For each backward or null edge (p; a; q) of the string-matching automaton of x, let us denote by c x (p; q) the maximum time for executing the series of transitions from q to q via p, i.e. for reading the word x jqj+1 x jqj+2 x jpj a starting in state q. Let us also denote by C x (y) the time for executing the search phase when y is the searched word, i.e. the time for executing the automaton on y. Lemma 6.6. Let x; y 2 A . There exists a nite sequence of backward or null edges of M(A x), say ((p j ; a j ; q j )) 16j6k , satisfying the three following conditions: (i) q k = "; (ii) P k j=1 jp j j jq j j + 1 = jyj; (iii) C x (y) 6 P k j=1 c x (p j ; q j ).

Proof. The proof is by induction on jyj. Since the property trivially holds when jyj = 0, we assume that jyj > 1.

Observe rst that since an upper bound is expected for C x (y), we can assume, even if the alphabet has to be extended by one letter, that the last letter of y is not a letter occurring actually in x. Hence, we can assume that the lastly performed transition corresponds to a null edge. Now, let (p `)06`6jyj be the sequence of successive values of the current state p of algorithm Matcher (in other words p `= h x (y 1 y 2 y `)). Let m, 0 6 m 6 jyj 1, be the minimal integer satisfying p m+1 = p m 0 for some m 0 6 m, then let m 0 be the integer in f0; : : :; mg such that p m 0 = p m+1 . Thus, the triple (p m ; y m+1 ; p m 0 ) is a backward or null edge of M(A x), and the m m 0 + 1 successive letters y m 0 +1 , y m 0 +2 , : : :, y m+1 of y have been read during the computation of the transitions from p m 0 to p m+1 via p m . Consider the word y 0 de ned by y 0 = y 1 y 2 y m 0 y m+2 y m+3 y jyj . Following the de nition of m and m 0 we have that C x (y) 6 c x (p m ; p m 0 ) + C x (y 0 ). Applying the induction hypothesis to y 0 gives the existence of a nite sequence e 0 as depicted in the statement. The expected sequence related to y can then be obtained by adding the edge ((p m ; y m+1 ; p m 0 )) in front of the sequence e 0 . It clearly satis es conditions (i) to (iii). This ends the proof. u t Theorem 6.5. Let x and y be words. Using the linear string-matching automaton of x, searching for all occurrences of x as factors of y (search phase of algorithm Matcher) is performed in time O(jyj), constant extra-space, within a delay O(log minf1 + blog 2 jxjc; card(A)g).

Proof. Whatever e cient is the implementation of adjacency lists, we may assume that the time for executing the transition from the current state by the current input letter is asymptotically linear in the number of signi cant edges outgoing the involved state. For each backward or null edge (p; a; q) of M(A x), this assumption implies that c x (p; q) = O(se x (p; q)); which leads to c x (p; q) = O(jpj jqj + 1); by application of Proposition 6.3. We nally apply Lemma 6.6, and get the O(jyj) bound.

We now turn to the proof of the delay. The cardinality of each adjacency list is both upper-bounded by card(A), and, from Lemma 6.3 and Proposition 6.2, by 1+blog 2 jxjc. Now, observe that each adjacency list can be arranged in a balanced tree when computing it, without loosing the linear-time complexity of the construction. This provides a logarithmic time for computing a transition. Which proves the asymptotic bound of the delay.

u t

In the remainder of the section, no ordering on the alphabet is assumed, contrary to what is assumed for the previous statement. The model of computation is the comparison model in which algorithms have access to the input words by comparing pairs of letters to test whether they are equal or not. Within this model, given a word x, we denote by S(x) the family of the string-matching algorithms for which the search phase is on-line with a one-letter bu er.

String-matching algorithms based on the linear string-matching automaton of x can be classi ed according to the way the adjacency lists are ordered or scanned. For example, the adjacency lists can be ordered by decreasing length of target, or by the frequency of labels as letters of the pre x already read; each adjacency list can also be scanned according to a random processing. (Let us observe that any of these variations preserves the linear time of the search). We denote by L(x) the subfamily of algorithms in S(x) which use the linear string-matching automaton of x to search a given word for occurrences of x. Theorem 6.6. Given x 2 A + , consider an algorithm in L(x), and an input of non-zero length n. In the comparison model, performs no more than 2n 1 letter comparisons, and compares each of the n letter of the input less than minf1 + blog 2 jxjc; card(A)g times.

Proof. This is similar to the proof of Theorem 6.5. The term \ 1" of the 2n 1 bound results from the fact that we can assume that at least one transition by a null edge of M(A x) is simulated (the edge (q k 1 ; a k ; q k ) of Lemma 6.6).

u t

The 2n 1 bound of Theorem 6.6 is also the bound reached by the algorithm of Section 5 when ab is a pre x of the only word of the dictionary and the input is in a . However, this worst-case bound can be lowered in L(x), using the special strategy described in the following statement for computing transitions. Theorem 6.7. Given x 2 A + , consider an algorithm in L(x) that applies the following strategy: to compute a transition from any state p, scan the edges outgoing p in such a way that the forward edge (if any) is scanned last. Then, in the comparison model, executes no more than b(2 1=jxj) nc letter comparisons on any input of length n.

Proof. Let (p; a; q) be a backward or null edge of M(A x). The number of comparisons while executing the series of transitions from q to q via p is bounded by se x (p; q) (p 6 = x). By application of Proposition 6.3, we obtain that at most (2 1=jxj) (jpj jqj+1) comparisons are performed during this series of transitions. Then we apply Lemma 6.6 and obtain the expected bound. u t For a given length m of patterns, the delay minf1 + blog 2 mc; card(A)g (Theorem 6.6) and the coe cient 2 1=m (Theorem 6.7) are optimal quantities. This is proved by the next two propositions. Proposition 6.4. Consider the comparison model. Then, for each m > 1, for each n > m, there exist x 2 A m and y 2 A n such that any algorithm in S(x) performs at least minf1 +blog 2 mc; card(A)g letter comparisons in the worst-case on some letter of the searched word y.

Proof. De ne recursively the mapping : A ! A by (ua) = (u) a (u) for each (u; a) 2 A A and (") = ". (For instance, we have (abcd) = abacabadabacaba.)

Set k = minf1+blog 2 mc; card(A)g, choose k pairwise distinct letters, say a 1 , a 2 , : : :, a k , and assume that (a 1 a 2 a k 1 )a k is a pre x of x. If (a 1 a 2 a k 1 ) is the already read pre x of y, the algorithm can suppose that an occurrence of x starts at one of the positions in the form 2 k `, 1 6 `6 k. Hence, the algorithm performs never less than k letter comparisons at position 2 k 1 in the worst-case. u t Proposition 6.5. Consider the comparison model. Then, for each m > 1, for each n > 0, there exist x 2 A m and y 2 A n such that any algorithm in S(x) performs at least b(2 1=m) nc letter comparisons in the worst-case when searching y.

Proof. Assume that x = ab m 1 and y 2 Pref ((afa; bg m 1 ) ). Then let j, 1 6 j 6 n, be the current position on y, and let v be the longest su x of y 1 y 2 y j 1 that is also a proper pre x of x.

If v 6 = ", the algorithm has to query both if y j = a and if y j = b in the worst-case, in order to be able to report later an occurrence of x at position either j or j jvj. Otherwise v = ", and the algorithm can just query if y j = a. But, according to the de nition of y, the second case, namely v = ", may occur only when j 1 (mod m). Therefore, the number of letter comparisons performed on y is then never less than 2n dn=me = b(2 1=m) nc in the worst-case. u t

Su x automata 7.1 Outline

The su x automaton of a word x is de ned as the minimal deterministic (non necessarily complete) automaton that recognizes the ( nite) set of su xes of x. It is denoted by M(Su (x)) according to notations of Section 2. An example of su x automaton is displayed in Figure 7.1.

The automaton M(Su (x)) can be used as an index on x to solve the following problem. An alternative solution to the problem is to implement data structures techniques based on a representation of the set of su xes of x by compact tries. This structure is known as the su x tree of x.

The su x automaton provides another solution to the string-matching problem (see Section 6) since it can also be used to search a word y for factors of x. This yields a space e cient solution to the search for rotations (Section 7.5) of a given word.

The surprising property of su x automata is that their size is linear although the number of factors of a word can be quadratic in the length of the word. The construction of su x automata is also linear on xed alphabets. Main Theorem 7.1. The size of the su x automaton of a word x is O(jxj). The automaton can be implemented in time O(jxj logcard(A)) and O(jxj) extra-space.

The implementation which is referred to in the theorem is based on adjacency lists. As in Section 5, if we allow more extra-space, the time complexity reduces to O(jxj). This is valid also for Theorems 7.5 and 7.6, Propositions 7.2, 7.3, 7.4, 7.5, and 7.8.

We rst review in Section 7.2 properties of su x automata that are useful to design a construction method. At the same time, we provide exact bounds on the size of the automata. These results have consequences on the running time of the method. Section 7.3 is devoted to the construction of su x automata itself. The same approach is presented in Section 7.6 for factor automata. Sections 7.4 and 7.5 show how these automata can be used either as indexes or as string-matching automata.

7.2 Sizes and properties 7.2.1 End-positions. Right contexts according to Su (x) satisfy a few properties stated in the next lemmas and used later in the chapter. The rst remark concerns the context of a su x of a word. Lemma 7.1. Let u; v 2 A . If u 2 Su (v), then v 1 Su (x) u 1 Su (x). Proof. If v 1 Su (x) = ? the inclusion trivially holds. Otherwise, let z 2 v 1 Su (x). Then, vz 2 Su (x) and, since u 2 Su (v), uz 2 Su (x). So, z 2 u 1 Su (x). u t

Right contexts satisfy a kind of converse statement. To formalize it, we introduce the function endpos x : Fact(x) ! N de ned for each word u by endpos x (u) = minfjwj j w is a pre x of x and u is a su x of wg: The value endpos x (u) marks the ending position of the rst (or leftmost) occurrence of u in x. Lemma 7.2. Let u; v 2 Fact(x). If u Su (x) v, we have the equality endpos x (u) = endpos x (v), which is equivalent to say that one of the words u and v is a su x of the other. Proof. Let y; z 2 A be such that x = yz and u 2 Su (y). We assume in addition that jyj = endpos x (u). Then z is the longest word of u 1 Su (x). The hypothesis implies that z is also the longest word of v 1 Su (x), which shows that jyj = endpos x (v). In this situation, u and v are both su xes of y, which proves that one of them is a su x of the other.

u t

Since u 6 Su (w) z, we have that k > 0. Thus, Lemma 7.6 implies that v is a su x of s w k (z), and then that v is a su x of wa as expected. This proves the rst part of the statement.

Consider now a word u such that u Su (w) z.

If juj 6 jzj, to prove u Su (wa) z, using the above argument, we just have to show that u 2 Su (wa) because z 2 Su (wa). Indeed, this is a simple consequence of Lemma 7.2.

Conversely, assume that juj > jzj. When such a word u exists, z 0 6 = z and jz 0 j > jzj (z is a proper su x of z 0 ). Therefore, by the de nition of z, u and z 0 are not su xes of wa. Using again the above argument, this shows that u Su (wa) z 0 .

This proves the second part of the statement and ends the proof. u t Corollary 7.2. Let w 2 A and a 2 A. Let z be the longest su x of wa occurring in w. Let z 0 be the longest word such that z 0 Su (w) z. If z 0 = z, then, for each u; v 2 Fact(w), u Su (w) v implies u Su (wa) v. Proof. The conclusion follows directly from Theorem 7.2 if u 6 Su (w) z. Otherwise, u Su (w) z, and by the hypothesis on z and Lemma 7.2, we get juj 6 jzj. Thus, Theorem 7.2 again gives the same conclusion. u t Corollary 7.3. Let w 2 A and a 2 A. Assume that letter a does not occur in w. Then, for each u; v 2 Fact(w), u Su (w) v implies u Su (wa) v. Proof. Since a does not occur in w, the word z of Corollary 7.2 is the empty word. This word is the longest word in its own congruence class. So, the hypothesis of Corollary 7.2 holds. Therefore, the same conclusion follows. u t 7.2.4 Sizes of su x automata. We discuss the size of su x automata both in term of number of states and number of edges. We show that the global size of M(Su (x)) is O(jxj). The set of states and the set of edges of M(Su (x)) are respectively denoted by Q and E (without mention of x that is implicit in statements). Corollary 7.4. If jxj = 0, card(Q) = 1; and if jxj = 1, card(Q) = 2. Otherwise jxj > 2; then, jxj + 1 6 card(Q) 6 2jxj 1 and the upper bound is reached only when x is in the form ab jxj 1 for two distinct letters a and b. Proof. The minimum number of states is obviously jxj+ 1, and is reached when x is in the form a jxj for some a 2 A. Moreover, we have exactly card(Q) = jxj + 1 when jxj 6 2.

Assume now that jxj > 3. By Theorem 7.2, each symbol x k , 3 6 k 6 jxj, increases by at most 2 the number of states of M(Su (x 1 x 2 x k 1 )). Since the number of states for a word of length 2 is 3, we get that card(Q) 6 3 + 2(jxj 2) = 2jxj 1; as announced in the statement.

The construction of a word x reaching the upper bound for the number of states of M(Su (x)) is a mere application of Theorem 7.2 considering that each letter x k , 3 6 k 6 jxj, should e ectively increase by 2 the number of states of M(Su (x 1 x 2 x k 1 )). u t Figure 7.2 displays a su x automaton whose number of states is maximum for a word of length 7. Let length x : Q ! N be the function associating to each state q of M(Su (x)) the length of the longest word u in the congruence class q. It is also the length of the longest path from the initial state to q. (This path is labeled by u.) Longest paths form a spanning tree on M(Su (x)) (a consequence of Lemma 7.2). Transitions that belong to that tree are called solid edges. Equivalently, for each edge (p; a; q) of M(Su (x)), we have that:

(p; a; q) is solid () length x (q) = length x (p) + 1:

This notion is used in the construction of su x automata to test the condition stated in Theorem 7.2. We use it here to derive exact bounds on the number of edges of su x automata.

Lemma 7.10. Assuming jxj > 1, card(E) 6 card(Q) + jxj 2.

Proof. Consider the spanning tree of longest paths from the initial state in M(Su (x)). The tree contains card(E) 1 edges of M(Su (x)), which are the solid edges.

To each non-solid edge (p; a; q) we associate the su x uav of x de ned as follows: u is the label of the longest path from the initial state to p, and v is the label of the longest path from q to a terminal state. Note that, doing so, two di erent non-solid edges are associated with two di erent su xes of x. Since su xes x and " are labels of paths in the tree, they are not considered in the correspondence. Thus, the number of non-solid edges is at most jxj 1.

Counting together the number of both kinds of edges gives the expected upper bound. u t Corollary 7.5. If jxj = 0, card(E) = 0; if jxj = 1, card(E) = 1; and if jxj = 2, 2 6 card(E) 6 3. Otherwise jxj > 3; then jxj 6 card(E) 6 3jxj 4, and the upper bound is reached when x is in the form ab jxj 2 c, for three pairwise distinct letters a, b, and c. Proof. The lower bound is obvious, and reached when x is in the form a jxj for some a 2 A. The upper bound can be checked by hand for the cases where jxj 6 2.

Assume now that jxj > 3. By Corollary 7.4 and Lemma 7.10 we have card(E) 6 2jxj 1 + jxj 2 = 3jxj 3. The quantity 2jxj 1 is the maximum number of states obtained only when x is in the form ab jxj 1 for two distinct letters a and b. But the number of edges in M(Su (ab jxj 1 )) is only 2jxj 1. So, card(E) 6 3jxj 4.

The automaton M(Su (ab jxj 2 c)), for three pairwise distinct letters a, b and c, has 2jxj 2 states and exactly 3jxj 4 edges composed of 2jxj 3 solid edges and jxj 1 non-solid edges.

u t As a conclusion of Section 7.2, we get the following statement, direct consequence of Corollaries 7.4 and 7.5.

Theorem 7.3. The total size of the su x automaton of a word is linear in the length of the word.

Construction

We describe in Sections 7.3.1, 7.3.2 and 7.3.3 an on-line construction of the su x automaton M(Su (x)). 7.3.1 Su x links and su x paths. The construction of M(Su (x)) follows Theorem 7.2 and its corollaries stated in Section 7.2. Conditions that appear in these statements are checked on the automaton with the help of a function de ned on its states and called the \su x link". It is a failure function in the sense of Section 3.4, and is used with this purpose in Section 7.5.

Let (Q; i; T; E) = M(Su (x)) and be the corresponding transition function. Let p 2 Qnfig. State p is a class of factors of x congruent with respect to Su (x) . Let u be any word in the class of p (u 6 = " because p 6 = i). Then, the su x link of p is the congruence class of s x (u). By Lemma 7.4 the value s x (u) is independent of the word u chosen in the class p, which makes the de nition coherent. We denote by f x the function assignating to each state p its congruence class s x (u). Su x links induce by iteration \su x paths" in M(Su (x)). Note that if q = f x (p), then length x (q) < length x (p). Therefore, the sequence (p; f x (p); f x 2 (p); : : :) is nite and ends with the initial state i. It is called the su x path of p.

We denote by last x the state of M(Su (x)) that is the class of x itself. State last x has no outgoing edge (otherwise M(Su (x)) would recognize words longer than x). The su x path of last x , i.e.

(last x ; f x (last x ); f x 2 (last x ); : : :); plays an important role in the on-line construction. It is used to test e ciently conditions appearing in statements of the previous section. Proposition 7.1. Let u 2 Fact(x)nf"g and set p = (i; u). Then, for any integer k > 0 for which

s x k (u) is de ned, f x k (p) = (i; s x k (u)).
Proof. The proof is by induction on k.

For k = 0, the equality holds by hypothesis.

Next, let k > 1 such that s x k (u) is de ned and assume that f x k 1 (p) = (i; s x k 1 (u)). By de nition of f x , f x (f x k 1 (p)) is the congruence class of the word s x (s x k 1 (u)). Therefore, f x k (p) = (i; s x k (u)) as expected.

u t Corollary 7.6. Terminal states of M(Su (x)), the states in T , are exactly the states of the su x path of state last x .

Proof. Let p be a state of the su x path of last x . Then, p = f x k (last x ) for some integer k > 0. By Proposition 7.1, since last x = (i; x), we have p = (i; s x k (x)). Since s x k (x) is a su x of x, p 2 T . Conversely, let p 2 T . So, for some u 2 Su (x), p = (i; u). Since u 2 Su (x), we can consider the largest integer k > 0 such that juj 6 js x k (x)j. By Lemma 7.3 we get u Su (x) s x k (x). Thus, p = (i; s x k (x)) by de nition of M(Su (x)). Then, Proposition 7.1 applied to x shows that p = f x k (last x ), which proves that p belongs to the su x path of last x . u t 7.3.2 On-line construction. This section presents an on-line construction of su x automata. At each stage of the construction, just after processing a pre x x 1 x 2 x `of x, the su x automaton M(Su (x 1 x 2 x `)) is built. Terminal states are implicitly known by the su x path of last x1x2 x`( see Corollary 7.6). The state last x1x2 x`i s explicitly represented by a variable in the function building the automaton.

Two other elements are also used: Length and F . The table Length represents the function length x de ned on states of the automaton. All edges are solid or non-solid according to the de nition of Section 7.2 that relies on function length x . Su x links of states (di erent from the initial state) are stored in a table denoted by F that stands for the function f x . The implementation of M(Su (x)) with these extra features is discussed in the next section.

The on-line construction in Figure 7.4 is based on procedure SA-Extend given in Figure 7.5. The latter procedure processes the next letter, say x `, of the word x. It transforms the su x automaton M(Su (x 1 x 2 x ` 1 )) already built into the su x automaton M(Su (x 1 x 2 x `)).

We illustrate how procedure SA-Extend processes the current automaton through three examples.

Let us consider that x 1 x 2 x ` 1 = ccccbbccc, and let us examine three possible cases according to SuffixAutomaton(x) let be the transition function of (Q; i; T; E) 1 (Q; E) (?;?) 2 i State-Creation 3 Length i] 0 4 F i] nil 5 last i 6 for `from 1 up to jxj while p 6 = nil and (p; a) = nil if p = nil then F newlast] i else q (p; a) if Length q] = Length p] + 1 then F newlast] q else q 0 State-Creation for each letter b such that (q; b) 6 = nil loop E E + f(q 0 ; b; (q; b))g Length q 0 ] Length p] + 1

F newlast] q 0 F q 0 ] F q] F q] q 0 loop E E f(p; a; q)g + f(p;a; q 0 )g During the execution of the rst loop of the procedure, state p runs through a part of the su x path of last. At the same time, edges labeled by a are created from p to the newly created state, unless such an edge already exists in which case the loop stops.

If a = d, the execution of the loop stops at the initial state. The edges labeled by d start at terminal states of M(Su (ccccbbccc)). This case corresponds to Corollary 7.3. The resulting automaton is given in Figure 7.7. If a = c, the loop stops on state 3 = F last] (of the automaton depicted in Figure 7.6) because an edge labeled by c is de ned on it. Moreover, the edge is solid, so, we get the su x link of the new state. Nothing else should be done according to Corollary 7.2. This gives the automaton of Figure 7.8. Finally, when a = b, the loop stops on state 3 = F last] for the same reason, but the edge labeled by b from 3 is non-solid. The word cccb is a su x of the new word ccccbbcccb but ccccb is not. Since these two words reach state 5, this state is duplicated into a new state that becomes a terminal state. Su xes ccb and cb are re-directed to this new state, according to Theorem 7.2. We get the automaton of Figure 7.9. Theorem 7.4. Function SuffixAutomaton builds the su x automaton of any given word x.

Proof. The proof is by induction on the length of x. It heavily relies on the properties stated previously. If x = ", the function builds an automaton with only one state that is both initial and terminal. No edge is de ned. So, the automaton recognizes the language f"g, which is Su (x).

Otherwise x 6 = ". Let w 2 A and a 2 A be such that x = wa. We assume, after preprocessing w, that the current values of Q and E are respectively the set of states and of edges of M(Su (w)), that last is the state (i; w), that Length r] = length w (r) for each r 2 Q, and that F r] = f w (r) for each r 2 Qnfig. We prove rst that procedure SA-Extend correctly updates sets Q and E, variable last, and tables Length and F. Then, we show that terminal states are eventually correctly marked by function SuffixAutomaton.

The variable p of procedure SA-Extend runs through the states of the su x path of last of M(Su (w)). The rst loop creates edges by letter a onto the new created state newstate according to Lemma 7.9, and we have the equality Length newlast] = length x (newlast).

When the loop stops, three exclusive cases can be distinguished: (i) p is unde ned; (ii) (p; a; q) is a solid edge; (iii) (p; a; q) is a non-solid edge.

Case (i). The letter a does not occur in w, so, f x (newlast) = i. Then, we have F newlast] = f x (newlast). For any other state r, f w (r) = f x (r) by Corollary 7.3. Then, again F r] = f x (r) at the end of execution of procedure SA-Extend.

Case (ii). Let u be the longest word such that (i; u) = p. By induction and by Lemma 7.6, we have juj = length x (p) = Length p]. The word ua is the longest su x of x occurring in w. Then, f x (newlast) = q, and thus F newlast] = f x (newlast).

Since the edge (p; a; q) is solid, using the induction again, we obtain juaj = Length q] = length x (q), which shows that words congruent to ua according to Su (w) are not longer than ua. Therefore, Corollary 7.2 applies with z = ua. And as in case (i), F r] = f x (r) for each state di erent than newlast.

Case (iii). Let u be the longest word such that (i; u) = p. The word ua is the longest su x of wa occurring in w. Then, f x (newlast) = q, and thus F newlast] = f x (newlast).

Since the edge (p; a; q) is non-solid, ua is not the longest word in its own congruence class according to Su (w) . Theorem 7.2 applies with z = ua, and z 0 the longest word, label of the path from i to q. The class of ua according to Su (w) splits into two classes according to Su (x) . They are represented by states q and q 0 . Words v shorter than ua and such that v Su (w) ua are in the form v 0 a with v 0 2 Su (u) (consequence of Lemma 7.2). Before the execution of the last loop, all these words v satisfy q = (i; v). Therefore, after the execution of the loop, they satisfy q 0 = (i; v), as expected from Theorem 7.2. Words v longer than ua and such that v Su (w) ua satisfy q = (i; v) after the execution of the loop, as expected from Theorem 7.2 again. It is easy to check that su x links are correctly updated.

Finally, in the three cases (i), (ii), and (iii), the value of last is correctly updated at the end of procedure SA-Extend.

Thus, the induction proves that the sets Q and E, variable last, tables Length and F are correct after the execution of procedure SA-Extend.

That terminal states are correctly marked during the last loop of function SuffixAutomaton is a consequence of Corollary 7.6. u t 7.3.3 Complexity. In order to analyze the complexity of the above construction, we rst describe a possible implementation of elements required by the construction. We assume that the automaton is represented by adjacency lists. Doing so, the operations of adding, updating, and accessing a transition (computing (p; a)) take O(log card(A)) time with an e cient implementation of adjacency lists (see Section 3.2). Function f x is implemented by the array F that gives access to f x (p) in constant time.

For the implementation of the solid/non-solid quality of edges, we have chosen to use an array, namely Length, representing function length x , as suggested by the description of procedure SA-Extend. Another possible implementation is to tie a boolean value to edges themselves. Doing so, the rst edges created at steps 5 and 20 should be marked as solid. The other edges should be de ned as non-solid. This type of implementation do not require the array Length that can be eliminated. But the array can be used in applications like the one presented in Section 7.5. Both types of implementation provide a constant-time access to the quality of edges. Another consequence of these corollaries is that all operations executed once for each state or each edge take O(jxj log card(A)) on the overall. The same result holds for operations executed once for each letter of x. So, it remains to prove that the total running time of the two loops of lines 5{6 and lines 20{21 inside procedure SA-Extend is also O(jxj logcard(A)).

Assume that procedure SA-Extend is going to update M(Su (w)), w being a pre x of x. Let u be the longest word reaching state p during the test of the loop of lines 5{6. The initial value of u is s w (w), and its nal value satis es ua = s wa (wa) (if p is de ned). Let k be the quantity jwj juj, which is the position of the su x occurrence of u in w. Then, each test strictly increases the value of k during a single run of the procedure. Moreover, the nal value of k after a run of the procedure is not greater than its initial value at the beginning of the next run. Therefore, tests and instructions of that loop are executed at most jxj times.

We use a similar argument for the loop of lines 20{21 of procedure SA-Extend. Let v be the longest word reaching state p during the test of this loop. The initial value of v equals s w k (w) for some integer k > 2, and its nal value satis es va = s wa 2 (wa) (if p is de ned). Then, the position of v as a su x of w strictly increases at each test over all runs of the procedure. Again, tests and instructions of that loop are executed at most jxj times. Therefore, the accumulated running time of the two loops of lines 5{6 and lines 20{21 altogether is O(jxj log card(A)). Which ends the proof. u t

As indexes

The su x automaton of a word naturally provides an index on its factors. We consider four basic operations on indexes: membership, rst position, number of occurrences, and list of positions. The su x automaton also helps computing e ciently the number of factors in a word, as well as the longest factor occurring at least twice in a word. Proof. Just spell the word w in M(Su (x)) considering the two implementations described in Section 7.3. Stopping the search on the rst unde ned transition gives the longest pre x u of w for which (i; u) is de ned, which means that it is a factor of x. u t 7.4.2 First position. Problem 7.3. (First (respectively last) position of w in x.) Given w 2 Fact(x), nd its rst (respectively last) position in x.

We assume that w 2 Fact(x). This test (\does w belong to Fact(x)?") can be performed separately as in Section 7.4.1, or can be merged with the solution of the present problem. The problem of nding the rst position fp x (w) of w in x is equivalent to computing endpos x (w) because fp x (w) = endpos x (w) jwj: Moreover, this is also equivalent to computing the maximum length of right contexts of w in x, lc x (w) = maxfjzj j z 2 w 1 Fact(x)g; because fp x (w) = jxj lc x (w) jwj: Symmetrically, nding the last position lp x (w) of w in x remains to computing the smallest length sc x (w) of its right contexts because lp x (w) = jxj sc x (w) jwj: To be able to answer e ciently requests on the rst or last positions of factors of x, we precompute arrays indexed by states of M(Su (x)) representing functions lc x and sc x . We get the next result. Proposition 7.3. The automaton M(Su (x)) can be preprocessed in time O(jxj) so that the rst (or last) position in x of any word w 2 Fact(x) can be computed in time O(jwj logcard(A)) within O(jxj) space.

Proof. We consider an array LC de ned on states of M(Su (x)) as follows. Let p be a state and u be such that p = (i; u); then, we de ne LC p] = lc x (u). Note that the value of LC p] does not depend on the word u because for an equivalent word v, lc x (u) = lc x (v) (by Lemma 7.2). The array LC satis es the induction relation:

LC p] = 0; if p = last x , 1 + maxfLC q] j q = (p; a); a 2 Ag; otherwise. So, the computation of LC can be done during a depth-rst traversal of the graph of M(Su (x)). Since the total size of the graph is O(jxj) (Theorem 7.3), this takes time O(jxj).

To compute fp x (w), we rst locate the state p = (i; w), and then return jxj jwj LC p]. This takes the same time as for the membership problem.

To nd the last occurrence of w in x we consider the array SC that represents the function sc x . If p = (i; u), we set SC p] = sc x (u), which is a coherent de nition. We then use the next relation to compute the array during a depth-rst traversal of M(Su (x)):

SC p] = 0; if p 2 T, 1 + minfSC q] j q = (p; a); a 2 Ag; otherwise.

After the preprocessing, we get the same complexity as above. This ends the proof. Proof. The number of occurrences of w in x is cardfz j z 2 A and wz 2 Su (x)g: If (i; w) = p, this is also cardfz j z 2 A and (p; z) 2 Tg: Let NB p] be this quantity, for any state of M(Su (x)).

The array NB satis es the recurrence relation:

NB p] = 1 + P q= (p;a);a2A NB q]; if p 2 T, P q= (p;a);a2A NB q]; otherwise, which shows that the array NB can be computed in time proportional to the size of the automaton during a depth-rst traversal of the graph. This takes O(jxj) time.

Afterwards, the problem remains to access NB p] for p = (i; w). (If p is unde ned, w does not occur in x.) Computing p takes the time announced in the statement.

u t

An argument similar to that of the previous proof gives the computation of the number of factors occurring in x, i.e. the size of Fact(x). Indeed, Fact(x) is the particular right context associated with the initial state of M(Su (x)). And to compute its size, we evaluate contexts sizes CS p] of all states of the automaton using the relation:

CS p] = 1; if p = last x , 1 + P q= (p;a);a2A CS q]; otherwise. This provides a linear-time computation of card(Fact(x)) = CS i].

7.4.4 List of positions. Problem 7.5. (Positions of w in x.) Given w 2 Fact(x), produce the list of positions of w in x. Proposition 7.5. The automaton M(Su (x)) can be preprocessed in time O(jxj) so that the list L of positions in x of any w 2 Fact(x) can be computed in time O(jwj log card(A) +card(L)) within O(jxj) space.

Proof. We just sketch the proof of the statement. The automaton is preprocessed in order to create shortcuts over states on which exactly one edge is de ned and that are not terminal states. To do so, we create a graph structure superimposed on the automaton. The nodes of the graph are either terminal states or states whose degree is at least two. Arcs of the graph are labeled by the labels of the corresponding path in the automaton. From a given state, labels of outgoing arcs start with pairwise distinct letters (because the automaton is deterministic).

Once the node q associated with w (or an extension of it) is found in the graph, the list of positions of w in x is computed by traversing the subgraph rooted at q. Consider the tree of the traversal. Its internal nodes have at least two children, and its leaves are associated with distinct positions (some positions can correspond to internal nodes). Therefore, the number of nodes of the tree is less than 2 card(L), which proves that the time of the traversal is O(card(L)). The extra running time is used to nd q. u t Problem 7.7. (Searching for rotations.) Given x 2 A , locate all occurrences of rotations of x in any given word y.

A rst solution to the problem is to apply the algorithm of Section 5 to the set of rotations of x. However, the space required by this solution can be quadratic in jxj like can be the size of the corresponding trie. A solution based on su x automata keeps the memory space linear.

Proposition 7.8. After a preprocessing on x in time O(jxj log card(A)), positions of occurrences of rotations of x occurring in y can be computed in time O(jyj logcard(A)) within O(jxj) space. Proof. Note that the factors of length jxj of the word xx are all the rotations of x. And that longer factors have a rotation of x as a su x. (In fact, the word xuA 1 , where u is the shortest period of x, satis es the same property.)

The solution consists in running the procedure EndingFactors with the automaton M(Su (xx)) after adding this modi cation: retain position k jxj each time `k > jxj. Indeed, `k > jxj if and only if the longest factor w of xx ending at position k is not shorter than x. Thus, the su x of length jxj of w is a rotation of x. The complexity of the new procedure is the same as that of procedure EndingFactors. u t

Factor automata

The factor automaton of a word x is the minimal deterministic automaton recognizing Fact(x). It is denoted by M(Fact(x)). It is clear that the su x automaton M(Su (x)) recognizes Fact(x) if all its states are transformed into terminal states. But the automaton so obtained is not always minimal. For example, the factor automaton of aabbabb, shown in Figure 7.11, is smaller than the su x automaton of the same word (Figure 7.1). In this section we brie y review few elements related to factor automata: their relation to su x automata, their sizes, and their construction. 7.6.1 Relation to su x automata. The construction of factor automata by an on-line algorithm is slightly more tricky than the construction of su x automata. The latter can be simply deduced from a procedure that builds factor automata as follows. To get M(Su (x)), rst build M(Fact(x$)), extending alphabet A by letter $, then set as terminal states only those states from which an edge by letter $ outgoes, and nally remove all edges by letter $ and the state they reach. The correctness of this procedure is straightforward, but is also a consequence of Theorem 7.7 below.

Conversely, the construction of M(Fact(x)) from M(Su (x)) requires a minimization procedure. This is related to the non-solid path in M(Fact(x)) considered in the on-line construction, and that is presented here.

Let us denote by x the su x function corresponding to the right syntactic congruence associated with Fact(x) (and denoted by Fact(x) in this chapter). Let z = x (x) (the longest su x of x occurring at least twice in it). Let (p j ) 06j6jzj be the sequence of states of M(Fact(x)) de ned by p 0 = i, and, for 0 < j 6 jzj, p j = (p j 1 ; z j ), where is the transition function of M(Fact(x)), and i its initial state. Let k, 0 6 k 6 jzj, be the smallest integer for which (p k ; z k+1 ; p k+1 ) is a non-solid edge (setting k = jzj if no such edge exists). Then, the non-solid path of M(Fact(x)) is composed of edges (p k ; z k+1 ; p k+1 ); (p k+1 ; z k+2 ; p k+2 ); : : :; (p jzj 1 ; z jzj ; p jzj ):

In equivalent terms, the word z is decomposed into uv, where u = z 1 z 2 z k and v = z k+1 z k+2 z jzj . The word u is the longest pre x of z which is the longest word in its own congruence class according to Fact(x) . This implies that all shorter pre xes of z satisfy the same condition while longer pre xes do not. The word v labels the non-solid path of M(Fact(x)). It is the empty word if the non-solid path contains no edge.

With the above notion we can describe an alternative method to derive M(Su (x)) from M(Fact(x)). It consists of rst building M(Fact(x)), and then duplicating states p k+1 , p k+2 , : : :, p jzj , of the non-solid path of M(Fact(x)) into terminal states while creating edges and su x links accordingly. This gives also an idea of how, by symmetry, the automaton M(Su (x)) can be minimized e ciently into M(Fact(x)).

For example, in the automaton M(Fact(aabbabb)) of Figure 7.11, the non-solid path is composed of the two edges (1; b; 3) and (3; b; 4). The automaton M(Su (aabbabb)) is obtained by cloning respectively states 3 and 4 into states 3 00 and 4 00 of Figure 7.1.

The duplication of the non-solid path labeled by v as above is implemented by the procedure of Figure 7.12. The input (r; k), which represents the non-solid path, is de ned by k = jxv 1 j and r = (i; xv 1 ). For example, with the automaton M(Fact(aabbabb)) of Figure 7.11 the input is (5; 5).

FA-to-SA(r; k)

1 for letter a from k + 1-st to last letter of x 2 loop t (r; a) 3 p F t] 4 q (p; a) 5 q 0 State-Creation 6 for each letter b such that (q; b) 6 = nil 7 loop E E + f(q 0 ; b; (q; b))g 8

Length q 0 ] Length p] + 1 9

F t] q 0 10 F q 0 ] F q] 11 F q] q 0 12 loop E E f(p; a; q)g + f(p;a; q 0 )g 13 p F q] 14 while p 6 = nil and (p; a) = q 15 r t Fig. 7.12. From M(Fact(x)) to M(Su (x)). It is assumed that the couple (r; k) is ( (i; xv 1 ); jxv 1 j) where v is the label of the non-solid path of M(Fact(x)).

7.6.2 Size of factor automata. Bounds on the size of factor automata are similar to those of su x automata. We state the results in this section. We set (Q; i; T; E) = M(Fact(x)). Proposition 7.9. If jxj 6 2, card(Q) = jxj + 1. Otherwise jxj > 3, and jxj + 1 6 card(Q) 6 2jxj 2.

If jxj > 4, the upper bound is reached only when x is in the form ab jxj 2 c for three letters a, b, and c, such that a 6 = b 6 = c.

Proof. The argument of the proof of Corollary 7.4 works again, except that the last letter of x yields the creation of only one state. Therefore, the upper bound on the number of states is one unit less than that of su x automata. By Theorem 7.2, in order to get the maximum number of states, letters x 3 , x 4 , : : :, x jxj 1 should eventually lead to the creation of two states (letters x 1 , x 2 , and x jxj cannot). This happens only when x 1 6 = x 2 , x 2 = x 3 = = x jxj 1 . If x jxj = x jxj 1 the word x is in the form ab m 1 , with m > 3 and a 6 = b, and its factor automaton has exactly m + 1 states. Therefore, we must have x jxj 6 = x jxj 1 to get the 2jxj 2 bound, and this is also su cient. u t Proof. Lemma 7.10 is still valid for factor automata, and gives the upper bound 3jxj 4 for jxj > 3.

The rest can be checked by hand.

To reach the upper bound, regarding Lemma 7.10 again, M(Fact(x)) should have the maximum number of states. Note that if x is in the form ab jxj 2 a, with a; b 2 A and a 6 = b, card(E) = 2jxj 1 only. If x is in the form ab jxj 2 c for three pairwise letters a, b, and c, card(E) = 3jxj 4. Therefore, by Proposition 7.9, this is the only possibility to reach the upper bound. u t 7.6.3 On-line construction. The on-line construction of factor automata is similar to the construction of su x automata (Section 7.3). The main di erence is that the non-solid path of the current automaton is stored and updated after the processing of each letter, and that table F implements x instead of f x that is related to Su (x) . The couple of variables (r; k) represents the path as explained previously. The couple gives access to the waiting list of states that are possibly duplicated afterwards.

The function of Figure 7.15 relies on procedure FA-Extend (given in Figure 7.16) aimed at transforming the current automaton M(Fact(w)) into M(Fact(wa)), a 2 A. The correctness of the function is based on a crucial property stated in the next theorem. For each nonempty word w, we denote by R(M(Fact(w))) the automaton obtained from M(Fact(w)) by removing the state last w and all edges reaching it.

FactorAutomaton(x) 1 (Q; E) (?; ?) 2 i State-Creation 3 Length i] 0 4 F i] nil 5 last i 6 (r; k) (i; 0) 7 for `from 1 up to x 8 loop FA-Extend(`) 9 return (Q; i; Q; E); Length; F Fig. 7.15. On-line construction of the factor automaton of a word x.

FA-Extend(`) The sequence of calls to procedure FA-to-SA behaves like a construction of M(Su (x)) (or just of M(Su (x 0 )), for some pre x x 0 of x). Thus, their accumulated running time is as announced by the theorems of Section 7.3, that is, O(jxj logcard(A)). This sketches the proof of the result. The notion of a failure function to represent e ciently an automaton is implicit in the work of Morris and Pratt (1970). It is intensively used in 26] and 2]. The table-compression method is explained in 4]. It is the base of some implementations of lex (compiler of lexical analyzer) and yacc (compiler of compiler) UNIX software tools that involve automata.

The regular-expression-matching problem is considered for the construction of compilers (see 4] for example). The transformation of a regular expression into an automaton is treated in standard textbooks on the subject. The construction described in Section 4 is by Thompson 32]. Many tools under the UNIX operating system use a similar method. For example the grep command implements the method with reduced regular expressions. While the command egrep operates on complete regular expressions and uses a lazy determinization of the underlying automaton.

The rst linear-time solution of the string-matching problem was given by Morris and Pratt, and improved in 26]. The analogue solution to the dictionary-matching problem was designed by Aho and Corasick 2] and is implemented by the fgrep UNIX command.

Several authors have considered a variant of the dictionary-matching problem in which the set of words changes during the search. This is called the \dynamic-dictionary-matching problem" (see 5], 6], 25]). A related work based on su x automata is treated in 27]. A solution to the problem restricted to uniform dictionaries is given in 11] in the comparison model of computation.

The linear size of su x automata (also called \directed acyclic word graphs" and denoted by the acronym DAWG) and factor automata has been rst noticed by Blumer et al., and their e cient construction is in 9] and 16]. An alternative data structure that stores e ciently the factors (subwords) of a word is the su x tree. It has been rst introduced as a position tree by Weiner 35], but the most practical algorithms are by McCreight 28] and Ukkonen 33]. Su x automata and su x trees have similar applications to the implementation of indexes (inverted les), to pattern matching, and to data compression.

Fig. 2 . 1 .

 21 Fig. 2.1. An automaton recognizing the language fa; bg abaaab.

  .1. AdjacencyLists-Transition(p; a) 1 p state of the couple of label a in G p] 2 if p = nil 3 then p i 4 return p Fig. 3.1. Computation of the transition from a state p by a letter a when an array G of adjacency lists represents the transition function.

FailureFunction

  Fig.3.2. Computation of the transition from a state p by a letter a when a subtransition and an array F corresponding to a failure function represent the transition function.

4 .

 4 Matching regular expressions 4.1 Outline Problem 4.1. (Regular-expression-matching problem.) Given a regular expression x, preprocess it in order to locate all occurrences of words of Lang(x) that occur in any given word y.

Fig. 4 . 1 .

 41 Fig. 4.1. Normalized extended automata recognizing the regular expressions 0 (I), 1 (II), and a (III) for some a 2 A.

Fig. 4 . 5 .

 45 Fig. 4.5. Algorithm for testing whether a word y belongs to Lang(x), x being a regular expression.

Figure 4 . 6 . 6 occurrenceif t 2 CFig. 4 . 6 .

 466246 Fig. 4.6. Algorithm for computing pre xes of a word y that belong to A Lang(x), x being a regular expression.

Fig. 5 . 2 .

 52 Fig. 5.2. The trie of fab;babb;bbg.

Fig. 5 . 4 .

 54 Fig. 5.4. The linear dictionary-matching automaton of fab;babb;bbg.

Fig. 5 . 5 .

 55 Fig. 5.5. The optimized representation of D(fab; babb; bbg).

Fig. 5 . 6 .

 56 Fig. 5.6. The optimized representation of D('(4)).

  Fig.6.1. During the construction of the string-matching automaton of abaaab, unfolding of the edge ("; a; ") from step \"" (I) to step \a" (II), of the edge (a; b; ") from step \a" to step \ab" (III), and of the edge (ab; a; a) from step \ab" to step \aba" (IV). It is assumed that A = fa; bg.

Fig. 6 . 3 .

 63 Fig. 6.3. A string-matching automaton with the maximum number of signi cant edges. The signi cant edges are the only depicted edges; the target of other edges is 0.

Fig. 6 . 4 .

 64 Fig. 6.4. Construction of the linear string-matching automaton of a word x.

Fig. 6 . 5 .

 65 Fig. 6.5. The string-matching automaton of abacabad without its null edges.

Fig. 7 . 1 .

 71 Fig. 7.1. The minimal deterministic automaton recognizing the su xes of aabbabb.

Fig. 7 . 2 .

 72 Fig. 7.2. A su x automaton with the maximum number of states.

Figure 7 .Fig. 7 .

 77 Figure 7.3 displays a su x automaton whose number of edges is maximum for a word of length 7.

  13 return ((Q; i; T; E); Length; F ) Fig.7.4. On-line construction of the su x automaton of a word x.

Fig. 7 . 5 .Fig. 7 .

 757 Fig. 7.5. From M(Su (x1x2 x` 1)) to M(Su (x1x2 x`)).

Fig. 7 .

 7 Fig. 7.7. M(Su (ccccbbcccd)).

Fig. 7 .

 7 Fig. 7.8. M(Su (ccccbbcccc)).

Fig. 7 .

 7 Fig. 7.9. M(Su (ccccbbcccb)).

Theorem 7 . 5 .

 75 Function SuffixAutomaton can be implemented to work in time O(jxj logcard(A)) within O(jxj) space on each given word x. Proof. The set of states of M(Su (x)) and arrays Length and F require O(card(Q)) space. The set of adjacency lists require O(card(E)) space. Thus, the implementation takes O(jxj) space by Corollaries 7.4 and 7.5.

u t 7 . 4 . 3

 743 Occurrence number. Problem 7.4. (Number of occurrences of w in x.) Given w 2 Fact(x), nd how many times w occurs in x. Proposition 7.4. The automaton M(Su (x)) can be preprocessed in time O(jxj) so that the number of occurrences in x of any word w 2 Fact(x) can be computed in time O(jwj log card(A)) within O(jxj) space.

Fig. 7 .

 7 Fig. 7.11. Minimal deterministic automaton recognizing the factors of aabbabb.

Figure 7 .

 7 Figure 7.13 displays a factor automaton having the maximum number of states for a word of length 7.Proposition 7.10. If jxj 6 2, jxj 6 card(E) 6 2jxj 1. Otherwise jxj > 3, and jxj 6 card(E) 6 3jxj 4. If jxj > 4, the upper bound is reached only when x is in the form ab jxj 2 c for three pairwise distinct letters a, b, and c.

Fig. 7 .

 7 Fig. 7.13. A factor automaton with the maximum number of states.

Figure 7 .Fig. 7 .

 77 Figure 7.14 displays a factor automaton having the maximum number of edges for a word of length 7.

  books are entirely devoted to pattern matching. One can refer to 19] and 31]. The topic is treated in some books on the design of algorithms such as 3], 7], 23], 15]. An extensive bibliography is also included in 1], and the subject is partially treated in relation to automata in 29].

  Computation of the transition from a state p by a letter a in the table-compression method with suitable arrays fail, base, target, and check.

	TableCompression-Transition(p; a) 1 while check base p] + a] 6 = p 2 loop p fail p] 3 return target base p] + a]
	Fig. 3.3.

  These two operations are respectively performed by functions Closure and Transitions of Figures 4.3 and 4.4. With careful implementation, based on standard manipulation of sets and queues, the time and the space required to compute a closure or the transitions from a closure are linear in the size of involved sets of states.

	Closure(E; S) 1 R S 2 # EmptyQueue 3 for each state p in S 4 loop Enqueue(#; p) 5 while not QueueIsEmpty(#) 6 loop p Dequeue(#) 7

  From M(Fact (x1 x` 1)) to M(Fact(x1 x`)).

	1 a x2 if (F last ];a) 6 = nil 3 then newlast State-Creation 4 E E + f(lasta; newlast)g 5 Length newlast] Length last] + 1 6 F newlast] (F last ];a) 7 if k = `and Length F last]] + 1 = Length (F last]; a)] 8 then (r; k) (newlast; `+ 1) 9 else FA-to-SA(r; k) 10 newlast State-Creation 11 p last 12 loop E E + f(p; a; newlast)g 13 p F p] 14 while p 6 = nil and (p; a) = nil 15 if p = nil 16 then F newlast] i 17 (r; k) (newlast; `+ 1) 18 else q (p; a) 19 F newlast] q 20 if Length p] + 1 = Length q] 21 then (r; k) (newlast; `+ 1) 22 else (r; k) (last; `) 23 last newlast
	Fig. 7.16.

The next two lemmas provide recurrence relations satis ed by the numbers se u (p). The expressions are stated using the following notation: given a predicate e, the integer denoted by (e) has value 1 when e is true, and value 0 otherwise. Lemma 6.3. Let (u; a) 2 A A. For each v 2 Pref (ua), we have: se ua (v) = 8 < : se u (Bord(ua)); if v = ua, se u (u) + (Bord(ua) = "); if v = u, se u (v); otherwise.

Proof. This is a straightforward consequence of Lemma 6.1. u t Lemma 6.4. Let u 2 A + . For each v 2 Pref (u), we have:

se u (Bord(u)); if v = u, se u (Bord(v)) + (Bord(va) = "); if va 2 Pref (u) for some a 2 A, 1; if v = ". Proof. Follows from Lemma 6.3.

u t

The next lemma is the \cornerstone" of the proof of the logarithmic bound given in Proposition 6.2 stated afterwards. Lemma 6.5. Let u 2 A + . For each v 2 Pref (u)nf"g, we have: 2jBord(v)j > jvj =) se u (Bord(v)) = se u (Bord 2 (v)): Proof. Set k = 2jBord(v)j jvj, w = v 1 v 2 v k , and a = v k+1 . Since wa is a proper border of Bord(v)a, the border of Bord(v)a is nonempty. Then we apply Lemma 6.4 to the proper pre x Bord(v) of u. u t Proposition 6.2. Let u 2 A . For each state p of M(A u), we have: se u (p) 6 1 + blog 2 (jpj + 1)c: Proof. We prove the result by induction on jpj. From Lemma 6.4, this is true if jpj = 0. Next, suppose jpj > 1.

Let j be the integer such that 2 j 6 jpj + 1 < 2 j+1 ; then let k be the integer such that jBord k+1 (p)j + 1 < 2 j 6 jBord k (p)j + 1: Let `2 f0; : : :; k 1g; we have 2jBord `+1 (p)j > 2 j+1 2 > jpj > jBord `(p)j; which implies se u (Bord `+1 (p)) = se u (Bord `+2 (p)) from Lemma 6.5. Hence we get the equality se u (Bord(p)) = se u (Bord k+1 (p)): From the induction hypothesis applied to the state Bord k+1 (p), we get se u (Bord k+1 (p)) 6 1 + blog 2 (jBord k+1 (p)j + 1)c: Now Lemma 6.4 implies se u (p) 6 se u (Bord(p)) + 1:

This shows that se u (p) 6 j + 1 = 1 + blog 2 (jpj + 1)c; and ends the proof.

u t

Another often used property of the syntactic congruence associated with Su (x) is that it partitions the su xes of factors into intervals (with respect to the lengths of su xes). Lemma 7.3. Let u; v; w 2 Fact(x). Then, if u 2 Su (v), v 2 Su (w), and u Su (x) w, we have u Su (x) v Su (x) w. Proof. By Lemma 7.1, we have the inclusions w 1 Su (x) v 1 Su (x) u 1 Su (x). But then, the equality u 1 Su (x) = w 1 Su (x) implies the conclusion of the statement. u t

A consequence of the next property is that the direct inclusion of right contexts relative to Su (x) induces a tree structure on them. In the tree, the parent link corresponds to the proper direct inclusion. This link is discussed in Section 7.2.2 where it is called the \su x function". Corollary 7.1. Let u; v 2 A . Then, one of the three following conditions holds:

Proof. We just have to show that if u 1 Su (x) \ v 1 Su (x) 6 = ?, then we have the inclusion u 1 Su (x) v 1 Su (x) or the inclusion v 1 Su (x) u 1 Su (x). Let z 2 u 1 Su (x) \ v 1 Su (x). Then, uz and vz are su xes of x. So, u and v are su xes of xz 1 , which implies that one of the words u and v is a su x of the other. Therefore, the conclusion follows by Lemma 7.1. u t 7.2.2 Su x function. We consider the function s x : Fact(x) ! Fact(x) de ned for each nonempty word v in Fact(x) by s x (v) = the longest u 2 Su (v) such that u 6 Su (x) v:

Regarding Lemma 7.1, this is equivalent to s x (v) = the longest u 2 Su (v) such that v 1 Su (x) u 1 Su (x): The function s x is called the su x function relative to x. An obvious consequence of the de nition is that s x (v) is a proper su x of v. The next lemma shows that the su x function s x induces what we call a \su x link" on states of M(Su (x)). Lemma 7.4. Assuming x 6 = ", let u; v 2 Fact(x)nf"g. If u Su (x) v, then s x (u) = s x (v). Proof. From Lemma 7.2 we can assume without loss of generality that u 2 Su (v). The word u cannot be a su x of s x (v), because Lemma 7.3 would then imply s x (v) 1 Su (x) = v 1 Su (x), which contradicts the de nition of s x (v). Therefore, s x (v) is a su x of u. Since, by de nition, it is the longest su x of v non equivalent to it, it is equal to s x (u). u t Lemma 7.5. If x 6 = ", s x (x) is the longest su x of x that occurs at least twice in x. Proof. The set x 1 Su (x) is equal to f"g. Since x and s x (x) are not equivalent, the set s x (x) 1 Su (x) contains some nonempty word z. Therefore, s x (x)z and s x (x) are su xes of x, which proves that s x (x) occurs at least twice in x. Any su x w of x, longer than s x (x), satis es w 1 Su (x) = x 1 Su (x) = f"g by de nition of s x (x). Thus, w occurs only as a su x of x, which ends the proof. u t The next lemma shows that the image of a factor of x by the su x function is a word of maximum length in its own congruence class. This fact is needed in Section 7.5 where the su x automaton is used as a matching automaton. Lemma 7.6. Assuming x 6 = ", let u 2 Fact(x)nf"g. Then, any word equivalent to s x (u) is a su x of s x (u). Proof. Let w = s x (u) and v Su (x) s x (u). The word w is a proper su x of u. If the conclusion of the statement is false, Lemma 7.2 insures that w is a proper su x of v. Let z 2 u 1 Su (x). Since w is a su x of u and is equivalent to v, we have z 2 w 1 Su (x) = v 1 Su (x). Therefore, u and v are both su xes of xz 1 , which implies that one of them is a su x of the other. But this contradicts either the de nition of w, or the conclusion of Lemma 7.3. This proves that v is necessarily a su x of w. u t 7.2.3 State splitting. In this section we present the properties that yield to the on-line construction of su x automata described in Section 7.3. This is achieved by deriving relations between the congruences Su (w) and Su (wa) for any couple (w; a) 2 A A. The rst property, stated in Lemma 7.8, is that Su (wa) is a re nement of Su (w) . The next lemma shows how right contexts evolves.

Lemma 7.7. Let w 2 A and a 2 A. For each u 2 A , we have: u 1 Su (wa) = u 1 Su (w)a f"g; if u 2 Su (wa), u 1 Su (w)a;

otherwise.

Proof. Note rst that " 2 u 1 Su (wa) is equivalent to u 2 Su (wa). So, it remains to prove u 1 Su (wa)nf"g = u 1 Su (w)a.

Let z be a nonempty word in u 1 Su (wa). This means uz 2 Su (wa). The word uz can then be written uz 0 a with uz 0 2 Su (w). Thus, z 0 2 u 1 Su (w), and z 2 u 1 Su (w)a.

Conversely. Let z be a (nonempty) word in u 1 Su (w)a. It can be written z 0 a for some z 0 2 u 1 Su (w). Therefore, uz 0 2 Su (w), which implies uz = uz 0 a 2 Su (wa), that is z 2 u 1 Su (wa). u t Lemma 7.8. Let w 2 A and a 2 A. The congruence Su (wa) is a re nement of the congruence Su (w) , that is, for each u; v 2 A , u Su (wa) v implies u Su (w) v. Proof. We assume u Su (wa) v, that is, u 1 Su (wa) = v 1 Su (wa), and prove u Su (w) v, that is, u 1 Su (w) = v 1 Su (w). We only show that u 1 Su (w) v 1 Su (w) because the reverse inclusion follows by symmetry.

If u 1 Su (w) is empty, the inclusion trivially holds. Otherwise, let z 2 u 1 Su (w). This is equivalent to uz 2 Su (w), which implies uza 2 Su (wa). The hypothesis gives vza 2 Su (wa), and thus vz 2 Su (w) or z 2 v 1 Su (w), which achieves the proof. u t Given a word w, the congruence Su (w) partitions A into classes. And Lemma 7.8 remains to say that these classes are union of classes according to Su (wa) , a 2 A. It turns out that only one or two classes according to Su (w) split into two sub-classes to get the partition induced by Su (wa) . One of the class that splits is the class of words not occurring in w. It contains the word wa itself that gives rise to a new class and a new state of the su x automaton (see Lemma 7.9). Theorem 7.2 and its corollaries exhibit conditions under which another class also splits and how it splits. Lemma 7.9. Let w 2 A and a 2 A. Let z be the longest su x of wa occurring in w. If u is a su x of wa such that juj > jzj, u Su (wa) wa.

Proof. This is a straightforward consequence of Lemma 7.5. u t Theorem 7.2. Let w 2 A and a 2 A. Let z be the longest su x of wa occurring in w. Let z 0 be the longest factor of w such that z 0 Su (w) z. For each u; v 2 Fact(w), we have:

u Su (w) v and u 6 Su (w) z =) u Su (wa) v: Furthermore, for each u 2 A , we have: u Su (w) z =) u Su (wa) z; if juj 6 jzj, u Su (wa) z 0 ; otherwise.

Proof. Let u; v 2 Fact(w) be such that u Su (w) v, that is, u 1 Su (w) = v 1 Su (w). We rst assume u 6 Su (w) z and prove u Su (wa) v, that is u 1 Su (wa) = v 1 Su (wa). By Lemma 7.7, we just have to prove that u 2 Su (wa) is equivalent to v 2 Su (wa). Indeed, it is even su cient to prove that u 2 Su (wa) implies v 2 Su (wa) because the reverse implication comes by symmetry.

Assume then that u 2 Su (wa). Since u 2 Fact(w), u is a su x of z, by de nition of z. So, we can consider the largest integer k > 0 such that juj 6 js w k (z)j. Note that s w k (z) is a su x of wa (as z is), and that Lemma 7.3 insures that u Su (w) s w k (z). So, v Su (w) s w k (z) by transitivity. { nd a longest factor repeated in x; { nd a shortest factor occurring only once in x. Problem 7.6. (Longest repeated factor in x.) Produce a longest word u 2 Fact(x) that occurs twice in x.

If the table NB used to compute the number of occurrences of a factor is already computed, the problem is equivalent to nd the deepest state p in M(Su (x)) for which NB p] > 1. The label of the path from the initial state to p is a solution to the problem. In fact, the problem can be solved without any use of the table NB. We just consider the deepest state p which satis es one of the two conditions: (i) the degree of p is at least two; (ii) p is a terminal state and the degree of p is at least one. Doing so, no preprocessing on M(Su (x)) is even needed, which gives the following result. Proposition 7.6. With M(Su (x)), computing a longest repeated factor of x can be performed in time O(jxj).

Given a longest repeated factor u of x, ua is a factor of x for some letter a. It is clear that this word is a shortest factor occurring once only in x, i.e., this word is a solution to the dual problem. Hence, the proposition also holds for the second problem.

As string-matching automata

The su x automaton M(Su (x)) of x can be used to solve the string-matching problem, to locate the occurrences of x in a word y. The search procedure behaves like the search phase of algorithm Matcher (see Section 2) that processes y in an on-line manner. The existence of failure links in M(Su (x)) is essential for this application, which gives them their name. The search procedure is a consequence of a generic procedure, given Figure 7.10, that can be used for other purposes. 7.5.1 Ending factors. Procedure EndingFactors of Figure 7.10 computes the longest factor of x ending at each position in y, or more exactly the length of this factor. More precisely, we de ne for each k 2 f0; : : :; jyjg the number `k = maxfjwj j w 2 Su (y 1 y 2 y k ) \ Fact(x)g: The procedure EndingFactors performs an on-line computation of the sequence (`k) 06k6jyj of lengths of longest ending factors. The output is given as a word on the alphabet f0; : : :; jxjg. Function length x of Section 7.2 (implemented via table Length) is used to reset properly the current length just after a su x link has been traversed.

The core of procedure EndingFactors is the computation of transitions with the failure table F (implementing the su x link f x ), similarly as in the general method described in Sections 3. [START_REF] Aho | Compilers { Principles, techniques and tools[END_REF] 7.5.2 Optimization of su x links. Indeed, instead of the su x link f x , we rather use another link, denoted by fx , that optimizes the delay of searches. Its de nition is based on transitions de ned on states of the automaton, and parallels what is done in Section 5.4.

The \follow set" of a state q of M(Su (x)) is Follow x (q) = fa j a 2 A; (q; a) is de nedg:

Then, fx (q) is de ned by the relation: fx (q) = f x (q); if Follow x (f x (q)) * Follow x (q), fx (f x (q)); otherwise. Note that fx (q) can be left unde ned with this de nition.

A property of Follow x sets simpli es the computation of fx . In the su x automaton we always have Follow x (q) Follow x (f x (q)). This is because f x (q) corresponds to a su x v of any word u for which q = (i; u). Then, any letter following u in x also follows v (see Lemma 7.1). And this property transfers to follow sets of q and f x (q) respectively. With this remark, the de nition of the failure function fx can be equivalently stated as: fx (q) = f x (q); if the degrees of q and of f x (q) are di erent, fx (f x (q)); otherwise.

Thus, the computation of fx has only to consider degrees of states of the automaton M(Su (x)), and can be executed in linear time. Proposition 7.7. For procedure EndingFactors using a table, say F, implementing the su x link fx instead of the table F, the delay is O(card(A)). Proof. This is a consequence of: Follow x (q) Follow x ( fx (q)) A for any state q for which fx (q) is de ned. u t 7.5.3 Searching for rotations. The knowledge of the sequence of lengths (`k) 06k6jyj leads to several applications such as searching for x in y, computing lcf (x; y), the maximum length of a factor common to x and y, or computing the subword distance between two words: d(x; y) = jxj + jyj 2 lcf (x; y): The computation of positions of x in y relies on the simple observation:

`k = jxj () x occurs at position k jxj in y:

The same remark applies as well to design an e cient solution to the next problem. A rotation (or a conjugate) of a word u is a word in the form wv, w; v 2 A , when u = vw.

Theorem 7.7. Let w 2 A , z the longest su x of w that occurs at least twice in it, and a 2 A. If za 6 2 Fact(w), then, disregarding terminal states, R(M(Fact(wa))) = M(Su (w)):

Before proving the theorem, we prove the following lemma.

Lemma 7.11. Let w 2 A , z the longest su x of w that occurs twice in it, and a 2 A. If za 6 2 Fact(w), then, for each s 2 A , we have s Fact(wa) z =) s 2 Su (z): Proof. The condition on z implies that (za) 1 Fact(wa) = f"g. Then, we have (sa) 1 Fact(wa) = f"g, which implies that s is a su x of w. Since z occurs twice in w, this is also the case for s (because some word ta, with t 6 = ", belongs to z 1 Fact(wa) = s 1 Fact(wa)). Therefore, by the de nition of z, s is a su x of z. u t Proof of Theorem 7.7. We prove that, for any words u; v 2 Fact(w), u Fact(wa) v () u Su (w) v;

which is a re-statement of the conclusion of the theorem.

Assume rst u Fact(wa) v. After Lemma 7.2 we can consider, for example, that u 2 Su (v). Then, v 1 Su (w) u 1 Su (w), and to prove u Su (w) v it remains to show u 1 Su (w) v 1 Su (w).

Let t 2 u 1 Su (w). We show that t 2 v 1 Su (w). Since ut 2 Su (w), we have uta 2 Su (wa) Fact(wa), and using the hypothesis, namely u Fact(wa) v, we get that vta 2 Fact(wa). If ut occurs only once in w, (ut) 1 Fact(w) = f"g. Therefore, (vt) 1 Fact(w) = f"g because Fact(wa) is a congruence, which proves that vt 2 Su (w), i.e. t 2 v 1 Su (w). If ut occurs at least twice in w, by de nition of z, ut is a su x of z. So, z = z 0 ut for some pre x z 0 of z. Then, z 0 vt Fact(wa) z, which implies that vt is a su x of z and consequently of w by Lemma 7.11. Hence again, t 2 v 1 Su (w). This ends the rst part of the statement.

Conversely, let us consider that u Su (w) v, and prove u Fact(wa) v. Without loss of generality, we assume u 2 Su (v), so it remains to prove u 1 Fact(wa) v 1 Fact(wa).

Let t 2 u 1 Fact(wa). If t = ", t 2 v 1 Fact(wa) because v 2 Fact(w). We then assume that t is a nonempty word. If ut 2 Fact(w), for some t 0 2 A , utt 0 2 Su (w), that is tt 0 2 u 1 Su (w). The hypothesis u Su (w) v implies tt 0 2 v 1 Su (w), and consequently t 2 v 1 Fact(wa). If vt 6 2 Fact(w), t is a su x of wa. It can be written t 0 a for some su x t 0 of w. So, t 0 2 u 1 Su (w), and then t 0 2 v 1 Su (w) which shows that vt 0 is a su x of w. Therefore, t 2 v 1 Fact(wa). This ends both the second part of the statement and the whole proof. u t During the construction of M(Fact(x)), the following property is invariant: let M(Fact(w)) be the current automaton and z be as in Theorem 7.7, then (i; z) = F last]. Consequently, the condition on z that appears in Theorem 7.7 translates into the test \ (F last]; a) 6 = nil". If its value is true, the automaton and the su x z extend, and the procedure FA-Extend updates the pair (r; k) if necessary in a natural way. Otherwise, Theorem 7.7 applies, which leads to rst transform M(Fact(w)) into M(Su (w)). After that, the automaton is extended by the letter a. In this situation, the new non-solid path is composed of at most one edge, as a consequence of Lemma 7.6 (see also the proof of Theorem 7.7).

Finally, we state the complexity of function FactorAutomaton: the construction of factor automata by this function takes linear time on a xed alphabet. Theorem 7.8. Function FactorAutomaton can be implemented to work on the input word x in time O(jxj log card(A)) within O(jxj) space. Proof. If, for a moment, we do not consider the calls to procedure FA-to-SA, it is rather simple to see that there is a linear number of instructions executed to built M(Fact(x)). Implementing the automaton with adjacency lists, the cost of computing a transition is O(logcard(A)). Which gives the O(jxj log card(A)) time for the considered instructions.

The solution of the string-matching problem presented in Section 6 is adapted from an original algorithm of Simon 30]. It has been analyzed and improved by Hancart 24]. These algorithms as well as algorithms in 26] solve the string-pre x-matching problem which is the computation of ending pre xes at each position on the searched word. Breslauer et al. 12] gave lower bounds to this problem that meet the upper bounds of Theorem 6.7. Galil showed in 20] how to transform the algorithms of Knuth, Morris and Pratt, so that the search phase works in real time (independently of the alphabet). This applies as well to the algorithm of Simon.

There are many other solutions to the string-matching problem if we relax the condition that the bu er on the searched word is reduced to only one letter. The most practically e cient solutions are based on the algorithm of Boyer and Moore 10]. With the use of automata, it has been extended to the dictionary-matching problem by Commentz-Walter 14] (see also 1]) and by Crochemore et al. (see 19]). The set of con gurations possibly met during the search phase of a variant of the algorithm of Boyer and Moore in which all information is retained leads to what is called the \Boyer-Moore automaton". It is still unknown if the number of states of the automaton is polynomial as conjectured by Knuth (see [START_REF] Knuth | Fast pattern matching in strings[END_REF][START_REF] Bruy Ere | Automates de Boyer-Moore[END_REF][START_REF] Baeza-Yates | On Boyer-Moore automata[END_REF]). Theorem 6.3 is by Galil and Seiferas 21]. Like their solution, several other proofs (in [START_REF] Crochemore | Two-way string-matching[END_REF][START_REF] Crochemore | String-matching on ordered alphabets[END_REF][START_REF] Plandowski | The zooming method: a recursive approach to time-space e cient string-matching[END_REF]) of the same result are based on combinatorial properties of words (see Chapter \Combinatorics of words").

Other kinds of patterns are considered in the approximate string-matching problem (see 19] for references on the subject). The rst kind arises when mismatches are allowed between a given word and factors of the searched word (base of the Hamming distance). A second kind of patterns arises when approximate patterns are de ned by transformation rules (substitution, insertion, and deletion) that yield the edit distance (see Chapter \String editing and DNA"). This notion is widely used for matching patterns in DNA sequences (see 34]).

Index