WEAK REPETITIONS IN STRINGS

L. J. Cummings

Faculty of Mathematics University of Waterloo

W. F. Smyth

Department of Computer Science & Systems McMaster University

School of Computing Curtin University of Technology

ABSTRACT

A weak repetition in a string consists of two or more adjacent substrings which are permutations of each other. We describe a straightforward Θ(n^{2}) algorithm which computes all the weak repetitions in a given string of length n defined on an arbitrary alphabet A. Using results on Fibonacci and other simple strings, we prove that this algorithm is asymptotically optimal over all known encodings of the output.

1 INTRODUCTION

Interest in the periodic behaviour of strings dates back to Thue [T06] at the turn of the century. Thue considered what we call here strong repetitions (equal adjacent substrings) and showed how to construct an infinitely long string on an alphabet of only three letters with no strong repetitions. (Other constructions on three letters have been discovered several times since, most recently by Dekking [D79] and Pleasants [P70] — the latter lists several references to earlier constructions.) More recently, Erdős [E61, p. 240] considered “Abelian squares” (what we call weak repetitions: adjacent substrings that are permutations of each other), and asked what was the minimum size of alphabet on which infinitely long strings with no weak repetitions could be constructed. In 1970 Pleasants [P70] gave a construction on an alphabet of five characters, and Keränen [K92] has very recently found a best possible construction on only four characters.

Typeset by AMS-TEX

It has been only in the last 15 years or so, with the increased modern emphasis on algorithms, that a problem more in the spirit of computer science has been considered: how to compute (efficiently) all the repetitions in a given string x of length n. It might be supposed that in the worst case such a computation would require time Ω(n^{2}), since it can easily be seen that the string x = a^{n} contains ⌊n^{2}/4⌋ strong (also weak) repetitions. (For example, a^{6} contains five distinct repetitions aa, three distinct repetitions a^{2}a^{2}, and one repetition a^{3}a^{3}.) However, in 1981 Crochemore [C81], using a clever encoding of repetitions (see the next section), devised a Θ(n log n) algorithm to compute all the strong repetitions in a string x defined on an ordered alphabet. Crochemore also showed that, in his encoding, a Fibonacci string of length n contains Ω(n log n) repetitions, so that, at least with respect to his encoding, his algorithm was “optimal”. Somewhat later, two other, quite different, algorithms for computing all the strong repetitions were published [AP83, ML84], both also requiring Θ(n log n) time, but now over an arbitrary alphabet.

This paper discusses, apparently for the first time, the computation of all the weak repetitions in x. This problem generalizes and includes the corresponding strong repetitions problem, since every strong repetition is also a weak one. In Section 2 we introduce some notation and terminology, in particular another encoding (called the R-encoding) which appears to be more natural for weak repetitions. In Section 3 we then describe an algorithm for computing all the weak repetitions in x: this “obvious” algorithm executes in time Θ(n^{2}) on all strings of length n. In Section 4, the main part of the paper, we show that, in the R-encoding, the Fibonacci string contains Θ(n^{2}) weak repetitions; further that, in Crochemore’s encoding, another simple string contains Θ(n^{2}) weak repetitions. With respect to known encodings, therefore, we conclude that the computation of all weak repetitions is a Θ(n^{2}) problem. A final section gives some brief concluding remarks.

2 TERMINOLOGY & NOTATION

Let A denote a (possibly infinite) set of distinct elements a_{i}, i = 1, 2, …., which are not required to be ordered. We call A an alphabet and its elements letters. Let A^{+} denote the set of all concatenations of elements of A, and let A^{∗} = {ϵ} ∪ A^{+}, where ϵ denotes the empty element. The elements of A^{∗} are called strings, and a string x of length |x| = n ≥ 1 is written x = x_{1}x_{2} ⋯ x_{n}, where each x_{i} ∈ A. If x = uv, then u is said to be a prefix and v a suffix of x. For any positive integer k, a concatenation of k identical strings u is written u^{k}.

A string x is said to be strongly periodic of order k if there exists an integer k > 1 and a string u ∈ A^{+} such that x = u^{k}. Similarly, x is said to be weakly periodic of order k if there exists k > 1 and u_{1} ∈ A^{+} such that x = u_{1}u_{2} ⋯ u_{k}, where each u_{i}, 2 ≤ i ≤ k, is a permutation of u_{1} (that is, a concatenation of the same elements of A, but not necessarily in the same order). When k = 2 in these definitions, x is said to be a strong (respectively, weak) square. If x is not strongly (respectively, weakly) periodic of any order k, then we shall say that x is strongly (respectively, weakly) primitive. If there exists a strongly (respectively, weakly) periodic string w such that x = uwv for some strings u, v ∈ A^{∗}, then w is said to be a strong (respectively, weak) repetition in x. The following observations are immediate consequences of these definitions:

* if x is strongly periodic of order k, then x is weakly periodic of order k;

* if x is weakly primitive, then x is strongly primitive;

* if x is strongly (respectively, weakly) periodic of order k and k′ | k, then x is strongly (respectively, weakly) periodic of order k′;

* the number of weak repetitions in x is at least as great as the number of strong repetitions in x.

Consider some examples on the alphabet A = {a, b}: x = abaababa is weakly primitive, therefore strongly primitive; x = abbaabba is weakly periodic of order 4, hence weakly periodic of order 2, and is also strongly periodic of order 2; x = bbaababa is strongly primitive and weakly periodic of order 2; x = abbabababaab is weakly periodic of order 6, hence weakly periodic of orders 2 and 3. The string x = abbaba contains strong (hence weak) repetitions b^{2} and (ba)^{2} and, in addition, the weak repetitions (ab)(ba) and (ab)(ba)(ba); as we have seen, the string x = a^{n} contains exactly ⌊n^{2}/4⌋ strong (hence weak) squares.

Observing that it suffices to compute maximum-length repetitions of primitive substrings, Crochemore [C81] improves the definition of strong repetition as follows. Suppose there exist an integer k > 1, strings u and v, and a nonempty strongly primitive string z such that x = uz^{k}v and z is neither a suffix of u nor a prefix of v. Then the strong repetition z^{k} is uniquely specified by the triple (|u|+1, |z|, k), where |u| + 1 gives the position of the repetition, |z| its period, and k its order. Clearly the collection of all such triples for a given string x specifies the strong repetitions of x; we call this collection the C-encoding of the strong repetitions and denote it C(x). With the obvious adjustments, a C-encoding of the weak repetitions can be defined in a similar way. Observe that for the string x = a^{n}, C(x) = {(1, 1, n)} for both strong and weak repetitions: thus all the repetitions in x, including the ⌊n^{2}/4⌋ squares, are described by a single triple.

Other encoding schemes are possible for strong/weak repetitions. For instance, one may think of the cth position of x as a centre of strong/weak squares of various lengths: then if a substring

x_{c,p}^{−}x_{c,p}^{+} = (x_{c−p}x_{c−p+1} ⋯ x_{c−1})(x_{c}x_{c+1} ⋯ x_{c+p−1})  (1)

were a strong/weak square of period p ≤ p_{c} = min{c − 1, n − c + 1} centred at c, it could be encoded by the pair (c, p). Clearly a collection of all such pairs (c, p) could be used to specify all the repetitions of x. This collection can be further compressed by taking advantage of cases where, for given c, the periods p fall into ranges of acceptable values; thus, for p_{2} ≥ p_{1}, the pairs (c, p_{1}), (c, p_{1} +1), …, (c, p_{2}) may be expressed as a range triple (c, p_{1}, p_{2}). A collection of such triples identifying all squares in x is called an R-encoding of the repetitions and denoted R(x). For the string x = a^{n}, for example, a minimum-cardinality R-encoding is given by R(x) = {(c, 1, p_{c}), c = 2, 3, …, n}, of cardinality n − 1.

In [C81] it was shown that, for Fibonacci strings f_{i}, i = 0, 1, …., and for strong repetitions,

|C(f_{i})| ∈ Ω(F_{i} log F_{i}),

where F_{i} denotes |f_{i}|. (Fibonacci strings are defined on A = {a, b} as follows: f_{0} = b, f_{1} = a; for every i ≥ 2, f_{i} = f_{i−1}f_{i−2}.) It follows then that, with respect to the C-encoding, the algorithms which compute strong repetitions in O(n log n) time are asymptotically optimal. In this paper we consider both the C-encoding and the R-encoding for weak repetitions, and exhibit classes of strings of length n such that both encodings necessarily contain Ω(n^{2}) elements; thus algorithms, such as the one described in Section 3, which compute weak repetitions in O(n^{2}) time, are also, with respect to known encodings, asymptotically optimal.

3 A WEAK REPETITIONS ALGORITHM

Here we outline a simple Θ(n^{2}) algorithm (called Algorithm A) which computes a minimum-cardinality R-encoding of the weak repetitions in a given string x = x_{1}x_{2} ⋯ x_{n}. We suppose that x contains exactly m distinct letters, which we denote by λ_{i}, i = 1, 2, …, m. Clearly m ≤ n. The algorithm considers in turn each potential centre c = 2, 3, …, n of x to determine every integer p ∈ [1, p_{c}] such that the pair (c, p) encodes a weak repetition. Recall that p_{c} = min{c − 1, n − c + 1}.

Algorithm A makes use of two O(n) integer arrays, Σ[0..m] and INDEX[1..n]. For i = 1, 2, …, m, Σ[i] is used as a counter of the number of occurrences of λ_{i}: each occurrence to the left of c is counted with a decrement of 1, while each occurrence to the right is counted with an increment of 1. Σ[0] is used as a “global” counter: as we shall see, Σ[0] = 0 if and only if a weak repetition has been found.

The array INDEX is used to specify positions in Σ, according to the following rule:

INDEX[j] = i ⟺ x_{j} = λ_{i}.

Thus Σ[INDEX[j]] is the counter corresponding to x_{j}, and so INDEX effectively replaces x, which is not mentioned at all in the main part of the algorithm.

The replacement of x by INDEX is performed in a preprocessing phase. Where x is defined on an arbitrary alphabet A, this replacement requires time O(n^{2}); if A is totally ordered, the replacement can be effected (using a search tree, for example) in time O(n log n); if A is fixed and finite, conversion reduces to an O(n) table lookup procedure.

Corresponding to each potential centre c = 2, 3, …, n, Algorithm A computes a linked list L consisting of all ranges [p_{1}, p_{2}] such that for every p ∈ [p_{1}, p_{2}], (c, p) encodes a weak square. To accomplish this, the algorithm first initializes L to a single entry [1, p_{c}] and then updates L by eliminating ranges which cannot give rise to weak repetitions. After all updates to L have been made, therefore, L consists of exactly those ranges of values of p which do give rise to weak repetitions. Over all possible values of c, the aggregate of these lists is equivalent to a minimumcardinality R(x), and since L can contain at most ⌈p_{c}/2⌉ elements, it is clear that |R(x)| ∈ O(n^{2}). Moreover, since the algorithm handles the update of L without backtracking — that is, in monotone increasing order of p —, it follows that, for each c, update of L requires time O(n) and, over all values of c, time O(n^{2}).

Corresponding to each potential centre c = 2, 3, …, n, Algorithm A first initializes all counters to zero, initializes L, and then, for each integer p = 1, 2, …, p_{c}, decrements the counter Σ[INDEX[c−p]] and increments Σ[INDEX[c+p−1]]. The entire processing for each centre c is as follows: initialize all counters to zero; L ← [1, p_{c}]; for p ← 1 to p_{c} do

i ← INDEX[c − p]; Σ[i] ← Σ[i] − 1; if Σ[i] ≥ 0 then Σ[0] ← Σ[0] − 1

else

Σ[0] ← Σ[0] + 1; i ← INDEX[c + p − 1]; Σ[i] ← Σ[i] + 1; if Σ[i] ≤ 0 then Σ[0] ← Σ[0] − 1

else

Σ[0] ← Σ[0] + 1; if Σ[0] ≠ 0 then delete p from L.

It is easy to see that Σ[0] = 0 after the processing for the current value of p if and only if (c, p) encodes a weak square. Over all values of c and p, the interior of the for loop for p will be executed once for each of exactly ⌊n^{2}/4⌋ position pairs c − p and c + p − 1; it follows that Algorithm A requires Θ(n^{2}) time. As we have seen, the additional space required for Algorithm A consists of L, Σ and INDEX, and is thus Θ(n).

As an example of the operation of this algorithm, suppose

x = f_{6} = abaababaabaab

and consider c = 7 (so that p_{c} = 6). Then only for p = 1 and p = 4 does it occur that Σ[0] ≠ 0: for p = 1, L becomes {(2, 6)} and for p = 4, L becomes {(2, 3), (5, 6)}. Thus the elements of R(x) which are output corresponding to c = 7 are (7, 2, 3) and (7, 5, 6).

The algorithm described here is an “obvious” algorithm, but it does not appear to be easy to improve on. We have devised two other algorithms as follows:

* Algorithm B, which, for each potential centre c, eliminates periods p from L which are inconsistent with the distribution of each individual letter λ_{i} in x;

* Algorithm C, which, for each c, eliminates from L all periods p which are inconsistent with a “balance” between pairs of letters found close to position c in x.

Neither of these algorithms can guarantee that backtracking will not occur in the update of L, and so each executes in time O(mn^{2}). However, since it would not always be necessary to test all pairs of positions in x, it was expected that in many cases these algorithms would execute more quickly than Algorithm A. Timed runs of all the algorithms on long repetition-free and repetition-dense strings have not supported this expectation [TT93]: Algorithms B and C both appear to execute much more slowly on average than Algorithm A.

4 DISCUSSION OF COMPLEXITY

In this section we show that for Fibonacci strings f_{n}, |R(f_{n})| ∈ Ω(F_{n}^{2}), and also that for the strings g_{n} = (aababbab)^{n} of length 8n, |C(g_{n})| ∈ Ω(n^{2}). We conclude then that Algorithm A is asymptotically optimal over the C- and R-encodings of the output.

We consider first g_{n} = (aababbab)^{n}, a string of length G_{n} = 8n. In particular, we consider the weak repetitions of g_{n} as expressed in the C-encoding; indeed, we initially confine our attention to those repetitions (i, p, k) where i ≡ 1 (mod 8) and p ≡ 1 (mod 4). We show first that for this special class of weak repetitions, it must be true that k = 2, and hence that there exist exactly \binom{n+1}{2} of them.

Observe first that for i ≡ 1 (mod 8), g_{n}[i] = a. Observe also that g_{n} may be written in the form

a(abab)(baba)(abab)(baba) … (abab)bab,

so that for p = 1, 5, 9, …, there exists a weak square (in fact a palindrome)

a(ababbaba)^{(p−1)/4}a,  (2)

provided that

i + 2p − 1 ≤ 8n.  (3)

We see that each component of each square (2) necessarily contains (p + 1)/2 a’s and (p − 1)/2 b’s; that is, an excess of a’s over b’s of one. Furthermore, each such square is followed by substrings b, ba, bab, babb …, each of which will contain at least as many b’s as a’s. Thus no squares (2) can be extended to cubes, from which we conclude that k = 2.

We wish now to count the number of occurrences ν_{n} of the weak squares (i, p, 2) in g_{n}. From (3) it follows that p ≤ (8n − i + 1)/2, so that

ν_{n} = ∑_{i=1(8)}^{8n−7} ∑_{p=1(4)}^{(8n−i+1)/2} 1

= ∑_{i=1(8)}^{8n−7}(n − (i − 1)/8)

= n^{2} − ∑_{i=1}^{n}(i − 1)

= \binom{n + 1}{2}.

Essentially the same argument, with the roles of a and b reversed, shows that for i ≡ 5 (mod 8) and p ≡ 1 (mod 4) there are another \binom{n+1}{2} weak squares (i, p, 2). Similarly, the cases i ≡ 3 (mod 8) and i ≡ 7 (mod 8) with p ≡ 3 (mod 4) add an additional \binom{n+1}{2} and \binom{n}{2} weak squares, respectively. Thus the total number of weak repetitions in the C-encoding for odd positions i of g_{n} is 3\binom{n+1}{2} + \binom{n}{2} = 2n^{2} + n. We have then

Theorem 1. |C(g_{n})| ∈ Θ(G_{n}^{2}). □

In fact, it is also true for the R-encoding that |R(g_{n})| ∈ Θ(G_{n}^{2}). But it turns out in this case, due to the regularity of g_{n}, that a very slight modification of the R-encoding can be used to reduce the output required to Θ(G_{n}). The modification required is to replace the triples (c, p_{1}, p_{2}) of the R-encoding by quadruples (c, p_{1}, d, k) representing the squares

(c, p_{1}), (c, p_{1} + d), …, (c, p_{1} + (k − 1)d).

Therefore, in order to establish more clearly that the R-encoding requires in the worst case output quadratic in the length of the string, we consider next the Fibonacci string f_{n} and show that |R(f_{n})| ∈ Ω(F_{n}^{2}).

The Parikh or frequency vector of a string x = x_{1}x_{2} ⋯ x_{n} over an alphabet A is an integer vector ϕ(x) of length α = |A|, where the ith element ϕ(x)[i] counts the number of occurrences in x of the ith element of A. (For example, if A = {a, b}, then ϕ(a) = (1, 0) and ϕ(b) = (0, 1).) For strings x,y over A, it is easy to see that

ϕ(xy) = ϕ(x) + ϕ(y).

Observe also that xy is a weak square if and only if ϕ(x) = ϕ(y), so that in such a case ϕ(xy) = 2ϕ(x). We state a special case of an important lemma on Sturmian strings which will be useful later:

Lemma 1. Let u and v denote any two substrings of equal length of a Fibonacci string. Then ϕ(u) − ϕ(v) can only take one of the values (0, 0), (−1, 1), (1, −1). Proof. See [BS93]. □

Let ws(x) denote the number of weak squares (of the form (c, p)) in a string x. We now turn our attention to the estimation of ws(f_{n}). Clearly ws(f_{n}) ≥ |R(f_{n})|. In order to estimate more precisely, consider the two-dimensional array T = T [1..F_{n}, 1..F_{n}] formed by applying the following rule:

T [c, p] = 1, if f_{n} contains a weak square (c, p);

= 0, otherwise.

Recall from Section 2 the definition of p_{c}, which for Fibonacci strings we modify to

p_{c} = min{c − 1, F_{n} − c + 1}.

Then clearly for every p > p_{c}, T [c, p] = 0, so that row c of T contains at most p_{c} nonzero entries and column p is all zeros for every p > F_{n}/2. Observe also that for integers p such that 1 ≤ p ≤ F_{n}/2, column p of T contains at most F_{n} − 2p + 1 nonzero entries. Since the number of weak squares is just the number of ones in T, we can then easily compute a crude upper bound for ws(f_{n}):

Lemma 2. ws(f_{n}) ≤ ⌊F_{n}^{2}/4⌋. Proof. The upper bound is just the sum of the possibly nonzero entries in the columns of T. When F_{n} is even, this sum is

(F_{n} − 1) + (F_{n} − 3) + ⋯ + 1 = F_{n}^{2}/4;

and when F_{n} is odd, the sum is

(F_{n} − 1) + (F_{n} − 3) + ⋯ + 2 = (F_{n}^{2} − 1)/4.

Both these sums reduce to ⌊F_{n}^{2}/4⌋. □

Obviously, the upper bound in Lemma 2 is far from being best possible. For example, f_{8} has length F_{8} = 34 and contains 136 weak squares, but the bound provided by Lemma 2 is 289. In order to compute more precise bounds on ws(f_{n}), we consider now what may be called the diagonals of the array T. These are ordered collections of the values of all those positions in T which may possibly take the value 1; they are defined as follows:

D_{c} : {T [c, c − 1], T [c + 1, c − 2], …, T [2c − 2, 1]},  (4)

where c = 2, 3, …, M, with M = ⌈F_{n}/2⌉ if F_{n} is odd and ⌈F_{n}/2⌉ + 1 otherwise; and

D′_{c} : {T [c + 1, c − 1], T [c + 2, c − 2], …, T [2c − 1, 1]},  (5)

for c = 2, 3, …, ⌈F_{n}/2⌉. The collections D_{c} and D′_{c} are interleaved cross-diagonal entries that together fill a triangle of T whose sides are the first column, the main cross-diagonal, and the first diagonal below the main diagonal. Observe that |D_{c}| = |D′_{c}| = c − 1. From now on we shall treat the D_{c} and D′_{c} simply as strings of length c − 1 defined on the alphabet A = {0, 1}.

The following lemma shows that adjacent positions in any D_{c} or D′_{c} can be both zero or both one only if the substring aa occurs at a specified location in f_{n}. This will pave the way for showing that approximately half of the entries in each D_{c} or D′_{c} are ones, hence that the number of weak squares in f_{n} is order F_{n}^{2}.

Lemma 3. Suppose x is any Fibonacci string. For integers c ∈ [3, F_{n} − 1] and p ∈ [2, p_{c}], let h_{1} = T [c, p] and h_{2} = T [c+1, p−1] denote adjacent positions in some diagonal D_{c} or D′_{c} of the array T. Then h_{1} = h_{2} if and only if x_{c−p} = x_{c−p+1} = a. Proof. Let q denote the Parikh vector of x_{c} and let q′ denote the Parikh vector of x_{c−p}x_{c−p+1}. Observe that q = (0, 1) or (1, 0) and that, since b^{2} never occurs in any Fibonacci string, q′ ≠ (0, 2). It follows that q′ = (2, 0) if and only if x_{c−p} = x_{c−p+1} = a. Recall the notation x_{c,p}^{−} and x_{c,p}^{+} introduced in (1). Now let

δ_{1} = ϕ(x_{c,p}^{−}) − ϕ(x_{c,p}^{+}),  (6)
δ_{2} = ϕ(x_{c+1,p−1}^{−}) − ϕ(x_{c+1,p−1}^{+}),  (7)

and observe by Lemma 1 that δ_{1} and δ_{2} can assume only the values (0, 0), (1, −1), or (−1, 1). From (6) it follows that

ϕ(x_{c+1,p−1}^{+}) = ϕ(x_{c,p}^{+}) − q,
ϕ(x_{c+1,p−1}^{−}) = ϕ(x_{c,p}^{+}) + δ_{1} + q − q′,

and so (7) implies that

q′ = (δ_{1} − δ_{2}) + 2q.  (8)

First consider the case h_{1} = h_{2} = 1; that is, δ_{1} = δ_{2} = (0, 0). Then (8) implies that q′ = 2q and, since q′ ≠ (0, 2), it follows that q′ = (2, 0).

Next suppose that h_{1} = h_{2} = 0, so that neither δ_{1} nor δ_{2} can equal (0, 0). Then if δ_{1} = δ_{2}, (8) tells us again that q′ = (2, 0); while otherwise δ_{1} = −δ_{2}, so that (8) reduces to q′ = 2(δ_{1} + q), once more implying that q′ = (2, 0).

Conversely, when h_{1} = 1 and h_{2} = 0, it follows from (8) that q′ = 2q − δ_{2}, where δ_{2} = (−1, 1) or (1, −1); this equality can hold only if q′ = (1, 1). We reach the same conclusion in the case h_{1} = 0, h_{2} = 1. Since all possibilities have been considered, the result is proved. □

Lemma 4. Suppose x is any Fibonacci string. Let d denote any bit string (4) or (5) of length c − 1 corresponding to x, and suppose that ϕ(d) = (i, j), where i counts the frequency of zeros and j the frequency of ones. Then

(a) j = i + 1 if and only if c is even and

x_{c+1,c−1}^{−}x_{c+1,c−1}^{+} = x_{1}x_{2} ⋯ x_{2c−2}

has suffix aa;

(b) i = j + 2 if and only if c is odd and x_{c+1,c−1}^{−}x_{c+1,c−1}^{+} has suffix aaba;

(c) j ≤ i ≤ j + 1, otherwise. Proof. Suppose first that d = D_{c} for some valid integer c. To exclude trivial cases, suppose that c ≥ 3. Then the c − 1 entries d_{h}, h = 1, 2, …, c − 1, in d are 1 or 0 according as the c − 1 substrings

x_{c,c−1}^{−}x_{c,c−1}^{+} = (x_{1}x_{2} ⋯ x_{c−1})(x_{c} ⋯ x_{2c−2})
x_{c+1,c−2}^{−}x_{c+1,c−2}^{+} = (x_{3}x_{4} ⋯ x_{c})(x_{c+1} ⋯ x_{2c−2})
⋮
x_{2c−2,1}^{−}x_{2c−2,1}^{+} = x_{2c−3}x_{2c−2}

are squares or not, respectively. Observe that d_{h} = T [c + h − 1, c − h]. Therefore, by Lemma 3, consecutive entries d_{h} and d_{h+1}, 1 ≤ h ≤ c − 2, are unequal if and only if x_{2h−1} ≠ x_{2h}. Thus consecutive entries in d flipflop (from 0 to 1, or from 1 to 0) as determined by the first c − 2 pairs of entries in x:

x_{1}x_{2}, x_{3}x_{4}, …, x_{2c−5}x_{2c−4}.

Consider the case in which one of these pairs is aa. Occurrences of aa cannot exist either at the beginning or at the end of x, and in fact must always be embedded in substrings x′ = abaaba; that is, preceded by a pair ab and followed by a pair ba. Thus, except in the case that the substring x′ in question is a terminating substring (suffix) of x_{c,c−1}^{−}x_{c,c−1}^{+} = x_{1}x_{2} ⋯ x_{2c−2}, the entries in d corresponding to x′ must be either 1001 or 0110, depending on whether or not the substring marks the beginning of a square in x. In each of these cases, the number of zeros equals the number of ones, and the final entry equals the initial one. Since pairs in x which are not aa must be either ab or ba, each of which causes a flipflop in d, it follows that, except when x′ is a suffix, the number of ones and the number of zeros in d can differ by at most one. In particular, for any even position h < c − 1,

ϕ(d_{1}d_{2} ⋯ d_{h}) = (h/2, h/2),  (9)

a fact used below.

Now consider the case in which x′ is a suffix of x_{1}x_{2} ⋯ x_{2c−2}. In this case the final entries in d are either 100 or 011. But observe in particular that the final entry d_{c−1} in d is determined by whether or not x_{2c−3} = x_{2c−2}; that is, whether or not b = a. Thus d_{c−1} = 0, so that only the case 100 is possible. In this case, if in addition c is odd, it follows from (9) that ϕ(d_{1}d_{2} ⋯ d_{c−3}) = (\frac{c−3}{2}, \frac{c−3}{2}), and so i = (c + 1)/2 = j + 2. (That this case actually arises may be seen by considering f_{8} and c = 13.)

Finally, consider the only remaining case: aa a suffix of x_{1}x_{2} ⋯ x_{2c−2}. This is the only case in which d_{c−1} = 1, and, since aa is always preceded by ab, it follows that d_{c−2} = 0. Thus when c is odd, ϕ(d) = (\frac{c−1}{2}, \frac{c−1}{2}), while when c is even, ϕ(d) = (\frac{c}{2} − 1, \frac{c}{2}), so that j = i + 1.

Thus the result is proved for d = D_{c}. An almost identical argument establishes the result also for d = D′_{c}. □

We remark now that in the strings D_{c} and D′_{c}, every instance in which case (a) of Lemma 4 holds is matched by an instance of case (b), and vice versa. That is, c is odd and x_{1}x_{2} ⋯ x_{2c−2} has suffix aaba if and only if c − 1 is even and x_{1}x_{2} ⋯ x_{2c−4} has suffix aa. It follows that in counting the cumulative frequency of ones in the D_{c} and in the D′_{c}, we can simply ignore cases (a) and (b), and count ⌊(c − 1)/2⌋ ones in each of these strings. The total number of ones in T is then just the sum of ⌊(c − 1)/2⌋ over all strings D_{c} and D′_{c}, where c takes the values specified in (4) and (5). For example, for F_{n} ≡ 3 (mod 4), it is not difficult to compute that

\begin{aligned}ws(f_{n}) & = ∑_{k=1}^{(F_{n}−3)/4} k \\ & = (F_{n}^{2} − 2F_{n} − 3)/8. \end{aligned}

Similar calculations may be carried out for F_{n} ≡ 0, 1, 2 (mod 4), yielding

Theorem 2. ws(f_{n}) = (F_{n}^{2} − 2F_{n} + q)/8, where (a) q = 0 if F_{n} ≡ 0 (mod 2);

(b) q = 1 if F_{n} ≡ 1 (mod 4);

(c) q = −3 if F_{n} ≡ 3 (mod 4). □

This result specifies the number of weak squares (c, p) in f_{n}. However, the question remains whether, by encoding every collection (c, p_{1}), (c, p_{1}+1), …, (c, p_{2}) of weak squares as a single triple (c, p_{1}, p_{2}), an algorithm could perhaps run faster than O(F_{n}^{2}); that is, in time proportional to something less than the square of the string length. For example, in f_{6} the weak repetitions can be encoded by only 10 triples: (4, 1, 3), (6, 2, 3), (6, 5, 5), (7, 2, 3), (7, 5, 6), (9, 1, 3), (9, 5, 5), (10, 3, 3), (11, 3, 3), (12, 1, 2). Without the use of the triples, 18 pairs (c, p) would be required.

Observe that any one of these output triples, say (c, p_{1}, p_{2}), corresponds to a sequence, or run, of one or more consecutive ones in row c of the matrix T; specifically,

T [c, p_{1}] = T [c, p_{1} + 1] = ⋯ = T [c, p_{2}] = 1,

where T [c, p_{2} + 1] = 0 and also

p_{1} > 1 ⟹ T [c, p_{1} − 1] = 0.

Thus whenever 01 occurs in row c of T, a run (triple) is beginning, and whenever 10 occurs, a run (triple) is ending. Therefore, to determine a lower bound on the number of output triples, we may count the occurrences of 01 or of 10. As it turns out, it is convenient (and sufficient) to count the total occurrences of both 01 and 10, and then divide by two; the following technical lemma provides the basis for doing this.

Lemma 5. Let x denote any Fibonacci string, and let i ≥ 1 and j ≥ i + 3 denote any two nonadjacent positions in x such that j − i is odd. Let

c = (i + j + 1)/2, p = (j − i − 1)/2.

Then T [c, p] = T [c, p + 1] if and only if x_{i} = x_{j}. Proof. Since the occurrences are nonadjacent, and since j −i is odd, it follows that a substring w of even length lies between positions i and j. In fact, w = x_{c,p}^{−}x_{c,p}^{+}, where c and p are as defined in the statement of the lemma.

Suppose first that x_{i} = x_{j}, and consider the case in which w is a weak square. Then T [c, p] = 1. But since x_{i} = x_{j}, it follows that T [c, p + 1] = 1 also. Similarly, when w is not a weak square, it is clear that T [c, p] = T [c, p + 1] = 0.

Conversely, suppose that T [c, p] = T [c, p + 1]. If w is a weak square, then we see that x_{i}wx_{j} must be also, and so we conclude that x_{i} = x_{j}. Similarly, if w is not a weak square, then neither is x_{i}wx_{j}, and so it follows from Lemma 1 that, in this case also, x_{i} = x_{j}. □

Lemma 5 tells us that by counting all the pairs (i, j), j −i ≥ 3, for which x_{i} ≠ x_{j} and j − i is odd, we will identify all cases in which T [c, p] ≠ T [c, p + 1]; that is, all occurrences of 01 (beginning of a run of ones) and of 10 (end of a run of ones) in the triangle of T determined by the strings (4) and (5). These occurrences do not include all beginnings and all ends of runs; specifically excluded are beginnings of runs for which p = 1 (corresponding to occurrences of aa in x) and endings of runs for which p = p_{c}. Thus the number of pairs (i, j) is only a lower bound on the number of runs; nevertheless, as we shall now show, this number is Θ(|x|^{2}).

Suppose that some Fibonacci string f_{n} is given, n ≥ 3. It is easy to show that b occurs F_{n−2} times in f_{n}, and so it follows that there are F_{n−1} occurrences of a. Let m > 1 denote the number of b’s at odd positions of f_{n}; then F_{n−2} − m b’s occur at even positions. Note that there are ⌈F_{n}/2⌉ odd positions and ⌊F_{n}/2⌋ even positions in f_{n}. Hence there are ⌈F_{n}/2⌉ − m a’s at odd positions and ⌊F_{n}/2⌋ − F_{n−2} + m a’s at even positions.

To simplify the computation a little, let us assume that n is odd, so that f_{n} ends in a and every occurrence of b has exactly two neighbouring occurrences of a. It is these two neighbouring occurrences that are excluded by the “nonadjacent” condition of Lemma 5. Then over all b’s occurring at odd positions, the total number of nonadjacent pairs with a’s occurring at even positions is given by

m(⌊F_{n}/2⌋ − F_{n−2} + m − 2).

Similarly, the total number of nonadjacent pairs corresponding to b’s at even positions and a’s at odd positions is

(F_{n−2} − m)(⌈F_{n}/2⌉ − m − 2).

Then |R(f_{n})|, the total number of runs of ones in T, is at least

\frac{1}{2}\{m(⌊F_{n}/2⌋ − ⌈F_{n}/2⌉ − F_{n−2} + 2m) + F_{n−2}(⌈F_{n}/2⌉ − m − 2)\}

> \frac{1}{2}\{F_{n−2}(F_{n}/2 − 2) − m(2F_{n−2} − 2m + 2)\}

= m^{2} − (F_{n−2} + 1)m + F_{n−2}(F_{n}/2 − 2)/2 ≡ g(m).

The function g(m) achieves its minimum value if

\frac{dg(m)}{dm} = 2m − (F_{n−2} + 1) = 0;

that is, if m = (F_{n−2} + 1)/2. In this case,

g(m) = (F_{n−2}(F_{n−1} − 6) − 1)/4.

Since F_{n−2} > F_{n}/3, it follows that for sufficiently large n, g(m) > F_{n}^{2}/36, and hence that |R(f_{n})| ∈ Ω(F_{n}^{2}). Since |R(f_{n})| < ws(f_{n}), so that by Theorem 2 |R(f_{n})| ∈ O(F_{n}^{2}), we have thus proved

Theorem 3. |R(f_{n})| ∈ Θ(F_{n}^{2}). □

In fact, it appears that, making use of more precise calculations, it is possible to establish that |R(f_{n})| ≈ ws(f_{n})/2.

5 CONCLUDING REMARKS

In this paper we have presented a simple Θ(n^{2}) algorithm for finding all the weak repetitions in a given string x of length n. We have shown that this algorithm is optimal over known encodings of the output; in the course of doing so, we have derived an exact expression for the number of weak squares in a Fibonacci string.

We remark that the methodology used to count weak squares and weak repetitions in Fibonacci strings may also have applications to similar counting problems on other strings.

The results of this paper suggest, but do not clearly establish, that the computation of the weak repetitions in x is an Ω(n^{2}) problem. To prove this conjecture, it would be necessary to find an information-theoretic argument that would show that Θ(n^{2}) processing steps are required in the worst case. In fact, an even stronger result has been proved for the strong repetitions problem [ML84]: Main and Lorentz show that, over a possibly infinite alphabet, Ω(n log n) time is required to determine whether or not x contains a strong repetition. We give here a somewhat different proof which applies also to weak repetitions.

For a string x of length n, suppose that n = 2^{k} for some positive integer k, and suppose further that the letter x_{n/2} does not appear in x_{n/2+1}x_{n/2+2} ⋯ x_{n}. Suppose in fact that this property applies recursively to substrings of x of length 2^{k−1}, 2^{k−2}, …, 1. It follows then that any weak (or strong) repetition in x occurs either in the substring x_{1}x_{2} ⋯ x_{n/2} or in x_{n/2+1}x_{n/2+2} ⋯ x_{n}. In order to verify this fact, it is both necessary and sufficient to perform n/2 comparisons of x_{n/2} against x_{n/2+1}, x_{n/2+2}, …, x_{n}. Let c(n) denote the number of comparisons required to perform the verification. Then

c(n) = 2c(n/2) + n/2,

a recurrence relation which can easily be solved, using the initial condition c(1) = 0, to yield

c(n) = \frac{n}{2} log_{2} n.

Hence

Theorem 4. Let x be a string of length n. The time required to determine whether or not x contains a (strong or weak) repetition is Ω(n log n). □

It appears likely that for weak repetitions the lower bound of Theorem 4 can be increased to Ω(n^{2}). If so, then it would follow that any other weak repetitions algorithms would necessarily require Θ(n^{2}) time.

REFERENCES [AP83] A. Apostolico & F. P. Preparata, Optimal off-line detection of repetitions in a string, Theoretical Comp. Sci. 22 (1983) 297-315.

[BS93] J. Berstel & P. Séé, A characterization of Sturmian morphisms, The Mathematical Foundations of Computer Science, A. Borzyszkowski & S. Sokolowski (eds.), Springer-Verlag (1993) 281-290.

[C81] M. Crochemore, An optimal algorithm for computing the repetitions in a word, Inf. Proc. Lett. 12-5 (1981) 244-250.

[D79] F. M. Dekking, Strongly non-repetitive sequences and progressionfree sets, JCT Series “A” 27 (1979) 181-185.

[E61] P. Erdős, Some unsolved problems, Hungarian Academy of Sciences Mat. Kutató Intézet Közl. 6 (1961) 221-254.

[K92] V. Keränen, Abelian squares are avoidable on 4 letters, Lecture Notes in Computer Science 623, Springer-Verlag (1992) 41-52.

[ML84] M. G. Main & R. J. Lorentz, An O(nlogn) algorithm for finding all repetitions in a string, J. Algs. 5 (1984) 422-432.

[P70] P. A. Pleasants, Non-repetitive sequences, Proc. Cambridge Phil. Soc. 68 (1970), 267-274.

[T06] A. Thue, Über unendliche Zeichenreichen, Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana 7 (1906) 1-22.

[TT93] C. Y. Tan & T. K. K. Teo, honours project, School of Computing, Curtin University (1993).

ACKNOWLEDGEMENTS

The work of both authors was supported in part by grants from the Natural Sciences & Engineering Research Council of Canada. The authors express their appreciation of the work of Chin Yong Tan and Kelvin Teo of Curtin University, who programmed and tested the algorithms discussed in this paper.

Revised 8 November 1994