Fr Éd

Érique Bassino
email: frederique.bassino@lipn.univ-paris13.fr

Counting occurrences for a finite set of words: combinatorial methods

Keywords: F.2.2. [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.1. [Discrete Mathematics]: Generating functions, Counting problems Statistics, Inclusion-Exclusion, Generating Functions, Aho-Corasick Automaton

In this article, we provide the multivariate generating function counting texts according to their length and to the number of occurrences of words from a finite set. The application of the inclusion-exclusion principle to word counting due to Goulden and Jackson (1979, 1983) is used to derive the result. Unlike some other techniques which suppose that the set of words is reduced (i.e., where no two words are factor of one another), the finite set can be chosen arbitrarily. Noonan and Zeilberger (1999) already provided a MAPLE package treating the non-reduced case, without giving an expression of the generating function or a detailed proof. We provide a complete proof validating the use of the inclusion-exclusion principle. Some formulae for expected values, variance and covariance for number of occurrences when considering two arbitrary sets of finite words are given as an application of our methodology.

INTRODUCTION

Enumerating sequences with given combinatorial properties is rigorously formalized since the end of the seventies and the beginning of the eighties by Goulden and Jackson [START_REF] Goulden | An inversion theorem for clusters decompositions of sequences with distinguished subsequences[END_REF]1983] and by Guibas and Odlyzko [Guibas and Odlyzko 1981a;1981b].

The former [START_REF] Goulden | An inversion theorem for clusters decompositions of sequences with distinguished subsequences[END_REF]1983] introduce a very powerful method of inclusion-exclusion to count occurrences of words from a reduced set of words (i.e., a set where no word is factor of another word of the set) in texts; this method is characterized by counting texts where some occurrences are marked (other terms are pointed or anchored) and then removing multiple counts of the same text (text counted several times with different markings). We refer later to this by inclusion-exclusion method.

Goulden-Jackson counting is typically multivariate, a formal parameter being associated to each word.

The latter [Guibas and Odlyzko 1981a;1981b] introduce the notion of autocorrelation of a word that generalizes to correlation between words, this notion being implicit in Goulden and Jackson. Formal non-ambiguous manipulations over languages translate into generating functions; we refer to this later by formal language method. Unlike Goulden and Jackson, Guibas and Odlyzko consider univariate cases, like enumerating sequences avoiding a pattern, or sequences terminating with a first occurrence of a pattern in a text (see also [START_REF] Sedgewick | An Introduction to the Analysis of Algorithms[END_REF]). Régnier and Szpankowski [Régnier and Szpankowski 1997] extends this further to multivariate analysis and simultaneous counting of several words; following up works of these authors consider a Markovian source on the symbol emission [Régnier and Szpankowski 1998;Régnier 2000]. See also the books of Szpankowski [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF]] and Lothaire [START_REF] Lothaire | Applied Combinatorics on Words. Encyclopedia of Mathematics[END_REF]]. Bourdon and Vallée [Bourdon and Vallée 2002;[START_REF] Bourdon | Pattern matching statistics on correlated sources[END_REF] apply the previous analysis to dynamical sources. [START_REF] Prum | Finding words with unexpected frequencies in deoxyribonucleic acid sequences[END_REF], [START_REF] Reinert | Compound Poisson and Poisson process approximations for occurrences of multiple words in Markov chains[END_REF]], Reinert et al. [START_REF] Reinert | Probabilistic and statistical properties of words: an overview[END_REF]], and Roquain and Schbath [START_REF] Roquain | Improved compound Poisson approximation for the number of occurrences of multiple words in a stationary Markov chain[END_REF] follow a more probabilistic approach.

Noonan and Zeilberger [START_REF] Noonan | The Goulden-Jackson Method: Extensions, Applications and Implementations[END_REF] extend the inclusion-exclusion method of Goulden and Jackson and solve the general non-reduced case (words may be factor of other words), implementing corresponding MAPLE programs, without however completely publishing the explicit result formulae. Recently Kong [START_REF] Kong | Extension of Goulden-Jackson cluster method on pattern occurrences in random sequences and comparison with Régnier Szpankowski method[END_REF]] applies the results of Noonan and Zeilberger for the reduced case to an asymmetrical Bernoulli (also called memoryless) model for the generation of symbols. He also compares the Goulden and Jackson method to the Régnier and Szpankowski method, emphasizing the conceptual simplicity of the inclusion-exclusion approach. It is however useful to note that the formal language approach provides access to information that the inclusion-exclusion method does not, such as the waiting time for a first match of a word or the time separating two matches of the same word or of two different words (in both cases eventually forbidding matches with other words). There is however no known solutions to the general problem of words counting by the formal language method.

A third approach is possible by use of automata. Nicodème et al. [Nicodème et al. 2002] use classical algorithms to (1) build a marked deterministic automaton recognizing a regular expression and (2) translate into generating function by the Chomsky-Sch ützenberger algorithm [START_REF] Chomsky | The algebraic theory of context-free languages[END_REF]; this provides the bivariate generating function counting the matches. A variation of the method extends the results to Markovian sources. This result applies immediately to a set of words considered as a regular expression. Nicodème [Nicodème 2003] extends this to multivariate counting by taking the product of marked automata (with an automaton and a mark associated to a word) and to sets of words with possible errors1 . Notice that, when handling finite languages, step (1) of the automaton approach may be directly done by building the Aho-Corasick automaton, which is specifically designed for pattern-matching.

Each of the three above-mentioned approaches did develop quite independently and partially unaware of each other.

In this article we focus on a fundamental object, called multivariate generating function, which allows a concise mathematical description of occurrences statistics in random texts. More precisely, we describe two approaches to compute the multivariate generating function F U counting texts according to their length and to their number of occurrences of words from a pattern or set U = {u 1 , . . . , u r } of r words. The resulting generating function is rational; once computed, it is a simple task to obtain all kind of statistics (see Section 6 for some examples). The reader is also referred to [START_REF] Flajolet | Analytic Combinatorics[END_REF]] for a general background on generating functions.

Historically, research on counting occurrences for finite cases considered separately the so-called "reduced" case, which is easier, and where no word of the pattern is factor of another word of the pattern; in the opposite or "non-reduced" case, there are no conditions on the pattern. We focus on methods which solve the problem in this latter case (as example the pattern U can contain u 1 = abbababa and u 2 = baba although u 2 is a factor of u 1 ). Note that in the non-reduced case, the count of matches that we consider here may exceed the count of positions of the texts at which an occurrence terminates; in contrary, in the reduced case, these two counts are identical. We aim at presenting for the general counting problem a novel approach and a full proof of results partially in Noonan and Zeilberger [START_REF] Noonan | The Goulden-Jackson Method: Extensions, Applications and Implementations[END_REF].

This article is organized as follows. We define in Section 2 our notations. In Section 3 we present an approach using the Aho-Corasick automaton that solves the general (non-reduced) problem; we also consider the complexity of this method. We present in Section 4 an intuitive approach to the inclusion-exclusion method that [START_REF] Goulden | Combinatorial Enumeration[END_REF] applied to reduced sets of words. We describe and prove in Section 5 our results that follow from the analytic inclusion-exclusion principle in the general case of word counting; algorithmic aspects are also considered in this section. As an application of our methodology, Section 6 provides precise formula for some statistics (expectation and variance of any set of finite words, and covariance for number of occurrences when considering two arbitrary sets of finite words).

BASIC NOTATIONS

Let A be the alphabet on which the words are written and U = {u 1 , u 2 , . . . , u r } be a finite set (or pattern) of distinct words on the alphabet A. By convention, in this article, words in a set U are always indexed in lexicographic order. We will also consider that in a single word pattern U = {u}, the word u has index 1.

Weights. We denote π(w) the weight of the word w. The weight could be a formal weight over the commutative monoid A (i.e., π(ababab) = α 3 β 3 ), or the probability generating function in the Bernoulli (also called memoryless) setting, π(w) = Pr(w) (the probability of w in this model), or even π(w) = 1 for a uniformly weighted model over all words (enumerative model).

Representing occurrences. This article is focused on statistics of occurrences of words of U with possible overlaps in texts. A convenient way to represent occurrences, adopted throughout this article, is to associate to a text w of length n a sequence O = (O i ) n i=1 called the occurrence index of the pattern U in the text w, defined, for 1 ≤ i ≤ |w|, O i ⊂ {1, . . . , r}, where Card(U) = r, as O i = {j | u j has an occurrence ending at position i of w}.

For instance let us consider the case of a text w = aababaabbbabaa and a simple pattern formed with one word u = aba. Then the occurrence index O of the pattern {u} in w verifies

O i = {1} if i ∈ {4, 6, 13} ∅ otherwise
Notice that we have selected (what we refer next as distinguished) all occurrences of u in w. Later on, along our needs, we will select or distinguish only a subset of those occurrences.

Generating functions. For any (possibly infinite) set of words H, we denote H(z) = h∈H π(h)z |h| the univariate generating function of H, where z is a formal variable marking the length of the words. For instance the generating function of the alphabet A is A(z) = α∈A π(α)z. We consider also multivariate generating functions which take into account statistics of occurrences. When considering a pattern (denoted as a set) {u 1 , . . . , u j , . . . , u r }, we will typically use the variables t j and x j to count the number of occurrences of the word u j ; as we shall see later there will be a need for two variables, although they are in a very simple relation to each other. If the pattern is composed of a single word U = {u}, we use the variables t and x. Given a r-row vector x = (x 1 , . . . , x r ) of formal variables and a r-row vector j = (j 1 , . . . , j r ) of integers, we will denote by x j the product r i=1 x ji i . To any set of words X , we can associate a formal series or generating function that gathers the counts statistics

X(z) = w∈X π(w)z |w| x τ (w) ,
where τ (w) = (|w| 1 , . . . , |w| r ), and |w| i is the total number of occurrences of u i in w (with possible overlaps). For instance, the generating function of the (composed of a single text) set

X = {abaaabaabb} with U = {u 1 = aa, u 2 = baa} is X(z, x 1 , x 2 ) = z 10 π(a) 6 π(b) 4 x 3 1 x 2 2 .
In this article we describe how to compute in the most general case the multivariate generating function F U (z, x) counting texts from A according to their length and to the number of occurrences (with overlap) of words from a set U, w) .

F U (z, x) = F (z, x) := w∈A π(w)z |w| x τ (
(1)

Autocorrelation and correlation of words. We recall here the classical definitions of autocorrelation of one word and of correlation of a word with another word. The autocorrelation set C u of a word u is defined as usual as

C u = {h, u • h = y • u with |y| < |u|};
note that the empty word ε belongs to C u . We use the notations C u (z) or C(z) if there is no ambiguity about the word considered for the autocorrelation polynomial of the word u.

We define similarly the correlation set C u,v from a word u to a word v as

C u,v = {h; u • h = y • v, |y| < |u|; } (2)
Note that C u,u is the autocorrelation set of the word u and that if u = v the empty word ε does not belong to the set C u,v .

AUTOMATON APPROACH

We resort in this section to the well-known Aho-Corasick algorithm [START_REF] Aho | Efficient String Matching: An Aid to Bibliographic Search[END_REF][START_REF] Crochemore | Jewels of Stringology[END_REF] which builds from a finite set of words U a (not necessarily minimal) deterministic complete automaton recognizing the language A U. This automaton denoted by A U is the basis of many efficient algorithms on string matching problems and is often called the string matching automaton. It is usually described by the trie built upon the set of input words together with a failure function. Let T U be the ordinary trie representing the set U, seen as a finite deterministic automaton (Q, δ, ε, T ), where the set of states is Q = Pref(U) (prefixes of words in U), the initial state is ε (denoting ε the empty word), the set of final states is T = Pref(U)∩A U, and the transition function δ is defined on Pref(U) × A by

δ(p, x) = px if px ∈ Pref(U), Border(px) otherwise,
where the failure function Border() is defined by

Border(v) =
the longest proper suffix of v in Pref(U) if it is defined, or ε otherwise.

In the following we identify a word v ∈ Pref(U) with the node reached by reading the letters of v while following the corresponding transitions on the tree seen as an automaton, so that Border() defines also a map from the set Pref(U) on the set of nodes of the tree. There are efficient O(|U|) algorithms [START_REF] Aho | Efficient String Matching: An Aid to Bibliographic Search[END_REF][START_REF] Crochemore | Jewels of Stringology[END_REF] linear both in time and space to build such a tree structure and the auxiliary Border() function.

The matrix T(x) (with x an r-vector of formal variables) denotes the weighted transition matrix of the Aho-Corasick automaton where the variable x i marks the states accepting the word u i . The generating function is expressed as

F (z, x) = w∈A π(w)z |w| x τ (w) = (1, 0, • • • , 0) (I -zT(x)) -1    1 . . . 1    , (3)
where π(w) can be viewed as the weight of the word w.

Example 3.1. Let U = {aa, aab}. Ordering the states of the automaton following the lexicographical order, we have, with α = π(a), β = π(b), and x = (x 1 , x 2 )

T(x 1 , x 2 ) =    β α 0 0 β 0 αx 1 0 0 0 αx 1 βx 2 β α 0 0    ,
F (z, x 1 , x 2 ) = 1 -α(x 1 -1)z 1 -z(αx 1 + β -αβ(x 1 -1)z + α 2 βx 1 (x 2 -1)z 2 ) .
As mentioned in the introduction, a myriad of information can be extracted from such a generating function. The next few examples illustrate basic uses of generating functions.

-The coefficient

[z n x n1 1 x n2 2 ]F (z, x 1 , x 2 )
is the probability in the Bernoulli model (where α + β = 1) that a random text of size n has n 1 occurrences of aa and n 2 occurrences of aab.

-In the enumerative case (α = β = 1), the coefficient

[z n x n1 1 x n2 2 ]F (z, x 1 , x 2
) counts the number of words of length n with n 1 occurrences of aa and n 2 occurrences of aab. Any computer algebra system can compute the first terms of the Taylor series of a rational function. In the example above, we have

F (z, x 1 , x 2 ) =1 + 2z + (x 1 + 3)z 2 + (x 1 x 2 + x 1 + x 2 1 )z 3 + (3x 1 x 2 + 2x 1 + x 2 1 + x 2 1 x 2 + x 3 1 + 8)z 4 + O(z 5 );
this entails for instance that amongst the words of length 4 (corresponding to the term in z 4 ), we have the following correspondence between the terms of the generating function, the texts, and the occurrences statistics τ (w) of aa and aab in a text w. Term Texts w of length 4 τ (w) 3x 1 x 2 {baab, aabb, aaba}

(1, 1) 2x 1 {bbaa, abaa} (1, 0) x 2 1 {baaa} (2, 0) x 2 1 x 2 {aaab} (2, 1) x 3 1 {aaaa}
(3, 0) 8 {bbbb, bbba, bbab, babb, baba, abbb, abba, abab} (0, 0)

Complexity. Let L = u∈U |u| be the sum of the lengths of the words of U. We first have to compute the Aho-Corasick automaton and this can be done classically in time O(L) for a finite alphabet. The automaton can have up to L states. Denoting by N the number of states of the Aho-Corasick automaton, the transitions matrix T is of size N2 , but in general this matrix is sparse: only N × Card A entries are non-zero (since the automaton is complete and deterministic with Card A transitions from each state).

So the complexity to obtain the counting multivariate generating function by this approach is basically the one of inverting a relatively sparse matrix of the form I-zT(x) all terms of which are linear polynomials in z with coefficients that are monomials of the form α x εi i (with α = π( ) for ∈ A and ε i ∈ {0, 1}); these coefficients correspond to the transition matrix of the automaton. The limit of this approach is the fact that the size of the transition matrix can grow rapidly if we consider many rather long words. In the two next sections, we adopt the analytic inclusion-exclusion approach which leads also to solve a system of equations, but then the size of the system is r × r (where r is the number of words in U).

REDUCED CASE OF WORD COUNTING BY INCLUSION-EXCLUSION

We give in this section an intuitive introduction to the inclusion-exclusion method for words counting of [START_REF] Goulden | Combinatorial Enumeration[END_REF]. This method uses a principle of overcounting that is later reversed by a simple algebraic substitution; the overall process is known as analytic inclusion-exclusion. Note that the language approach [Régnier 2000] that follows previous work [Régnier [START_REF] Égnier | On Pattern Frequency Occurrences in a Markovian Sequence[END_REF]] provides the same multivariate generating functions as Goulden and Jackson do. The principle of overcounting and inclusion-exclusion however has the property of extending nicely to the general case of non-reduced patterns that we present in the next section.

Intuitive approach to counting by inclusion-exclusion

The idea behind inclusion-exclusion counting is that it is sometimes harder to specify a set of objects satisfying simultaneously a collection of conditions than a set of objects which violates some of these conditions 2 .

Thus we introduce the notion of decorated text which allows for distinguishing only a subset of the occurrences of the pattern.

where and are the indices that signal the end positions of the occurrences of u 1 and u 2 respectively; we remark that two words can end at the same position.

CONVENTION 4.2. When considering a word u, the associated decorated word built upon u, where the only distinguished occurrence is u itself, is denoted by the sans-serif letter u . The last two decorated texts correspond respectively to the respective cases where no occurrence is distinguished and where all occurrences are distinguished (the fully decorated case).

Naturally, a text with exactly k occurrences of a pattern will give rise to 2 k decorated texts (each occurrence may be distinguished or not). It is important to note that two texts decorated differently are considered distinct.

Our initial problem was to count the set of all texts together with all occurrences considered. We will instead count the set all of decorated texts (considering all ways to distinguish occurrences). Indeed this appear to be a significantly easier task. Going back from the counts of decorated texts (where texts are overcounted) to the counts of texts is done by use of the inclusion-exclusion principle (see among others [Goulden and Jackson 1983, 2.2.28, 2.2.29], [Szpankowski 2001, 3.2], and [Flajolet and Sedgewick 2009, III.7.4] for details). This gives an elegant solution to the problem. This yields the generating function P (z, x) = π(a) 4 z 4 x 2 (where x counts the number of occurrences of the word u, and z the length of the text). The set of the four decorated texts for this example is accordingly

Q = {aa
(z, t) = w∈Q π(w)z |w| t #distinguished occurrences = π(a) 4 z 4 (t 2 + t + t + 1),
(where the variable t counts the distinguished occurrences and z the length of the decorated text). The relation between P (z, x) and Q(z, t) is simply Q(z, t) = P (z, 1 + t) since the substitution x → t + 1 parallels the fact that an occurrence may (or not) be distinguished (and then counted by the variable t). This relation can be used the other way around P (z, x) = Q(z, x -1).

This variable change t → x -1 is in fact quite general and is the essence of the inclusion-exclusion principle for generating functions. It readily extends to the case of a pattern with several words. Consider the text P = aaaaba and the pattern U = {u 1 = aaa, u 2 = aba}; the fully decorated text (signaling all occurrences) aa a ab a gives the generating function P (z, x 1 , x 2 ) = π(a) 5 π(b)z 6 x 2 1 x 2 that counts all occurrences. There are 2 3 decorated texts for the word P (each occurrence may be distinguished or not), forming the set

(z, t 1 , t 2 ) = π(a) 5 π(b)z 6 (1 + t 1 + t 1 + t 2 1 + t 2 + t 1 t 2 + t 1 t 2 + t 2 1 t 2 ) = P (z, t 1 + 1, t 2 + 1). 4.1.2.
Combinatorial description of decorated texts. To put into application the inclusionexclusion principle, a general construction of all decorated texts has to be derived. We consider an alphabet A and a set of patterns U = {u 1 , . . . , u r }, with u 1 ≺ • • • ≺ u r for the lexicographic order.

We define hereafter the fundamental notion of cluster.

Definition 4.3 (Cluster). A cluster c with respect to a pattern U is a decorated text such that -all positions are covered by at least a distinguished occurrence, -and, either there is only one distinguished occurrence, or any distinguished occurrence has an overlap with another distinguished occurrence.

Let us denote by C U the class of all clusters for a pattern U (or C when the context is clear).

Then the set of decorated texts T decomposes as sequences of either arbitrary letters of the alphabet A or clusters

T = (A + C) .
(5)

Figure 1 illustrates a particular decorated text that is an element of T. To apply directly the generating function methodology (see [START_REF] Flajolet | Analytic Combinatorics[END_REF]), it is essential that this decomposition is unambiguous: for a given decorated text, there is a unique way to decompose it along the language Equation (5). This property is actually true because the expansion of the right member of Equation ( 5) is composed of non-intersecting sets: the sets A and C are always distinct (as decorated texts), the concatenation is a non-commutative product, and finally clusters are well delimited since C ∩ C • C = ∅. As a remark Figure 1 illustrates the fact that two clusters may appear one immediately after the other. = 1,2,3). The alphabet is A = {a, b}. On this graphical representation, we write below the text the distinguished occurrences to stress out the fact that these occurrences overlap. Since Card(U ) = 1 the symbol signals distinguished occurrences of u (the label is here redundant). Now, let us assume that we know how to compute the generating function ξ(z, t) of the set of clusters C,

ξ(z, t) = w∈C π(w)z |w| t τ (w) , (6)
where τ (w) = (|w| 1 , . . . , |w| r ) and, by analogy with Equation (1) p. 4, the quantity |w| i denotes the number of distinguished occurrences of u i in w. It then follows from Equations ( 5) and ( 6) and general principles [START_REF] Flajolet | Analytic Combinatorics[END_REF]] that the generating function T (z, t) of all decorated texts is

T (z, t) = 1 + A(z) + ξ(z, t + A(z) + ξ(z, t) 2 + • • • = 1 1 -A(z) -ξ(z, t) . (7)
so that the sought generating function is

F U (z, x) = 1 1 -A(z) -ξ(z, x -1) . (8)
Therefore, we have reduced the problem of computing the generating function F U (z, t) to the one of computing the generating function of the set of clusters ξ(z, t). This is quite simple when the pattern U is reduced, and more difficult in the non-reduced case as will be shown in Section 5.

Clusters for one word patterns

Let us explore the case of counting occurrences of one word u in texts over the alphabet {a, b}. Considering clusters for this case appears first in [START_REF] Jacquet | Autocorrelation on words and its applications. Analysis of Suffix Trees by String Ruler Approach[END_REF]]. To build the set of clusters C of u = aaa in the present case, we can write 3

C = aa a • a + a a . (9)
Remark that {a, aa} = C u -ε where ε is the empty word. Note also that in this expression the symbol states which occurrences are distinguished in the clusters. The bivariate generating function ξ(z, t) of C is obtained from this expression by counting the distinguished occurrences, i.e., symbols , with the variable t. Accordingly, Equa-3 Strictly speaking, the decorated words a and a a obtained upon the words a and aa are not valid per se since the word aaa is neither a factor of a nor of aa. We use here a slight abuse of language, as we write decorated suffixes in the context of a cluster, so that decorations always correspond to valid occurrences. tion (9) translates to

ξ(z, t) = c∈C π(c)z |c| t # distinguished occurrences in c = tu(z) 1 -t(C(z) -1) = tπ(a) 3 z 3 1 -t(π(a)z + π(a) 2 z 2 ) ,
where t counts the number of distinguished occurrences and u(z) and C(z) respectively are the generating functions of the word u and of the autocorrelation set C of u.

Then making use of the symbolic exclusion-inclusion principle and of Equation ( 8) and denoting by |w| u the number of occurrences of u in w, we directly get

F (z, x) = w∈A π(w)z |w| x |w| u = 1 1 -A(z) -ξ(z, x -1)
,

where A(z) is the generating function of the alphabet A. Considering again the word u = aaa and the binary alphabet A = {a, b}, and posing π(a) = π(b) = 1 (to get the enumerative generating function), we have C(z) = 1 + z + z 2 and we obtain

F (z, x) = 1 1 -2z - (x -1)z 3 1 -(x -1)(z + z 2 )
.

Clusters for several words in the reduced case

When considering the reduced case for several words, the method described in the preceding section readily applies; the only difference is that we need matrix products to describe the clusters.

Considering the example U = {u 1 = aaab, u 2 = baaa}. A typical cluster is We see on this example that to extend a cluster to the right in the reduced case, we only need to consider the last distinguished occurrence (say u 1 ) in the cluster and append a word from the correlation sets C u1,u2 or C u1,u1 defined in Equation (2) p. 4 to obtain the next distinguished occurrence still overlapping the previous one (by definition of the correlation sets). Informally we make clusters grow by starting from a seed (a word of U which is distinguished) and concatenating words of correlations sets, adding each time a new distinguished occurrence. Let us consider the set of decorated words {u 1 , . . . , u r } corresponding to the pattern U = {u 1 , . . . , u r } and the matrix of decorated correlation sets Q = (Q i,j ) defined for 1 ≤ i, j ≤ r by

Q i,j = e∈Ci,j e =ε {Suff |e| (u j )} where C i,j = C ui,uj ; (10)
the notation Suff (u) denotes here the suffix of length of a word u and the notation Suff (u) is the corresponding decorated word; we use here again an abuse of notation (see the footnote 3 p.9). Then the matrix formula giving the set of all decorated clusters is

C = (u 1 , . . . , u r ) Q ε ε , (11)
where, for a matrix M, we write The translation to the generating function ξ(z, t) is extremely easy and mirrors the previous combinatorial expression. For the last example the generating function ξ(z, t 1 , t 2 ) of clusters (setting π(a) = π(b) = 1 for clarity, and applying the map

M = (I -M) -1 = I + M + M 2 + . . . .
→ t 1 , → t 2 , α → z with α ∈ A) verifies ξ(z, t 1 , t 2 ) = ( z 4 t1, z 4 t2 ) I - 0 z 3 t2 (z+z 2 +z 3 )t1 0 -1 1 1 .
Equation ( 8) applies then again, yielding the generating function of occurrences.

Short bibliographic note about applications of the Goulden-Jackson method

The inclusion-exclusion method of Goulden-Jackson is extremely powerful. Its applications go far beyond enumeration of texts. As a direct application of the basic definitions, [Goulden and Jackson 1983, 2.2.30] provide the number of derangements for permutations of size m. As another application, [Flajolet and Sedgewick 2009, III,7,4] count rises in permutations. Among the articles applying the inclusion-exclusion method and the use of clusters to count texts with forbidden patterns, we mention the following. [START_REF] Noonan | New Upper Bounds for the Connective Constants of Self-Avoidings Walks[END_REF]] evaluates connective constants of self-avoiding walks. [START_REF] Edlin | The Goulden-Jackson method for cyclic words[END_REF]] consider cyclic words with forbidden patterns and [START_REF] Zeilberger | The Umbral Transfer-Matrix Method. V. the Goulden-Jackson Cluster Method for Infinitely Many Mistakes[END_REF]] words with non-regular infinite forbidden patterns. Considering also words with forbidden patterns, [START_REF] Wen | The symbolic Goulden-Jackson method[END_REF]] uses symmetries of the set of words of the pattern to shrink the size of the matrix or linear system, while [START_REF] Kupin | Generalizations of the Goulden-Jackson method[END_REF] handle Markov sources. Finally, which will be the topic of the next Section, [START_REF] Noonan | The Goulden-Jackson Method: Extensions, Applications and Implementations[END_REF]] consider the general case of words counting. However, we point out that considering forbidden patterns corresponds to the case of reduced patterns; none of the articles mentioned here provide equivalents of the proofs and formulas that we give in the next Sections.

GENERAL CASE OF WORD COUNTING BY INCLUSION-EXCLUSION

We remark first that in the general non-reduced case, there is no known method of language decompositions similar to the approach of [Régnier and [START_REF] Égnier | On Pattern Frequency Occurrences in a Markovian Sequence[END_REF]], where a text is "scanned" with respect of all the occurrences of the pattern. Our goal is therefore to generalize the process of inclusion-exclusion to any finite set of words. The preceding section provides the main lines of the inclusion-exclusion method for reduced patterns as given in [START_REF] Goulden | Combinatorial Enumeration[END_REF]. This section extends this approach to the non-reduced case. See also [START_REF] Noonan | The Goulden-Jackson Method: Extensions, Applications and Implementations[END_REF]] that provides Maple scripts for this non-reduced case. Note also that if the language decomposition of Régnier and Szpankowski in the reduced case is a relatively easy combinatorial step, the combinatorial decomposition in the non-reduced 3. Occurrence 5 breaks the double staircase property; There is no reordering of the five occurrences that do not break the property. A skeleton (or reduced cluster) of the cluster will be built with occurrences 1 to 4. Occurrence 5 is a factor occurrence of occurrence 4 that will be add to the skeleton in a flip-flop manner that corresponds to the fact that this occurrence can be marked or left unmarked. case is harder; in both cases a trivial analytic manipulation follows and yields the sought generating function.

We introduce this section by mentioning an apparently trivial property verified in the reduced case. In general, this property is violated in the non-reduced case, but there are subsets of the distinguished occurrences that still verify it; the construction used in the non-reduced case will built upon one of these subsets that we will call skeleton of the cluster.

The double staircase property. Assume that we randomly number the occurrences of a cluster, and that each occurrence is represented by a thin domino, where the horizontal position of each domino is the position of the corresponding occurrence. Let now fall the dominoes from above, like in a Tetris game (Figure 2 (left)). In the case of reduced patterns, there is a simple and obvious property; there is a reordering of the occurrences such that letting fall the dominoes produces a double staircase shape (where the steps have unit height), one corresponding to the left side of the dominoes, and the other to the right side (Figure 2 (right)). Coming back to words, the progression from a given domino to the next one in this ordering corresponds to append a word belonging from the correlation set from the word whose occurrence corresponds to the given domino to the word whose occurrence corresponds to the next domino; this appears clearly in the example U = {u 1 = aaba, u 2 = baaa} of Section 4.3. This property can be violated in the case of non-reduced patterns, but as seen in the cluster of Figure ( 3), it is possible to build what will be called in the following the skeleton of the cluster that verifies the staircase property.

Combinatorial description of clusters in the general case

We exhibit a property of decorated texts which will prove useful for factorizing clusters.

Definition 5.1 (Reduced decorated text). A decorated text is said to be reduced if no distinguished occurrence is a factor of another distinguished one.

Counting occurrences for a finite set of words

39:13

Note that this property is automatically granted if the pattern U is reduced. We define a particular class of clusters called skeletons, which have this property.

Definition 5.2 (Skeleton). A skeleton is a cluster such that no distinguished occurrence is a factor of another distinguished occurrence.

We introduce also two dual operations, denoted by Skel and Flip which relate clusters and skeletons.

Definition 5.3 (Skeletization and flip operation). The two dual operations Skel and Flip are defined as:

-Let c be a cluster, the skeleton Skel(c) (denoted also c) of a decorated text c is obtained from c by undistinguishing (moving the status of an occurrence from "distinguished" to "not distinguished") the factor occurrences in c. -Let c be a skeleton, the Flip operation associates to c the set Flip(c) of all clusters c such that Skel(c) = c.

We have the following lemma for clusters.

LEMMA 5.4. The skeleton Skel(c) of a cluster c is uniquely defined. It is a cluster and the distinguished occurrences in Skel(c) can be increasingly ordered with respect to their end positions such that each occurrence overlap the following one, when it exists. This ordering is unique.

PROOF. We omit the proof which is very simple. This example illustrates that two different clusters with same support (here abababa) can have different skeletons.

Now, the general strategy to describe clusters is to build reduced clusters, and along this process to identify all factor occurrences (mirroring the Flip operation).

We therefore introduce a notation aimed at representing factor occurrences produced by the Flip operation for a skeleton.

where end positions of occurrences belonging to the skeleton are signaled by black filled circles, and factor occurrences are signaled by white filled circles. This notation gives us a way to represent all the clusters sharing the same skeleton. As a matter of facts, there is no conceptual difference between bicolored decorated words and the set of decorated words with the same skeleton obtained by examining all ways of distinguishing factor occurrences. For instance the fully bicolored decorated cluster of ( 12) is strictly equivalent to the set containing 2 5 = 32 (there are five factor occurrences) differently decorated clusters.

Remark 5.7 (Integrity rule for Flips of skeletons). In Definition 5.6 we flip only occurrences which are factors of the distinguished occurrences of the skeleton. So, by Definition 5.6, for two different skeletons c 1 and c 2 , we have

Flip(c 1 ) ∩ Flip(c 2 ) = ∅.
We provide an example for the last remark by considering the pattern U = {u 1 = aaa, u 2 = aaaaaaa}, a skeleton c 1 , and the corresponding Flip(c 1 ). In order to improve the readability here we decompose clusters according to their skeletons.

c 1 = aa aaaaaa a aaa aaaaaaa =⇒ Flip(c 1 ) = aa a • a a a a a a. (13)
We remark here that the fourth position has no label signaling a factor occurrence aaa; indeeds considering a factor occurrence aaa at this position would break the integrity rule and correspond to a skeleton c 2 different of c 1 , namely, (

) 14
Right extensions. The skeletons will basically be built on a matrix construction similar to the one of the reduced case (see Equation ( 10)). Next, in a second step, the factor occurrences are added to the skeleton. As shown in the following example, the classical definition of correlations of words is not compatible with the definition of skeletons.

Considering the words u = a 3 and v = a 7 , following the definition of correlation (Equation (2) p. 4), we have C a 3 ,a 7 = {a 4 , a 5 , a 6 }. How however can we go from an occurrence of a 3 to an occurrence of a 7 in a skeleton? We have the three cases

(i) aaa| |aaaa (ii) aaa| |aaaaa (iii) aaa| |aaaaaa
where the black rules underline the positions of the last occurrence of a 7 . As seen in case (i), it is not possible to progress in a skeleton from an occurrence of a 3 to an occurrence a 7 by the word a 4 ; in this case the first occurrence of a 3 is a factor of the underlined occurrence of a 7 , which is contradictory to the definition of skeletons. On the contrary, cases (ii) and (iii) correspond to valid extensions.

In order to properly generate the skeletons we therefore introduce the notion of right extension of a pair of words (u, v). This notion is a generalization of the correlation set of two words u and v but differs in that:

(i) overlapping is not allowed to start at the beginning of u.

(ii) extension has to add some letters to the right of u.

These two conditions ensure that, while scanning a text from left to right, going from one distinguished occurrence to another in a skeleton, both ending and beginning positions are changing, hence preventing from considering factor occurrences.

More formally we have Definition 5.8 (Right extension set). The right extension set of a pair of words (u, v) is

E u,v = { e | there exists e ∈ A + such that ue = e v with 0 < |e| < |v|}.
Note that, when u and v have no factor relation, the right extension set E u,v is the correlation set of u to v. Moreover, when u = v, the set E u,v is the strict autocorrelation set of u (the empty word does not belong to E u,u ). We can also define a decorated variant.

Definition 5.9 (Bicolored decorated right extension set). Let u and v be two words, and u and v be defined by Convention 4.2 p. 7. The bicolored decorated right extension of the pair of words (u, v) is

E u,v = e∈Eu,v Suff |e| (Flip(v)),
where for a set V of bicolored decorated words, Suff (V) is the set of (bicolored decorated) suffixes of length from V.

We use again here the abuse of notation mentioned in footnote 3 p. 9. We apply the last definition in the following example.

Example 5.10. We consider the pattern U = {u 1 , u 2 } = {aa, aaa} together with two particular clusters c 1 and c 2 as an illustration. We have As for correlation matrices, we define right extension matrices with respect to a pattern U = {u 1 , . . . , u r } with indices of words dictated by the lexicographical order

E = E ui,uj 1≤i,j≤r .
We define also accordingly the decorated variant E of the right extension matrix E of dimension r × r .

Example 5.11. We give some examples of patterns and their right extension matrices (non-decorated and decorated). (2) For U = {a 3 , a 7 }, we have5

u 1 = aa a, u 2 = aaaaaa a so that Flip(u 1 ) = {aa a}, Flip(u 2 ) = {aa a a a a a},
and E = a + aa a 5 + a6 a + aa a + a 2 + a 3 + a4 + a 5 + a 6 , so that (3) As a slightly more complicated example the pattern U = {aa, ab, ba, baaab} gives

E =    { a, a
u 1 = a a, u 2 = a b, u 3 = b a, u 4 = baaa b, Flip(u 1 ) = {a a}, Flip(u 2 ) = {a b}, Flip(u 3 ) = {b a}, Flip(u 4 ) = {b a a a b}, E =    a b ∅ ∅ ∅ ∅ a aaab a b ∅ ∅ ∅ ∅ a aaab    and E =           { a} { b} ∅ ∅ ∅ ∅ { a} { a a a b} { a} { b} ∅ ∅ ∅ ∅ { a} { a a a b}          
.

We introduce here the notion of (k + 1)-skeleton.

Definition 5.12 ((k + 1)-skeleton). We denote by (k + 1)-skeleton a skeleton that is composed of k + 1 occurrences and by (k + 1)-cluster a cluster whose skeleton is a (k + 1)-skeleton.

We state now the link between clusters and bicolored decorated right extensions. PROPOSITION 5.13. The set C of all clusters verifies

C = (Flip(u 1 ), . . . , Flip(u r )) • E •    ε . . . ε    . ( 15
)
PROOF. We recall that,

(1) given any cluster c, undistinguishing the factor occurrences leads to a skeleton c such that c ∈ Flip(c), (2) and, given two different 6 skeletons c and c , we have Flip(c) ∩ Flip(c ) = ∅.

These two properties imply that taking the Flip of all possible skeletons generates all possible clusters in a way where each cluster is generated exactly once.

Given a pattern U = {u 1 , . . . , u r } and any (k+1)-skeleton c, the definition of skeletons yields that there are a unique sequence (i 1 , . . . , i k+1 ) and a unique decomposition

c =(u • w 1 • w 2 • . . . • w k , (D d ) 1≤d≤|c| ), (16)
where

       u = u i1 ∈ U and, for 1 ≤ j ≤ k, w i ∈ E ui j ,ui j+1 , D |u| = i 1 , D |u•w1• ... •we| = i j+1 if w e = E ui j ,ui j+1 , D d = ∅ if not defined previously.
In this last equation, the sequence (D d ) records the distinguished positions of the skeleton c and the corresponding indices.

For 1 ≤ j ≤ r we denote u j (resp. E i,j ) the monocolor words where there is only a label u j upon the last position (factor positions have been undistinguished). We also denote E = (E i,j ). Considering the set C k+1 of (k + 1)-skeletons, Equation ( 16) yields by considering all possible (k + 1)-skeletons

C k+1 = (u 1 , . . . , u r ) • E k •    ε . . . ε    , which implies that C = (u 1 , . . . , u r ) • E •    ε . . . ε    , ( 17
)
where C is the set of all skeletons. Now we need to lift up Equation ( 17) to clusters, i.e., we consider factor occurrences. This is done thanks to the Flip operation. Indeed, applying the Flip operator on the words u i and using Definition 5.9 to compute the entries E i,j of the matrix E do not modify the skeleton. Moreover no factor occurrence can be missed in the resulting bicolored words. This implies that the set of clusters C = Flip(C) verifies Equation (15).

Generating functions of clusters

We need now to compute the multivariate generating functions U i (z, t) of the bicolored words Flip(u i ) and E i,j (z, t) of the bicolored right extensions E i,j to get the generating function ξ(z, t). The following lemma gives the correspondence between bicolored decorated texts and their generating functions. LEMMA 5.14. We consider a pattern U = {u 1 , . . . , u r } and a fully bicolored decorated cluster c = (c, D, F) with skeleton c and length |c| = , such that c = α 1 α 2 . . . α with α i ∈ A, and where D = (D i ) 1≤i≤ (resp. F = (F i ) 1≤i≤ ) is the occurrence index of the distinguished occurrences defining the skeleton (resp. occurrence index of the factor occurrences), the positions being relative to the beginning of the cluster as in Equation ( 16). The generating function c(z, t) of the set of clusters Flip(c) built upon the skeleton c is computed thanks to the bicolored representation c and verifies

c(z, t) = i=1   π(α i )z ×   j∈Di t j   × s∈Fi (1 + t s )   , (18)
where the variable t i counts the occurrences of the word u i .

PROOF. Indeed, distinguished occurrences which define the skeleton are signaled thanks to D whereas, once the skeleton is fixed, factor occurrences can be distinguished or not, giving for each i, if s ∈ F i , a term7 (1 + t s ).

Using the notations defined in the proof of Proposition 5.13, to compute the sequence (U i (z, t)) 1≤i≤r and the matrix E(z, t) = (E i,j (z, t)) 1≤i,j≤r , we apply the last lemma and Equation ( 18) successively to the clusters Flip(u i ) and Flip(u i • E i,j ); these last expressions give access to the multivariate generating functions of the bicolored sets E i,j deriving from the sets E i,j ; (it is not possible to apply directly the lemma on E i,j since it is neither a cluster nor a skeleton). We then have

E i,j (z, t) = e(z, t) U i (z, t)
, where e(z, t) is the generating function of Flip(u i • E i,j ).

Example 5.15. We develop further the Example 5.11 from p. 15 by taking π(a) = π(b) = 1.

(1) For (u 1 , u 2 ) = (ab, aba), we have

Flip(u 1 ) = {a b} → U 1 (z, t 1 , t 2 ) = z 2 t 1 Flip(u 2 ) = {a b a} → U 2 (z, t 1 , t 2 ) = z 3 t 2 (1 + t 1 ) E =   ∅ ∅ a b a   → E(z, t 1 , t 2 ) = 0 0 zt 2 z 2 t 2 (1 + t 1 )
.

(2) For (u 1 , u 2 ) = (a 3 , a 7 ), from Example 5.11 again, we have

Flip(u 1 ) → U 1 (z, t 1 , t 2 ) = z 3 t 1 , Flip(u 2 ) → U 2 (z, t 1 , t 2 ) = z 7 t 2 (1 + t 1 ) 5 , E(z, t 1 , t 2 ) = t1(z+z 2 ) t2(1+t1) 5 (z 5 +z 6 ) t1(z+z 2 ) t2((1+t1)z+(1+t1) 2 z 2 +(1+t1) 3 z 3 +(1+t1) 4 z 4 +(1+t1) 5 (z 5 +z 6 )) .
(3) Finally, for (u 1 , u 2 , u 3 , u 4 ) = (aa, ab, ba, baaab), the last pattern of Example 5.11, we get

E(z, t 1 , t 2 , t 3 , t 4 ) =    t 1 z t 2 z 0 0 0 0 t 3 z t 4 z 4 (1 + t 1 ) 2 (1 + t 2 )(1 + t 3 ) t 1 z t 2 z 0 0 0 0 t 3 z t 4 z 4 (1 + t 1 ) 2 (1 + t 2 )(1 + t 3 )    .
With these notations, we get to the following proposition.

PROPOSITION 5.16. The generating function ξ(z, t) of clusters built from the set U = {u 1 , . . . , u r } is given by

ξ(z, t) = (U 1 (z, t), . . . , U r (z, t)) • I -E(z, t) -1 • 1 . . . 1 , (19)
where U i (z, t) is the generating function for the (bicolored) decorated word Flip(u i ), and E(z, t) is the matrix of generating functions for the (bicolored) right extension sets. PROOF. This expression follows from general principles on generating functions applied to the combinatorial description of clusters from (15).

Particular cases

We examine for special cases of interest the generating functions of clusters.

One word. For U = {u}, we get

ξ(z, t) = tπ(u)z |u| 1 -t C(z) = tπ(u)z |u| 1 -t(C(z) -1) , (20)
where C(z) and C(z) respectively are the autocorrelation polynomial and the strict autocorrelation polynomial (empty word ε omitted) of u.

Two words. For a general set of two words {u 1 , u 2 }, we can compute explicitly ξ(z, t 1 , t 2 ) by the Cramer's rule,

ξ(z, t 1 , t 2 ) = U 1 + U 2 -U 1 E 2,2 -E 1,2 + U 2 E 1,1 -E 2,1 1 -E 2,2 -E 1,1 + E 1,1 E 2,2 -E 2,1 E 1,2 , (21)
where U 1 , U 2 , (E i,j ) 1≤i,j≤j respectively are the generating functions in (z, t 1 , t 2 ) obtained by application of Lemma 5.14 for (bicolored) decorated words u 1 , u 2 and the (bicolored) decorated matrix of right extensions (E i,j ) 1≤i,j≤j .

Example 5.17. Let us consider again the pattern U = {a 3 , a 7 } from Example 5.15(2) p. 18 and π(a) = π(b) = 1; we therefore have π(w) = 1 for all words w (the unweighted "enumerative" model where each word has weight 1). Evaluating Equation ( 21) with these weights, the generating function of clusters ξ(z, t 1 , t 2 ) verifies

ξ(z, t 1 , t 2 ) = z 3 t 2 (1+t 1 ) 4 z 4 -t 2 t 1 (1+t 1 )z 3 -t 2 t 1 (1+t 1 ) 2 z 2 -t 2 t 1 (1+t 1 )z+t 1 1-z 3 t 2 (1+t 1 ) (1+t 1 ) 3 z 3 + t 1 3 +3 t 1 2 +2 t 1 +1 z 2 + t 1 3 +2 t 1 2 +t 1 +1 z+1-t 1 2 -2 t 1 -(t 2 t 1 +t 2 +t 1 )(z 2 +z)
Reduced set. When the set U is reduced, that is, no word of U is factor of another, we do not need to consider the Flip operation as clusters are always reduced. The distinguished occurrences are implicitly specified. So that the generating function can be stated with the help of the generating function of the correlation set ξ(z, t) = ∆(t)(π(u 1 )z |u1| , . . . , π(u r )z |ur| ) I -∆(t) C(z)

-1 1 . . . 1 ,
where ∆(t) is a square matrix with diagonal t = (t 1 , . . . , t r ) and C(z) is the matrix of generating functions for strict (i.e., empty word omitted) correlation sets. This is another formulation of the result of Goulden and Jackson [START_REF] Goulden | Combinatorial Enumeration[END_REF].

Generating function of texts. As mentioned in Section 4.1.2, a text is decomposed as a sequence of letters from A (with generating function A(z)) and clusters from C U (with generating function ξ(z, t) from Equation ( 6)). The multivariate generating function F (z, x) given by Equation ( 1) is derived by substituting t i → x i -1 for i ∈ {1, . . . , r}. To summarize, we have the following theorem. THEOREM 5.18. Let u = (u 1 , . . . , u r ) be a finite vector of words in A and E the associated right extension matrix. The multivariate generating function F (z, x) counting texts whose length is counted by the variable z and where the occurrences of u i are counted by the vector of formal variables x = (x 1 , . . . , x r ) is

F (z, x) = 1 1 -A(z) -ξ(z, x -1) , ( 22
)
where A(z) = α∈A π(α)z is the generating function of the alphabet and ξ(z, t) is defined in Equation ( 19). PROOF. The proof relies on two main points. On one hand, the generating function ξ(z, t) counts all the clusters (see Proposition 5.16). On the other hand, the inclusionexclusion principle yields the final result by the substitutions t i → x i -1.

The application of the standard techniques of analytic combinatorics (see [START_REF] Flajolet | Analytic Combinatorics[END_REF]) to the multivariate generating function F (z, x) gives access to statistics such as mean, variance, covariance. (See Section 6).

An algorithmic construction based on the Aho-Corasick automaton

We consider a pattern U = {u 1 , . . . , u r }. We recall that we assumed previously that u i ≺ u i+1 with respect to the lexicographical order for i from 1 to r -1; therefore k is the index of the word u k in the pattern considered as a list.

We want an efficient way to compute the generating function ξ(z, t) of the clusters of U. In particular, we have to compute the r-tuple (U 1 (z, t), . . . , U r (z, t)) and the r × r elements E i,j (z, t) of the right extension matrix from Proposition 5.16.

As mentioned in Section 3 the Aho-Corasick algorithm upon which we work first constructs a trie T U on the words of the pattern U. We denote Ω the Aho-Corasick automaton constructed upon the trie T U .

We label and name in the following any state of the automaton Ω by the word that leads to this state when starting from the root ε and progressing in the trie T U by successively reading the letters of w; see an example of such labeling in Figure 4. Therefore the term w will refer in a parallel manner to a word w and to the corresponding state in the automaton Ω.

We use the following definitions.

-We denote Pref(w) the set of prefixes of a word w.

-We denote S w the set of indices of words from U that are suffixes of w; this is considered in a wide sense: we accept the word w as a suffix of itself, although it is not a proper suffix. -We denote λ(w) the suffix link starting from state w, where λ(w) = Border(w), and the function Border(w) is defined as in Section 3 by Border(w) = the longest proper suffix of w in Pref(U) if it is defined, or ε otherwise.

As an example, considering Figure 4, there is a suffix link from the state (baaab) to the state (ab). -We denote σ(w) the length of the suffix chain8 starting at a state w.

We proceed in the following by steps.

-Step (i). We construct the Aho-Corasick automaton Ω recognizing the pattern U.

-Step (ii). We associate to each state w of the automaton the set S w containing the indices of words u from U that are recognized at state w (so that these words are also suffixes of w); beware that along the cases, these words may be or may be not factor occurrences. -Step (iii). By using the suffix links and the information stored in Step (ii), we compute all the needed generating functions.

We detail now each step of the algorithmic computation.

Step (i). This step is a classical construction for text analysis (see for instance [START_REF] Braffort | Algorithms on Strings[END_REF][START_REF] Crochemore | Jewels of Stringology[END_REF]). Note that the construction provides the suffix links for the pattern.

Step (ii). We add now more information to the automaton Ω.

The set S w can be obtained while building the automaton, since when a state w is terminal, we know which of the words of the pattern U is accepted. This is a classical modification of the basic Aho-Corasick algorithm (see [START_REF] Braffort | Algorithms on Strings[END_REF]] for instance). The complexity of this modification is O(r × u∈U |u|) if we naively manage subsets S w of {1, . . . , r} for each state w of the automaton.

Step (iii). Using the suffix links, we get an alternative way to express the right extension set from a word u i to a word u j (see Definition 5.8); we have

E i,j = e | h • e = u j and h ∈ {λ c (u i ), 1 ≤ c < σ(u i )} . ( 23
)
Note that h • e = u j ⇒ h ∈ Pref(u j ); this leads to consider the sets H i,j such that

H i,j = h = ε h ∈ Pref(u j ) ∩ λ c (u i ) | 1 ≤ c < σ(u i ) . (24)
Each word h in this equation is simultaneously a prefix of u j and a suffix of u i (by the definition of the suffix link function λ(w)); moreover the set H i,j is in bijection with the right extension set E i,j .

We now define, for states w ∈ Pref(u j ) ∪ {ε} such that there exists v ∈ A * that verifies w • v = u j , the auxiliary functions Φ (w) j (z, t) = v(z, t), where v is the decorated text associated to the word v. We have immediately

U j (z, t) = Φ (ε) j (z, t), and E i,j (z, t) = h∈Hi,j Φ (h) j (z, t). (25)
The generating functions Φ (w) j (z, t) can be defined recursively,

Φ (w) j (z, t) = t j if w = u j Φ (w•α) j (z, t) × π(α)z s∈Sw•α\{j} (1 + t s ) if w•α ∈ Pref(u j ) (α ∈ A). (26)
Thus all the functions Φ (w) j (z, t) for j ∈ {1, . . . , r} and w ∈ Pref(U) are computed from the leaves to the root by a postorder traversal of the trie T U ;

Example 5.19. We consider the example given in Figure 4 where we have U = {aa, aaa, ab, ba, baaab}. Following the recurrence defined in Equation ( 26), we have, recalling that 2 is the index of the word aaa in the pattern U, and since H 2,2 = {aa, a},

Φ (aaa) 2 (z, t) = t2, Φ (aa) 2 (z, t) = t2π(a)z(1+t1), Φ (a) 2 (z, t) = t2π 2 (a)z 2 (1+t1) 2 , Φ (ε) 2 (z, t) = t2π 3 (a)z 3 (1+t1) 2 U2(z, t) = t2π 3 (a)z 3 (1+t1) 2 , E2,2(z, t) = t2 π(a)z(1+t1)+π 2 (a)z 2 (1+t1) 2 .
Similarly, starting from Φ (baaab) 5

= t 5 , we obtain by using the recurrence We denote by S the size of the longest suffix chain of a word u ∈ U. The number of the sets H i,j defined in Equation ( 23) is typically less than r × r. To compute them, we can use sets P w associated to each state w of T U that record the indices of the words u ∈ U such that w ∈ Pref(u); for instance, considering Figure 4, we have P a = {1, 2, 3}. The computation of the sets P w can be done by a postorder traversal of the tree in time O(r × |Ω|) = O(r × u∈U |u|). Using these sets and the suffix links, all the sets H i,j can be computed in a largely overestimated overall cost r × r × S. It is then straightforward to compute E i,j (z, t) by Equation ( 25).

E 3,5 (z, t) = Φ (a) 5 (z, t) = π(a) 3 π(b)z 4 (1 + t 1 ) 2 (1 + t 2 )(1 + t 3 )(1 + t 4 )t 5 ,
The auxiliary functions Φ (w) j (z, t) for 1 ≤ j ≤ r and w a prefix of u j are computed, considering here operations on polynomials (mostly multiplications), in total time O(r × u∈U |u|).

As a conclusion of this section, assuming that the size of the alphabet is a constant, the "time complexity", considering elementary operations on automata and operations on polynomials in z and t, is O(r × u∈U |u| + S × r 2 ) in order to compute the sequence (U i (z, t)) r i=1 ) and the matrix E(z, t). We remark that the coefficients of the matrix are polynomials whose degrees (in any variable) are bounded by max u∈U |u| -1. Also we note that the r × r matrix E(z, t) is smaller and more compact than the linear system obtained by applying the Chomsky-Sch ützenberger algorithm on the Aho-Corasick automaton of Section 3 which has size O(( u∈U |u|) 2 ) since there are O u∈U |u| states in the automaton. Inverting the corresponding sparse matrix in z would imply handling possibly large coefficients that are multivariate polynomials over the counting variables x 1 , . . . , x r ; see Section 3 for an example.

MOMENTS

Bender and Kochman [START_REF] Bender | The distribution of subword counts is usually normal[END_REF] consider generalized words where a generalized word W is a set of words of same length. Considering two generalized words W 1 and W 2 , they compute the dominant term of the asymptotic covariance of the number of occurrences of W 1 and W 2 in random texts of size n as n tends to infinity. We consider as previously patterns U that are any finite sets of finite words, disregarding their lengths. We compute here in random texts of size n the dominant asymptotic term of:

-the expectation of the number of occurrences of a pattern U; -the variance of this number; -the covariance of the number of occurrences of a pattern U and of a pattern V.

Bender and Kochman also state limit laws in several cases for sets of generalized words, their proofs relying importantly on previous works of Bender et al in a series of articles [START_REF] Bender | Central and local limit theorems applied to asymptotic enumeration[END_REF]Bender and Richmond 1983;Bender et al. 1983]. Although it is very likely that these results still hold in the case of more general patterns, the corresponding study is beyond the scope of the present article.

Number of occurrences for a non-reduced pattern

We consider here a Bernoulli model and extend the probability measure π defined for words to sets of words in the following way π(U) = u∈U π(u).

We provide for the case of a pattern U = {u 1 , . . . , u k } expressions for the expected value and variance of the random variable X n counting the number of occurrences of U in a text of size n. Section 5 gives a mean to obtain the generating function for clusters ξ(z, t 1 , . . . , t k ) where the occurrences of the word u i ∈ U are counted by the variable t i . The cluster generating function Υ(z, t) related to occurrences of U is then defined9 by Υ(z, t) = ξ(z, t, . . . , t).

(

) 27
Finally the generating function of occurrences is by Equation ( 22)

F (z, x) = 1 1 -z -Υ(z, x -1)
, and, since F (z, 1) = 1/(1 -z), we have Υ(z, 0) = 0. Setting Υ t (z) = ∂ ∂t Υ(z, t) t=0 and Υ tt (z) = ∂ 2 ∂t 2 Υ(z, t) t=0 and using basic algebra, we have n≥0

E[X n ]z n = ∂ ∂x F (z, x) x=1 = Υ t (z) (1 -z) 2 n≥0 E[X 2 n ]z n = ∂ 2 ∂x 2 F (z, x) x=1 + ∂ ∂x F (z, x) x=1 = 2Υ t (z) 2 (1 -z) 3 + Υ tt (z) + Υ t (z) (1 -z) 2 .
It is easy to see that Υ t (z) = u∈U π(u)z |u| (the clusters with one and only one marked occurrence). The expression for Υ tt (z) takes into account that some words of U are factor of other ones After some algebra, we get the following result. We point out that the last sum is a correcting factor and is non zero only if the set is non reduced. If the set contains only one word u, recalling that E u,u is the strict autocorrelation set of u, we obtain (as we should!) the classical result for the variance (see by instance Theorem 7.14 in [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF]] book)

Υ tt (z) = 2
lim n→∞ 1 n
Var(X n ) = π(u) + 2π(u)π(E u,u ) -(2|u| -1)π(u) 2 .

(28)

Covariance of two patterns

We consider again a Bernoulli model and two patterns U and V. We use again the notion of right extensions sets introduced in this article. The following theorem extends the case handled by [START_REF] Bender | The distribution of subword counts is usually normal[END_REF] where U and V are generalized words. THEOREM 6.2. Let U = {u 1 , . . . , u k } and V = {v 1 , . . . , v j } be two patterns. The covariance of the variables X n and Y n counting respectively the number of occurrences of

We have also easy access to the covariance since n≥0 E(X n Y n )z n = ∂ 2 ∂x∂y F (z, x, y) x=y=1 = 2 (Υ1(z)+Υ3(z))(Υ2(z)+Υ3(z))

(1-z) 3 + Υ12(z)+Υ13(z)+Υ23(z)+Υ33(z)+Υ3(z)

(1-z) 2

= 2 Υ1(z)Υ2(z)

(1-z) 3 + Υ12(z) (1-z) 2 + 2 Υ3(z) 2 (1-z) 3 + Υ33(z)+Υ3(z)

(1-z) 2

+ 2 Υ3(z)(Υ1(z)+Υ2(z))

(1-z) 3 + Υ13(z)+Υ23(z)

(1-z) 2

.

A Taylor expansion at z = 1 gives for i = 1, 2, 3 (with f (z) = ∂ ∂z f (z)) Summarizing and after some computations, we get to Equation (29).

Υ i (z) = Υ i (1) -(1 -z)Υ i (1) + o(1 -z).
Example: variance-covariance matrix of a 3 and a 7 . We apply the results of this section to U = a 3 and V = a 7 in a Bernoulli model with p = π(a).

Let X n and Y n count the number of occurrences of a 3 and a 7 in a random text of size n. We denote

B 11 = lim n→∞ 1 n Var(X n ), B 22 = lim n→∞ 1 n Var(Y n ), B 12 = B 21 = lim n→∞ 1 n Cov(X n , Y n ).
We get by Equation ( 29),

          
π(a 3 )π(E a 3 ,a 7 ) = p 3 (p 5 + p 6 ), π(a 7 )π(E a 7 ,a 3 ) = p 7 (p + p 2 ), a 7 a 3 π(a 7 ) = 5p 7 , a 3 a 7 π(a 3 ) = 0, ( a 7 + a 3 -1)π(a 7 )π(a 3 ) = 9p 10 =⇒ B 12 = 5p 7 + 2p 8 + 2p 9 -9p 10 .

  abb,(4)

A

  abb, abaa aba abb, abaaabaabb, aba a aba abb.

  4.1.1. Toy examples. Let us consider the simple case of a text P = aaaa and a pattern with a single word U = {u = aaa}. We get the fully decorated text by considering all occurrences of aaa in aaaa aa a a.

  generating function of the decorated texts for aaaa Q

  generating function of decorated texts is Q

Fig. 1 .

 1 Fig.1. We consider the text w = baaaaaaaaaaabaaaabaaaaab, the pattern U = {aaa}, and a particular decorated text with three clusters c i (i = 1, 2, 3). The alphabet is A = {a, b}. On this graphical representation, we write below the text the distinguished occurrences to stress out the fact that these occurrences overlap. Since Card(U ) = 1 the symbol signals distinguished occurrences of u (the label is here redundant).

For

  instance with U = {u 1 = aaab, u 2 = baaa}, the set of clusters C is given by

Fig. 2 .

 2 Fig. 2. The nice property of double staircase shape for reduced patterns. (Left) Random ordering of the occurrences falling like dominoes in a Tetris game. (Right) Double staircase reordering.5

  Example 5.5. Let us consider the pattern U = {u 1 = ab, u 2 = ba, u 3 = baba} and the clusters c

  Definition 5.6 (Bicolored decorated cluster). Let c = (c, D) be a skeleton with respect to a pattern U = {u 1 , . . . , u r }. We denote by O the occurrence index of U in c, and, as previously, by D ⊆ O the set of indices of distinguished occurrences in c. The fully bicolored decorated word c associated to c is a pair c = (c, F) where F ⊂ O \ D is the set of indices of the distinguished factor occurrences within the occurrences indexed by D.In the graphical representation, we will denote by a different mark (white filled circles) factor occurrences of distinguished occurrences. Hence for instance, considering the skeleton c for U = {ab, ba, baba} Flip(c) is the set of clusters having c as skeleton and can be identified to the following bicolored decorated word c = Flip(c)

  Suff |a| (Flip(u 2 )) = { a}, Suff |aa| (Flip(u 2 )) = { a a}, and E a 3 ,a 3 = {

( 1 )

 1 For U = {ab, aba}, we have E =

Fig. 4 .

 4 Fig. 4. Illustration of the Aho-Corasick construction, considering the pattern U = {aa, aaa, ab, ba, baaab} of Example 5.15(3). Nodes are labeled with words from Pref(U ). Indices are to be understood (following the convention used in all this article) as indices of words in U ordered in the lexicographical order. Double circled terminal nodes correspond to states where an occurrence of U is found. However, for our particular purpose, we need a more precise information and associate to each node w the set Sw which is the set of labels of words from U accepted at state w. These sets are represented next to each state. Suffix links are represented with dashed lines.

  which follows from the fact that the set H 3,5 = {b} has a single element. Starting now from Φ (ba) 4 (z, t) = t 4 , we get E 3,4 (z, t) = Φ (b) 4 (z, t) = π(a)zt 4 . Complexity. The classical construction of the Aho-Corasick automaton yields a time complexity O( u∈U |u|). However we need more information on terminal nodes (namely the set of indices of words accepted), and this gives a complexity O(r × u∈U |u|) since we manipulate subsets of {1, . . . , r}.

  |u| v z |u| + 2 u,v∈U e∈Eu,v π(ue)z |ue| .

  PROPOSITION 6.1. Let U = {u 1 , . . . , u k } be a pattern. The expected value and the variance of the variable X n counting the number of occurrences of U in a random text of size n satisfyE[X n ] = u∈U π(u)(n -|u| + 1|u| v + o(1).

  Hence we getE(X n Y n ) = (n + 1)(n + 2) Υ 1 (1) + Υ 3 (1) Υ 2 (1) + Υ 3 (1) + (n + 1) Υ 1 (1) + Υ 3 (1) Υ 2 (1) + Υ 3 (1) + Υ 1 (1) + Υ 3 (1) Υ 2 (1) + Υ 3 (1) + Υ 12 (1) + Υ 13 (1) + Υ 23 (1) + Υ 33 (1) + Υ 3 (1) + o(n).Now we can interpret each of the coefficients: we have for instanceΥ 1 (1) + Υ 3 (1|u| v + π(u)π(E u,v ) + π(v)|v| u + π(v)π(E v,u ) .

ACM Transactions on Algorithms, Vol. 9, No. 4, Article 39, Publication date: March 2010.

Algorithms implemented in the package regexpcount of algolib, Algorithms Project, INRIA ACM Transactions on Algorithms, Vol. 9, No. 4, Article 39, Publication date: March

An application of the principle "it is easier to forget something than to remember everything". ACM Transactions on Algorithms, Vol. 9, No. 4, Article

39, Publication date: March 2010.

For instance {a b a} is equivalent to {ab a, a b a}.

See the Remark 5.7 p. 14 and the example that follows the remark.

See (13) and (14) p. 14 illustrating the integrity rule for Flips of skeletons (Remark 5.7).ACM Transactions on Algorithms, Vol. 9, No. 4, Article 39, Publication date: March 2010.

We remark that with this methodology it would be easy to get the generating functions of clusters counting separately occurrences forming the skeleton and factor occurrences with two sets of formal variables t and s for instance.ACM Transactions on Algorithms, Vol. 9, No. 4, Article 39, Publication date: March 2010.

The suffix chain of a word u is the sequence (u 1 = u, u 2 = Border(u 1 ), u 3 = Border(u 2 ), . . . , us = Border(u s-1 ) = ε). The length of this chain is σ(u) = s -1.ACM Transactions on Algorithms, Vol.

9, No. 4, Article 39, Publication date: March 2010.

Doing the substitutions t i → t, we do not count the number of positions where there is a match, but add up the number of matches with words of U at each matching position.ACM Transactions on Algorithms, Vol. 9, No. 4, Article 39, Publication date: March 2010.

Acknowledgments. The authors thank Jérémie Bourdon, Philippe Dumas, and Julien Fayolle for fruitful discussions and for providing important feedback.

F. Bassino acknowledges financial support from the French ANR (MAGNUM) under grant ANR-BLAN-2010-0204.

U and V in a random text of size n verifies

PROOF. We consider here the weighted case where A(z) = z. Let U and V be two sets of words. We first decompose as a direct sum the set U ∪ V:

In order to ease the notations, we index the variables in the generating function ξ(z, t) by words, i.e., the variable t u corresponds to the word u. Then we consider the generating function of clusters for the three disjoint sets U = U \ V, V = V \ U, and W = U ∩ V, with t = (t u ) u∈U ∪V and the respective variables t 1 , t 2 and t 3 such that

that is we simply substitute variables for words appearing in each of the three sets with t 1 , t 2 and t 3 . Let F (z, x, y) be the corresponding generating function counting occurrences. We have by Equation ( 22) and since occurrences in U ∩ V are marked two times (one x for belonging to U and one y for belonging to V)

By construction, since F (z, 1, 1) = 1 1-z , one has Υ(z, 0, 0, 0) = 0. To simplify the notations, we set

By general mechanisms [START_REF] Flajolet | Analytic Combinatorics[END_REF] we get from Equation (31

Computing the variance-covariance matrix B (a 3 ,a 7 ) = (B ij ) for i, j ∈ {1, 2}, and the corresponding determinant ∆, we get

p 7 (5+2p+2p 2 -9p 3 ) p 7 +2p 7 (p+p 2 +p 3 +p 4 +p 5 +p 6 )-13p 14 , ∆ = |B (a 3 ,a 7 ) | = p 10 + 4p 11 + 8p 12 + 5p 13 -25p 14 -20p 15 -24p 16 + 67p 17 -16p 20 .

Let us remark that ∆ is zero if p = 0 or p = 1 and nowhere else. This corresponds to a degeneracy of the system that can also be observed by using [START_REF] Bender | The distribution of subword counts is usually normal[END_REF] constructions;

-if p = 0 the background texts have no letters a and both counts of a 3 and a 7 are zero.

-if p = 1 the texts are sequences of a. In such texts of length larger than 7, the number of counts of a 3 exceeds exactly by 4 the number of counts of a 7 .

In all other cases (p = 0 and p = 1), the results of [START_REF] Bender | The distribution of subword counts is usually normal[END_REF] imply as limit a Gaussian law of dimension 2 for the two joint counts.

Conclusion and perspectives

We obtained a detailed proof and an explicit expression of the multivariate generating function counting texts according to their length and to their number of occurrences of words from a finite set. This result facilitates access to various moments and may lead to limiting distributions. From Bender and Kochman [START_REF] Bender | The distribution of subword counts is usually normal[END_REF], we expect to find mostly a multivariate normal law for word counts. Our approach can possibly provide simpler criteria to decide if such a limiting law holds or not. Another nice aspect of the inclusion-exclusion approach is that it provides explicit formulae like Equation (21) p. 19, whereas the Aho-Corasick construction does not give immediate access to the structure of correlations of the words; this can be a crucial advantage when looking for second moments of structures such as suffix-trees.

Ongoing work is more concerned with the complexity of the diverse approaches presented in this article. Also we plan to extend the analysis to more complex sources, such as Markovian or dynamical sources (see Vallée [Vallée 2001]).