BRICS RS-95-46 Breslauer et al.: The Comparison Complexity of the String Pre�x-Matching

BRICS

Basic Research in Computer Science

On the Comparison Complexity of the String Pre�x-Matching Problem

Dany Breslauer Livio Colussi Laura Toniolo

BRICS Report Series RS-95-46 ISSN 0909-0878 August 1995 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1995, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent publications in the BRICS Report Series. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK - 8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@daimi.aau.dk

BRICS publications are in general accessible through WWW and anonymous FTP:

http://www.brics.aau.dk/BRICS/
ftp ftp.brics.aau.dk (cd pub/BRICS)

On the Comparison Complexity of the String Prefix-Matching Problem

Dany Breslauer^{∗}  Livio Colussi^{†}  Laura Toniolo^{‡}

Abstract

In this paper we study the exact comparison complexity of the string prefix-matching problem in the deterministic sequential comparison model with equality tests. We derive almost tight lower and upper bounds on the number of symbol comparisons required in the worst case by on-line prefix-matching algorithms for any fixed pattern and variable text. Unlike previous results on the comparison complexity of string-matching and prefix-matching algorithms, our bounds are almost tight for any particular pattern.

We also consider the special case where the pattern and the text are the same string. This problem, which we call the string self-prefix problem, is similar to the pattern preprocessing step of the Knuth-Morris-Pratt stringmatching algorithm that is used in several comparison efficient stringmatching and prefix-matching algorithms, including in our new algorithm. We obtain roughly tight lower and upper bounds on the number of symbol comparisons required in the worst case by on-line self-prefix algorithms. Our algorithms can be implemented in linear time and space in the

standard uniform-cost random-access-machine model.

∗BRICS – Basic Research in Computer Science, Centre of the Danish National Research Foundation, Department of Computer Science, University of Aarhus, DK-8000 Aarhus C, Denmark. Partially supported by the ESPRIT Basic Research Action Program of the EC under contract #7141 (ALCOM II). Part of the research reported in the paper was carried out while this author was visiting at the Istituto di Elaborazione dell’Informazione, Consiglio Nazionale delle Ricerche, Pisa, Italy, with the support of the European Research Consortium for Informatics and Mathematics postdoctoral fellowship.

†Dipartimento di Matematica Pura ed Applicata, Università di Padova, Via Belzoni 7, I-35131 Padova, Italy. Partially supported by “Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo” of the Italian National Research Councile under grant number 89.00026.69.

‡Dipartimento di Matematica Pura ed Applicata, Università di Padova, Via Belzoni 7, I-35131 Padova, Italy. Parts of the research reported in this paper were carried out while this author was visiting at the Institut Gaspard Monge, Université de Marne-la-Vallée, Noisy-le-Grand, France, supported by “Borsa di studi per attività di perfeziomento all’estero” from the University of Padua, and at BRICS, Department of Computer Science, University of Aarhus, Aarhus, Denmark, supported by the Gini Foundation of Padua.

1 Introduction

In the string prefix-matching problem one is interested in finding the longest prefix of a pattern string P[1..m] that starts at each position of a text string T [1..n]. The output of the problem is an integer array Φ[1..n], 0 ≤ Φ[t] ≤ min(m, n−t+1), such that for each text position t, T [t..t+Φ[t]−1] = P[1..Φ[t]] and if Φ[t] < m and t + Φ[t] ≤ n, then T [t + Φ[t]] ≠ P[Φ[t] + 1].

The string prefix-matching problem is a natural generalization of the standard string-matching problem where only complete occurrences of the pattern are sought. The classical linear-time string-matching algorithm of Knuth, Morris and Pratt [32] can be easily adapted to solve the prefix-matching problem in the same time bounds without making additional symbol comparisons^{1}. This observation was first made by Main and Lorentz [35] who used a prefixmatching algorithm to detect repetitions in strings. In the parallel setting, Galil’s [22] string-matching algorithm also solves the prefix-matching problem. Breslauer [5] and Hariharan and Muthukrishnan [31] gave more efficient parallel algorithms and recently Ga̧sieniec and Park [27] obtained a time-work optimal parallel prefix-matching algorithm. Prefix-matching algorithms have also been used in the sequential two-dimensional pattern-matching algorithms of Amir, Benson and Farach [2] and Galil and Park [25] and in an early version of the parallel two-dimensional pattern-matching algorithm of Cole et al. [11].

In this paper we study the exact number of comparisons performed by deterministic sequential prefix-matching algorithms that have access to the input strings by pairwise symbol comparisons that test for equality. This work was motivated by recent interest in the exact comparison complexity of the stringmatching problem and is continuation of an earlier work by the same authors [7].

In a sequence of papers on the number of symbol comparisons required in string-matching algorithms Colussi [14], Galil and Giancarlo [24], Breslauer and Galil [9] and Cole and Hariharan [12] improved the upper bounds, while Galil and Giancarlo [23], Zwick and Paterson [38], Cole and Hariharan [12] and Cole et al. [13] tightened the lower bounds. Currently, the complexity of the string-matching problem is determined almost exactly with an upper bound of n + (8/3m)(n − m) comparisons and a lower bound of n + (9/4m)(n − m) comparisons^{2}. There are numerous other papers that study the exact number of comparisons required in the string-matching problem, in order statistics problems and in various other problems. Most relevant perhaps is the literature on constant-space linear-time string-matching algorithms [6, 17, 20, 21, 26, 28] and on variants of the Boyer-Moore string-matching algorithm [3, 4, 10, 15, 18, 19, 29, 32, 33].

1Since complete occurrences of the pattern cannot start at text positions larger than n − m+1, the string-matching algorithm can stop before reaching the end of the text. The prefixmatching algorithm must continue until the end of the text and therefore, it might make at most m extra comparisons.

2These bounds are on the number of comparisons made by on-line algorithms in the text processing step, after an unaccounted pattern preprocessing. There is a larger gap between the lower and upper bounds for off-line algorithms.

Boyer and Moore [4] showed that in the string-matching problem it is not always necessary to examine all n text symbols. On the other hand, Rivest [37] has proved that in the worst case any string-matching algorithm must always examine at least n − m + 1 text symbols. Clearly, any algorithm that solves the prefix-matching problem must examine all n text symbols since it must determine if each text symbol is equal to the first pattern symbol. Note that if the input alphabet is known to contain only two symbols, then the prefix-matching problem requires exactly n comparisons, since inequality to one alphabet symbol implies equality to the other.

Breslauer, Colussi and Toniolo [7] defined on-line prefix-matching algorithms and presented a family of algorithms that make at most ⌊(2 − 1/m)n⌋ symbol comparisons. They also gave a tight lower bound for any prefix-matching algorithm that has to match the pattern ‘ab^{m−1}’. These results imply that the two similar string-matching and prefix-matching problems have intrinsically different asymptotic comparison complexities, approaching n and 2n, respectively, as m grows. However, on-line prefix-matching algorithms have many similarities to the on-line string-matching algorithms given by Colussi [14] and Breslauer and Galil [9]. The definition of on-line prefix-matching algorithms also coincides with the finite automata approach to string matching. In an analysis of Simon’s automata based string-matching algorithm Hancart [30] independently obtained the same bounds that were given in [7] for on-line prefix-matching algorithms (see also [16]). The new results about on-line prefix-matching algorithms presented in this paper apply as well to automata based string-matching, and thus extend also Hancart’s work.

Our main effort in this paper is to determine c_{on−line}^{P[1..m]}(n), the number of symbol comparisons required in the worst case by on-line prefix-matching algorithms to match a fixed pattern P[1..m] in a variable text of length n. We determine c_{on−line}^{P[1..m]}(n) almost exactly by showing that for any pattern P[1..m], there exists a constant C_{on−line}^{P[1..m]}, 1 ≤ C_{on−line}^{P[1..m]} ≤ 2 − 1/m, such that,

C_{on−line}^{P[1..m]} × (n − m) + m ≤ c_{on−line}^{P[1..m]}(n) ≤ C_{on−line}^{P[1..m]} × n.

And thus,

lim_{n→∞} \frac{c_{on−line}^{P[1..m]}(n)}{n} = C_{on−line}^{P[1..m]}.

The upper bound of at most C_{on−line}^{P[1..m]}×n comparisons is achieved by an algorithm that takes linear time and uses linear space. Unlike previous publications on the comparison complexity of string-matching and prefix-matching algorithms that give worst case bounds for a specific pattern, our bounds are almost tight for any given pattern.

We then consider the special case where the pattern and the text are the same string. This problem, which we call the self-prefix problem, is similar to the failure function that is computed in the preprocessing step of the Knuth-Morris-Pratt [32] string-matching algorithm^{3}. The Knuth-Morris-Pratt failure function is used in various string-matching algorithms and also in the pattern preprocessing step of our prefix-matching algorithm. Using the techniques we develop for the prefix-matching problem, we obtain an on-line algorithm for the self-prefix problem that makes at most 2m − ⌈\sqrt{2m}⌉ symbol comparisons. We also prove a roughly tight lower bound (up to an additive constant 2) on the number of symbol comparisons required by such an algorithm, and thus, determine the worst case comparison complexity of the on-line self-prefix problem and of computing the Knuth-Morris-Pratt failure function. The self-prefix algorithm and the whole pattern preprocessing step of the prefix-matching algorithm take linear time and use linear space.

Finally, we consider general off-line prefix-matching algorithms. Such algorithms are more difficult to analyze since they have more liberties about the way they might proceed comparing the input symbols. We were unable to obtain tight bounds for off-line algorithms. However, we show that there exist pattern strings for which off-line algorithms require significantly fewer symbol comparisons than on-line algorithms.

The paper is organized as follows. In Section 2 we give the lower and upper bounds for on-line prefix-matching algorithms. In Section 3 we prove that offline algorithms can be superior to on-line algorithms in some cases. In Section 4 we present the algorithm for the self-prefix problem and in Section 5 we show how to implement the prefix-matching and self-prefix algorithms in the standard random-access-machine model. Conclusions and open problems are given in Section 6.

2 On-line prefix-matching

The discussion below proceeds in the comparison model where only comparisons of input symbols are counted and all other computation is free. We assume that our algorithms can obtain complete information about the pattern P[1..m] in an unaccounted pattern preprocessing step that might compare even all \binom{m}{2} pairs of pattern symbols. In Section 5 we discuss the efficient implementation of our algorithms, including the pattern preprocessing, in the standard randomaccess-machine computational model [1].

Recall the definition of on-line string prefix-matching algorithms given by Breslauer, Colussi and Toniolo [7].

3In fact, these two problems are equivalent with respect to the number of comparisons they require; the output of either one can be computed from the output of the other in linear-time without any extra comparisons of the input symbols.

Definition 2.1 A prefix-matching algorithm is on line if before comparing the text symbol T [t] it has determined if the pattern prefixes that start at text positions l, for 1 ≤ l < t, terminate before text position t.

Comparison efficient on-line prefix-matching algorithms are restricted about the choice of comparisons they can make. It is not difficult to verify that on-line algorithms that compare pairs of text symbols are not more efficient than those that compare only pattern symbols to text symbols.

Let K^{t} = {k_{i}^{t} | t − m < k_{0}^{t} < ⋯ < k_{q_{t}}^{t} = t} be the set of all text positions for which Φ[k_{i}^{t}] can not be determined without examining T [t]. Namely, T [k_{i}^{t}..t − 1] = P[1..t − k_{i}^{t}] and T [t] must be compared in order to check whether Φ[k_{i}^{t}] = t−k_{i}^{t} or Φ[k_{i}^{t}] > t−k_{i}^{t}. Then, all comparisons at text position t must be between T [t] and the pattern symbols P[t − k_{i}^{t} + 1] or otherwise can be answered by an adversary as unequal without giving an algorithm any useful information, provided that the text alphabet is large enough.

Clearly, T [t] has to be compared either until it is found to be equal to some symbol P[t − k_{i}^{t} + 1] or until it is known to be different from all these symbols. Thus, the only difference between the comparison efficient on-line prefix-matching algorithms we consider next, is the order according to which T [t] is compared to the pattern symbols P[t − k_{i}^{t} + 1].

2.1 Periods in strings

Periods are regularities of strings that are exploited virtually in all efficient string-matching algorithms. In this section we give some basic properties of periods and define the notation that we use throughout the paper. For an extensive treatment of periods and their properties see Lothaire’s book [34].

Definition 2.2 A string S[1..h] has a period of length π if S[g] = S[g + π], for g = 1, …, h − π. We define the set Π^{S[1..h]} = {π_{i}^{S} | 0 = π_{0}^{S} < ⋯ < π_{p_{h}}^{S} = h} to be the set of all period lengths of S[1..h]. π_{1}^{S}, the smallest non-trivial period length of S[1..h], is called the period of S[1..h].

A string S[1..l], such that Π^{S[1..l]} = {0, l}, is sometimes called unbordered. The simple properties of periods given next follow immediately from the definition.

Proposition 2.3 The set Π^{S[1..l]} satisfies: Π^{S[1..l]} \ {l} ⊆ Π^{S[1..l−1]}.

In the last proposition the inclusion in the opposite direction usually does not hold; the periods π ∈ Π^{S[1..l−1]}, such that π ∉ Π^{S[1..l]}, are said to terminate at position l.

Proposition 2.4 For any π ∈ Π^{S[1..l]},

Π^{S[1..l]} ∩ {π, …, l} = {π + τ | τ ∈ Π^{S[1..l−π]}} .

Periods are connected to on-line prefix-matching algorithms by the following observation.

Lemma 2.5 The members of the set K^{t} correspond to the periods of the pattern prefix P[1..t − k_{0}^{t}] by the following relation:

K^{t} = {k_{0}^{t} + π | π ∈ Π^{P[1..t−k_{0}^{t}]}} .

Proof. By the definitions, if k_{i}^{t} ∈ K^{t}, then T [k_{i}^{t}..t − 1] = P[1..t − k_{i}^{t}]. In particular, T [k_{0}^{t}..t − 1] = P[1..t − k_{0}^{t}] and therefore P[1..t − k_{i}^{t}] = P[k_{i}^{t} − k_{0}^{t} + 1..t − k_{0}^{t}], establishing that k_{i}^{t} − k_{0}^{t} ∈ Π^{P[1..t−k_{0}^{t}]}. Similarly, if π ∈ Π^{P[1..t−k_{0}^{t}]}, then by the definition of periods P[1..t − k_{0}^{t} − π] = P[π + 1..t − k_{0}^{t}]. Since T [k_{0}^{t}..t − 1] = P[1..t − k_{0}^{t}] we get that T [k_{0}^{t} + π..t − 1] = P[1..t − k_{0}^{t} − π], establishing that k_{0}^{t} + π ∈ K^{t}. □

By Lemma 2.5, {P[t − k_{i}^{t} + 1] | k_{i}^{t} ∈ K^{t}}, the set of all the pattern symbols that T [t] might be compared to, is equal to {P[l − π] | π ∈ Π^{P[1..l−1]}}, for l = t − k_{0}^{t} + 1. We define Σ_{l}^{P} = {P[l − π] | π ∈ Π^{P[1..l−1]}}, for l = 1, …, m. Notice that Σ_{l}^{P} is a set, thus containing distinct symbols and identifying equal symbols. One can visualize this definition by aligning copies of the pattern P with the text starting at the positions k_{i}^{t} ∈ K^{t}; then the elements of Σ_{t−k_{0}^{t}+1}^{P} are the pattern symbols that are aligned with the text symbol T [t].

The following property follows immediately from the definitions.

Proposition 2.6 For any π ∈ Π^{P[1..l−1]}, Σ_{l−π}^{P} ⊆ Σ_{l}^{P}. Furthermore, if π = π_{1}^{P[1..l−1]}, then Σ_{l−π}^{P} ∪ {P[l]} = Σ_{l}^{P}. (Notice that Σ_{l−π}^{P} = Σ_{l}^{P} if and only if Π^{P[1..l]} ≠ {0, l}.)

Given some symbol σ ∈ Σ_{l}^{P}, we define two functions that give the smallest and the largest period lengths of P[1..l − 1] that introduce the symbol σ into the set Σ_{l}^{P}:

π_{first}^{l}(σ) = min {π | π ∈ Π^{P[1..l−1]} and P[l − π] = σ} ,

and,

π_{last}^{l}(σ) = max {π | π ∈ Π^{P[1..l−1]} and P[l − π] = σ} .

The function π_{first}^{l}(σ) is important in on-line algorithms since it determines what will be k_{0}^{t+1} as a function of k_{0}^{t} and T [t].

Lemma 2.7 If T [t] ∈ Σ_{t−k_{0}^{t}+1}^{P}, then k_{0}^{t+1} = k_{0}^{t} + π_{first}^{t−k_{0}^{t}+1}(T [t]), except if t −

k_{0}^{t} + 1 = m and T [t] = P[m], where k_{0}^{t+1} = k_{0}^{t} + π_{1}^{P[1..m]}.

Proof. Given k_{0}^{t} and T [t] ∈ Σ_{t−k_{0}^{t}+1}^{P}, by Lemma 2.5,

k_{0}^{t+1} = min {k_{i} | k_{i} ∈ K^{t} and T [t] = P[t − k_{i}^{t} + 1]} = k_{0}^{t} + π_{first}^{t−k_{0}^{t}+1}(T [t]),

with the exception that if a complete occurrence of the pattern is discovered, namely if t − k_{0}^{t} + 1 = m and T [t] = P[m], then k_{0}^{t} ∉ K^{t+1} and k_{0}^{t+1} = k_{0}^{t} + π_{1}^{P[1..m]}. □

The function π_{last}^{l}(σ) is used in the development of comparison efficient online algorithms. Its main properties are summarized in the following lemma.

Lemma 2.8 For any l = 1, …, m, and π ∈ Π^{P[1..l−1]},

π_{last}^{l}(σ) = π + π_{last}^{l−π}(σ) for σ ∈ Σ_{l−π}^{P}

and

π_{last}^{l}(σ) < π_{last}^{l}(τ) for σ ∈ Σ_{l}^{P} \ Σ_{l−π}^{P} and τ ∈ Σ_{l−π}^{P}.

Proof. By Proposition 2.6, π_{last}^{l}(σ) is defined for σ ∈ Σ_{l−π}^{P} and by Proposition 2.4, π_{last}^{l}(σ) = π + π_{last}^{l−π}(σ) ∈ Π^{P[1..l−1]}. By Proposition 2.4, if π_{last}^{l}(σ) ≥ π, then σ ∈ Σ_{l−π}^{P}. Thus, if τ ∈ Σ_{l−π}^{P}, then π_{last}^{l}(τ) ≥ π, and if σ ∈ Σ_{l}^{P} \ Σ_{l−π}^{P}, then π_{last}^{l}(σ) < π. □

The following technical lemmas will be used throughout the paper.

Lemma 2.9 The set Π^{P[1..l−1]} is disjointly partitioned according to Σ_{l}^{P}:

Π^{P[1..l−1]} = ⋃_{σ∈Σ_{l}^{P}} {π + τ | π = π_{first}^{l}(σ) and τ ∈ Π^{P[1..l−π]} and τ < l − π} .

Proof. Define for σ ∈ Σ_{l}^{P},

Π_{σ}^{l} = {π + τ | π = π_{first}^{l}(σ) and τ ∈ Π^{P[1..l−π]} and τ < l − π} .

By Proposition 2.3 and Proposition 2.4, Π_{σ}^{l} ⊆ Π^{P[1..l−1]}, for all σ ∈ Σ_{l}^{P}. In addition, if π̂ ∈ Π_{σ}^{l}, then P[l − π̂] = σ, establishing that the sets Π_{σ}^{l} are disjoint for different σ. On the other hand, if π̂ ∈ Π^{P[1..l−1]}, then π̂ ∈ Π_{P[l−π̂]}^{l}. □

Lemma 2.10 For any π ∈ Π^{P[1..l]} and 0 ≤ h ≤ l − π,

∑_{g=h+1}^{h+π} |Σ_{g}^{P}| ≤ 2π − 1.

Proof. Observe that if P[g − π] ≠ P[g], then π ∉ Π^{P[1..g]}. By Proposition 2.3,

|Σ_{g}^{P}| = | {P[g − π] | π ∈ Π^{P[1..g−1]}} |
= 1 + | {P[g − π] | π ∈ Π^{P[1..g−1]}} \ {P[g]} |
≤ 2 + |Π^{P[1..g−1]}| − |Π^{P[1..g]}|.

Thus, for any π, not necessarily a period length, such that 1 ≤ π ≤ l and 0 ≤ h ≤ l − π,

∑_{g=h+1}^{h+π} |Σ_{g}^{P}| ≤ 2π + |Π^{P[1..h]}| − |Π^{P[1..h+π]}|.

If π ∈ Π^{P[1..l]} \ {0}, then by Proposition 2.4, |Π^{P[1..h]}| ≤ |Π^{P[1..h+π]}| − 1, establishing the claim. □

The following two lemmas describe the relations between the lengths of the pattern prefixes and the maximal delay.

Lemma 2.11 Let d_{h} = max {|Σ_{l}^{P}| | l = 1, …, h}. Then,

2^{d_{h}} − 1 ≤ ∑_{l=1}^{h} |Σ_{l}^{P}| ≤ 2h − 1.

Proof. The right side inequality is a special case of Lemma 2.10. The left side inequality is proved by induction on h. By Proposition 2.6, d_{h} ≤ d_{h−1} + 1. The basis of the induction for h = 1 holds since |Σ_{1}^{P}| = 1 and d_{1} = 1. The inductive hypothesis clearly holds if d_{h} = d_{h−1}. So it remains to prove the claim if d_{h} = d_{h−1}+1. Let π = π_{1}^{P[1..h−1]}. Then, by Proposition 2.6, d_{π} = d_{h−π} = d_{h−1}, and by the inductive hypothesis,

2^{d_{h}} − 1 = 2^{d_{π}} + 2^{d_{h−π}} − 1 ≤ ∑_{l=1}^{π} |Σ_{l}^{P}| + ∑_{l=1}^{h−π} |Σ_{l}^{P}| + 1 ≤ ∑_{l=1}^{h} |Σ_{l}^{P}|. □

Lemma 2.12 Let d_{h} = max {|Σ_{l}^{P}| | l = 1, …, h}. Then, for g ≥ h,

|Σ_{g}^{P}| ≤ d_{h} + ⌊log_{2} \frac{2g}{h + 1}⌋.

Proof. We prove by induction on g, for g ≥ h ≥ 1, that,

d_{g} ≤ d_{h} + ⌊log_{2} \frac{2g}{h + 1}⌋.

By Proposition 2.6, d_{g} ≤ d_{g−1} + 1. It suffices to prove the claim above only for those indices g > h, such that d_{g} = d_{g−1} + 1. Let g_{1}, g_{2}, …, be the sequence of these indices. The basis of the induction for g_{1} clearly holds since:

d_{g_{1}} = d_{h} + 1 ≤ d_{h} + ⌊log_{2} \frac{2g_{1}}{h + 1}⌋.

Let π = π_{1}^{P[1..g_{i}−1]}. By Proposition 2.6 and by the inductive hypothesis, d_{g_{i}−1} = d_{g_{i−1}} = d_{g_{i}−π}, and thus g_{i} − π ≥ g_{i−1}. But by Proposition 2.6, also π ≥ g_{i−1}. Therefore, g_{i} ≥ 2g_{i−1}, establishing the claim. □

Example. The delay at text position t, |Σ_{t−k_{0}^{t}+1}^{P}|, is the maximal number of comparisons that an algorithm will have to make at this text position. Define the strings Δ_{h}[1..2^{h}] over the alphabet {σ_{0}, …, σ_{h}} as:

Δ_{h}[g] = σ_{max{k | 2^{k} divides g}}.

An equivalent recursive definition is:

Δ_{0} = σ_{0} and
Δ_{h} = Δ_{h−1}[1..2^{h−1}] Δ_{h−1}[1..2^{h−1} − 1] σ_{h}.

These are the only strings for which Lemma 2.11 is satisfied with equality in both parts. They have been used by Hancart [30] and Breslauer and Galil [9] as worst case examples for the proportion between their length 2^{h} and the delay |Σ_{2^{h}}^{Δ_{h}}| = h + 1.

2.2 Static algorithms

We define a subclass of the on-line algorithms that we call static algorithms. These algorithm are restricted enough to be easy to analyze, but still general enough to draw conclusions about the performance of on-line algorithms from their analysis.

Definition 2.13 An on-line prefix-matching algorithm is said to be static if the order according to which the symbols in Σ_{t−k_{0}^{t}+1}^{P} are compared to the text symbol T [t] depends only on t − k_{0}^{t} + 1.

Since in a static algorithm A the order of comparisons depends only on l = t − k_{0}^{t} + 1, it will be defined by the functions:

Λ_{A,l}(h) : {1, …, |Σ_{l}^{P}|} ⟼ Σ_{l}^{P} for l = 1, …, m,

where the algorithm A compares T [t] first to Λ_{A,l}(1), then to Λ_{A,l}(2) and so on. The number of comparisons that algorithm A makes to discover that T [t] = σ, for some symbol σ ∈ Σ_{l}^{P}, is Λ_{A,l}^{−1}(σ). As static algorithms depend on the particular pattern, we shall denote by A(P[1..m]) the static algorithm A for the pattern string P[1..m]. We ommit the pattern from our notation when it is clear from the context what it is.

Example. The Knuth-Morris-Pratt string-matching algorithm compares the symbols in Σ_{l}^{P} = {P[l − π] | π ∈ Π^{P[1..l−1]}}, in increasing order of the periods π, sometimes repeating unnecessary comparisons. We define the static prefixmatching algorithm KMP to proceed in the spirit of the Knuth-Morris-Pratt algorithm, comparing the symbols P[l − π] in increasing order of the periods π, skipping symbols that were already compared. The order of comparisons Λ_{KMP ,l}(h) is defined such that,

π_{first}^{l}(Λ_{KMP ,l}(h)) < π_{first}^{l}(Λ_{KMP ,l}(g))
for l = 1, …, m, and 1 ≤ h < g ≤ |Σ_{l}^{P}|.

2.3 The optimization problem

In this section we describe the method we use to evaluate the performance of static prefix-matching algorithms and define a measure to compare the relative efficiency of algorithms.

Define the cost function Ω_{A}(l) to reflect the number of comparisons that the static algorithm A makes to match the pattern prefix P[1..l]:

Ω_{A}(l) = \{ \begin{matrix}0 & l = 0 \\ Ω_{A}(l − 1) + Λ_{A,l}^{−1}(P[l]) & l = 1, …, m. \end{matrix}

The goal is to bound the number of comparisons made by A by an expression of the form C_{A} × n, for some constant C_{A} that will be determined later. When the algorithm reaches text position t, just before comparing the text symbol T [t], we maintain inductively that the number of comparisons made so far is at most C_{A} × (k_{0}^{t} − 1) + Ω_{A}(t − k_{0}^{t}). This bound obviously holds initially at text position t = 1. However, when the algorithm advances to the next text position the term Ω(t+1−k_{0}^{t+1}) might not account for all the comparisons. We shall bound the excess number of comparisons by C_{A} × (k_{0}^{t+1} − k_{0}^{t}), in order to maintain the inductive claim.

Let l = t − k_{0}^{t} + 1. If the algorithm discovers that T [t] = σ, for σ ∈ Σ_{l}^{P}, then it has made Λ_{A,l}^{−1}(σ) comparisons at this text position. If σ = P[l] and l < m, then by Lemma 2.7, k_{0}^{t+1} = k_{0}^{t}, and the inductive hypothesis still holds as the cost function accounts for these comparisons.

However, if σ ≠ P[l], then by Lemma 2.7, k_{0}^{t+1} = k_{0}^{t} + π_{first}^{l}(σ) and only Ω_{A}(l − π_{first}^{l}(σ)) comparisons will be accounted by the cost function. To maintain the inductive hypothesis, we require that the remaining Ω_{A}(l − 1) + Λ_{A,l}^{−1}(σ) − Ω_{A}(l − π_{first}^{l}(σ)) comparisons are also accounted by imposing the following constraint on C_{A}:

\frac{Ω_{A}(l − 1) + Λ_{A,l}^{−1}(σ) − Ω_{A}(l − π_{first}^{l}(σ))}{π_{first}^{l}(σ)} ≤ C_{A}.  (1)

If the algorithm concludes that T [t] ≠ σ, for all σ ∈ Σ_{l}^{P}, then k_{0}^{t+1} = k_{0}^{t}+l = t + 1 and there are Ω_{A}(l − 1) + |Σ_{l}^{P}| comparisons that will not be accounted by the cost function. To maintain the inductive hypothesis in this case, we make certain that these comparisons are also accounted by requiring that:

\frac{Ω_{A}(l − 1) + |Σ_{l}^{P}|}{l} ≤ C_{A}.  (2)

In addition, if the algorithm discovers that T [t] = P[l] and the end of the pattern is reached, that is l = m, then by Lemma 2.7, k_{0}^{t+1} = k_{0}^{t} + π_{1}^{P} and only Ω_{A}(m − π_{1}^{P}) comparisons will be accounted by the cost function. To maintain the inductive hypothesis we require also that:

\frac{Ω_{A}(m) − Ω_{A}(m − π_{1}^{P})}{π_{1}^{P}} ≤ C_{A}.  (3)

Finally, when the end of the text is reached, that is when t = n + 1, the number of comparisons made is bounded by the inductive hypothesis by C_{A} × (k_{0}^{t} − 1) + Ω_{A}(t − k_{0}^{t}). Since Ω_{A}(h)/h ≤ (Ω_{A}(h − 1) + |Σ_{h}^{P}|)/h ≤ C_{A}, for h = n − k_{0}^{n+1} + 1, by Inequality 2, we get that the number of comparisons made is at most C_{A} × n, establishing the inductive claim.

For any static algorithm A let the characteristic constant C_{A} be the smallest constant satisfying the three inequalities above. Inequality 1 has to be satisfied at pattern positions l = 1, ⋯, m, and for all σ ∈ Σ_{l}^{P} \ {P[l]}; Inequality 2 at pattern positions l = 1, ⋯, m; Inequality 3 does not depend on the pattern position. Note that by the same line of reasoning, an adversary can force a static algorithm A to make at least C_{A} × (n − m) + m comparisons. Thus, as algorithms with smaller characteristic constants make fewer comparisons in the worst case as n grows, the characteristic constant can be used to compare the relative efficiency of static prefix-matching algorithms. The constraints on C_{A} are summarized in the following lemma.

Lemma 2.14 The number of comparisons an algorithm A makes while scanning the text T [1..n] is at most C_{A} × n, where the characteristic constant

C_{A} = max \{ \frac{Ω_{A}(l−1)+Λ_{A,l}^{−1}(σ)−Ω_{A}(l−π_{first}^{l}(σ))}{π_{first}^{l}(σ)} for l = 1, …, m, and σ ∈ Σ_{l}^{P} \ \{P[l]\}; \frac{Ω_{A}(l−1)+|Σ_{l}^{P} |}{l} for l = 1, …, m; \frac{Ω_{A}(m)−Ω_{A}(m−π_{1}^{P})}{π_{1}^{P}} \} .

Notice that C_{A} is always a rational number with denominator between 1 and m. Breslauer, Colussi and Toniolo [7] and Hancart [30] proved that the number of symbol comparisons made by a certain class of on-line prefix-matching algorithms, which include all static algorithms, is at most 2n − 1. We prove next a similar claim about static algorithms using the notation we developed above.

Lemma 2.15 The characteristic constant of any static algorithm A satisfies:

1 ≤ C_{A} ≤ 2.

Proof. Clearly 1 ≤ C_{A}. Recall that Ω_{A}(l) = ∑_{h=1}^{l} Λ_{A,h}^{−1}(P[h]) and that Λ_{A,h}^{−1}(σ) ≤ |Σ_{h}^{P}|, for any σ ∈ Σ_{h}^{P}. Given some σ ∈ Σ_{l}^{P} \ {P[l]}, define

P̂[1..l] = P[1..l − 1] σ. Then |Σ_{l}^{P}| ≤ |ΣP̂ ; l| + 1 and P̂[1..l] has period length π = π_{first}^{l}(σ). By Lemma 2.10, Inequality 1 becomes:

\frac{Ω_{A}(l − 1) + Λ_{A,l}^{−1}(σ) − Ω_{A}(l − π)}{π} ≤ \frac{∑_{h=l−π+1}^{l} |Σ_{h}^{P}|}{π}
≤ \frac{1 + ∑_{h=l−π+1}^{l} |ΣP̂ ; h|}{π} ≤ 2.

By Lemma 2.11, Inequality 2 becomes:

\frac{Ω_{A}(l − 1) + |Σ_{l}^{P}|}{l} ≤ \frac{∑_{h=1}^{l} |Σ_{h}^{P}|}{l} ≤ 2 − \frac{1}{l}.

And by Lemma 2.10, Inequality 3 becomes:

\frac{Ω_{A}(m) − Ω_{A}(m − π_{1}^{P})}{π_{1}^{P}} ≤ \frac{∑_{h=m−π_{1}^{P} +1}^{m} |Σ_{h}^{P}|}{π_{1}^{P}} ≤ 2 − \frac{1}{π_{1}^{P}} . □

In the next sections we address the problem of finding some static prefixmatching algorithm OP T that minimizes the characteristic constant C_{OP T}. Such an algorithm clearly exists as there is only a finite number of static prefixmatching algorithms.

Example. Consider an instance of the prefix-matching problem with the pattern string P[1..m] = ‘a^{α}b^{β}’, for α ≥ 2, β ≥ 1 and m = α + β. If α = 0 or β = 0, then the number of comparisons required is clearly n and if α = 1 and β ≥ 1, then the number of comparisons required is ⌊(2 − 1/m)n⌋ as shown by Breslauer, Colussi and Toniolo [7] and Hancart [30].

Let us try to find an optimal static algorithm OP T that has the smallest possible characteristic constant C_{OP T}. We define two algorithms. The first, which we call algorithm AB (it compares first ‘a’ and then if necessary ‘b’), is defined as:

Λ_{AB,l}(h) = \{ \begin{matrix}‘a’ & h = 1 and 1 ≤ l ≤ m \\ ‘b’ & h = 2 and α < l ≤ m, \end{matrix}

and the second algorithm, which we call algorithm X (identical to algorithm AB up to position α+1 and from there on it compares first ‘b’ and then if necessary ‘a’), is defined as:

Λ_{X ,l}(h) = \{ \begin{matrix}‘a’ & h = 1 and 1 ≤ l ≤ α + 1 \\ ‘b’ & h = 1 and α + 1 < l ≤ m \\ ‘a’ & h = 2 and α + 1 < l ≤ m \\ ‘b’ & h = 2 and l = α + 1. \end{matrix}

It is easy to verify that C_{AB} = 1 + (m − α)/m and that for any algorithm A other than AB and X, C_{A} > C_{X}. If β = 1, then the two algorithms are identical and if β ≥ 2, then C_{X} = (α + 3)/(α + 1). Thus, the optimal static algorithm OP T can be chosen as the algorithm that has the smaller characteristic constant C_{AB} or C_{X}, and C_{OP T} = min {C_{AB}, C_{X} }. Notice that there is a tie C_{AB} = C_{X} only for the patterns ‘a^{α}b’, ‘aabbbb’ and ‘aaabbb’.

In this example we have been able to reduce the number of candidates for an optimal static algorithm from the 2^{β} different algorithms to the two algorithms AB and X. We show that in the general case it suffices to consider only few algorithms as candidates for an optimal algorithm. These algorithms are closely related to the generalized form of algorithm AB that we call algorithm REVERSE.

2.4 The algorithm REVERSE

In this section we define a static prefix-matching algorithm that has some special properties. This algorithm, which we call REVERSE, or REV for short, will be the basis for the optimal static algorithm that is developed in Section 2.5.

The order of comparisons Λ_{REV ,l}(h) in algorithm REV is defined such that,

π_{last}^{l}(Λ_{REV ,l}(h)) > π_{last}^{l}(Λ_{REV ,l}(g)) for l = 1, …, m, and 1 ≤ h < g ≤ |Σ_{l}^{P}|.

More intuitively, if we recall that Σ_{l}^{P} = {P[l − π] | π ∈ Π^{P[1..l−1]}}, then algorithm REV compares the symbols P[l − π] in decreasing order of the periods π, skipping the symbols that were already compared. Notice that algorithm KMP compares the symbols P[l − π] in increasing order of the periods π, exactly the opposite of algorithm REV. See Figure 1.

The main property of algorithm REV that is used later in developing the optimal static algorithm is given in the following lemma.

Lemma 2.16 The cost function of algorithm REV is additive. That is,

Ω_{REV} (l − 1) + Λ_{REV ,l}^{−1}(P[l − π]) = Ω_{REV} (π) + Ω_{REV} (l − π),

for l = 1, …, m, and π ∈ Π^{P[1..l−1]}.

In most places we use this lemma with π = π_{first}^{l}(σ), for some σ ∈ Σ_{l}^{P}

1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
a c a b a c a a a c a b a c a c a c a b a c a a a c a b a c a D
a c a b a c a a a c a b a c a C
a c a b a c a A
a c a B
a C

A

Σ_{32}^{P} = {‘a’, ‘b’, ‘c’, ‘d’}

Figure 1: Algorithm REV compares first ‘a’, then ‘c’, then ‘b’ and last ‘d’. Algorithm KMP compares ‘d’, ‘c’, ‘a’ and ‘b’. Note that these comparison orders are not opposite of each other.

Proof. By Proposition 2.6, Lemma 2.8 and the definition of algorithm REV,

Λ_{REV ,h}(g) = Λ_{REV ,h−π}(g) for h = π + 1, …, l, and g = 1, …, |Σ_{h−π}^{P}|.

If π = 0, then by definition Ω_{REV} (l) = Ω_{REV} (l − 1) + Λ_{REV ,l}^{−1}(P[l]). If π > 0, then we prove by induction on h that Ω_{REV} (h) = Ω_{REV} (π) + Ω_{REV} (h − π), for h = π, …, l − 1. The basis of the induction for h = π clearly holds. Observing that P[h] = P[h − π], for h = π + 1, …, l − 1,

Ω_{REV} (h) = Ω_{REV} (h − 1) + Λ_{REV ,h}^{−1}(P[h])
= Ω_{REV} (π) + Ω_{REV} (h − π − 1) + Λ_{REV ,h−π}^{−1}(P[h − π])
= Ω_{REV} (π) + Ω_{REV} (h − π).

Finally, Λ_{REV ,l}^{−1}(P[l − π]) is defined since P[l − π] ∈ Σ_{l}^{P}, and thus,

Ω_{REV} (l − 1) + Λ_{REV ,l}^{−1}(P[l − π]) =
Ω_{REV} (π) + Ω_{REV} (l − π − 1) + Λ_{REV ,l−π}^{−1}(P[l − π]) =
Ω_{REV} (π) + Ω_{REV} (l − π).

One can also verify that REV is the only algorithm that has this property. □

Intuitively, the last lemma means that in the analysis of algorithm REV, comparisons made at any text position can be charged against the text symbol being compared and the charges do not have to be reassigned later.

The constraints on the characteristic constant in Lemma 2.14 are redundant for algorithm REV.

Lemma 2.17 The characteristic constant C_{REV} is given as,

C_{REV} = max_{l=1,...,m} \{\frac{Ω_{REV} (l)}{l}\} .

It suffices to take the maximum only over those l, such that P[1..l] is unbordered.

Proof. The proof follows from Lemma 2.16. The constraints imposed by Inequality 1 become:

\frac{Ω_{REV} (l − 1) + Λ_{REV ,l}^{−1}(σ) − Ω_{REV} (l − π_{first}^{l}(σ))}{π_{first}^{l}(σ)} = \frac{Ω_{REV} (π_{first}^{l}(σ))}{π_{first}^{l}(σ)}.

The constraints imposed by Inequality 2 satisfy:

\frac{Ω_{REV} (l)}{l} = \frac{Ω_{REV} (l − 1) + Λ_{REV ,l}^{−1}(P[l])}{l} ≤ \frac{Ω_{REV} (l − 1) + |Σ_{l}^{P}|}{l} ≤ C_{REV} .

Taking σ = Λ_{REV ,l}(|Σ_{l}^{P}|), these constraints become:

\frac{Ω_{REV} (l − 1) + |Σ_{l}^{P}|}{l} = \frac{Ω_{REV} (l − 1) + Λ_{REV ,l}^{−1}(σ)}{l}
= \frac{Ω_{REV} (π_{first}^{l}(σ)) + Ω_{REV} (l − π_{first}^{l}(σ))}{l}.

And if π_{first}^{l}(σ) > 0, then,

\frac{Ω_{REV} (π_{first}^{l}(σ)) + Ω_{REV} (l − π_{first}^{l}(σ))}{l} ≤

max \{\frac{Ω_{REV} (π_{first}^{l}(σ))}{π_{first}^{l}(σ))}, \frac{Ω_{REV} (l − π_{first}^{l}(σ))}{l − π_{first}^{l}(σ)}\} .

Similarly to the last inequality, one sees that it suffices to take the maximum only over those l, such that P[1..l] is unbordered. Finally, the constraint imposed by Inequality 3 becomes:

\frac{Ω_{REV} (m) − Ω_{REV} (m − π_{1}^{P})}{π_{1}^{P}} = \frac{Ω_{REV} (π_{1}^{P})}{π_{1}^{P}}. □

Breslauer, Colussi and Toniolo [7] and Hancart [30] described a family of algorithms that make at most ⌊(2 − 1/m)n⌋ symbol comparisons. One can verify that algorithm REV belongs to that family. Using the tools we have developed above we prove this bound directly.

Corollary 2.18 The characteristic constant C_{REV} ≤ 2 − 1/m.

Proof. By Lemma 2.17 and Lemma 2.11,

C_{REV} = max_{l=1,...,m} \{\frac{Ω_{REV} (l)}{l}\} ≤

max_{l=1,...,m} \{\frac{∑_{h=1}^{l} |Σ_{h}^{P}|}{l}\} ≤ max_{l=1,...,m} \{2 − \frac{1}{l}\} = 2 − \frac{1}{m}. □

The next corollary shows that on two letter alphabets the pattern ‘ab^{m−1}’ is the only pattern, up to permuting the symbols ‘a’ and ‘b’, that requires ⌊(2 − 1/m)n⌋ symbol comparisons. Note that for the strings Δ_{h}[1..2^{h}] defined in Section 2.1, C_{REV (Δ_{h})} = 2 − 1/2^{h} similarly to ‘ab^{m−1}’.

Corollary 2.19 If the pattern alphabet contains at most two distinct symbols, then,

C_{REV} = 1 + max_{l=1,...,m} \{\frac{| \{h | 1 < h ≤ l and P[h] ≠ P[1]\} |}{l}\} .

Proof. By the definition of algorithm REV, if the pattern contains only two distinct symbols, then Ω_{REV} (l) = l+| {h | 1 < h ≤ l and P[h] ≠ P[1]} | and the claim follows from Lemma 2.17. □

The following lemma describes the relation between the cost function of algorithm REV on the pattern prefixes and the maximal delay.

Lemma 2.20 Let d_{l} = max {|Σ_{h}^{P}| | h = 1, …, l}. Then,

2^{d_{l}−1} − 1 ≤ Ω_{REV} (l) − l.

Proof. The claim is proved by induction on l, similarly to the proof of Lemma 2.11. The basis of the induction for l = 1 clearly holds. By Proposition 2.6, d_{l} ≤ d_{l−1} + 1. The inductive hypothesis holds if d_{l} = d_{l−1}. So it remains to prove the claim if d_{l} = d_{l−1} + 1. Let π = π_{first}^{l}(Λ_{REV ,l}(|Σ_{l}^{P}| − 1)). Then, by Proposition 2.6 and by Lemma 2.16,

Ω_{REV} (l) = Ω_{REV} (l − 1) + |Σ_{l}^{P}| = Ω_{REV} (π) + Ω_{REV} (l − π) + 1.

By the definition of algorithm REV and by Proposition 2.6, d_{π} = d_{l−π} = d_{l−1}. By the inductive hypothesis,

2^{d_{l}−1} − 1 ≤ Ω_{REV} (π) − π + Ω_{REV} (l − π) − (l − π) + 1 = Ω_{REV} (l) − l. □

2.5 The optimal static algorithm

We define the variants of algorithm REV that we call R:θ, for 2 ≤ θ ≤ m, such that P[θ] ≠ P[1], as:

Λ_{R:θ,l}(h) = \{ \begin{matrix}Λ_{REV ,l}(h) & 1 ≤ l < θ and 1 ≤ h ≤ |Σ_{l}^{P}| \\ Λ_{REV ,θ}(h) & l = θ, 1 ≤ h ≤ |Σ_{θ}^{P}| and \\ & h ∉ \{Λ_{REV ,θ}^{−1}(P [θ]), Λ_{REV ,θ}^{−1}(χ_{θ})\} \\ P[θ] & l = θ and h = Λ_{REV ,θ}^{−1}(χ_{θ}) \\ χ_{θ} & l = θ and h = Λ_{REV ,θ}^{−1}(P[θ]) \\ P[l] & θ < l ≤ m and h = 1 \\ Λ_{REV ,l}(h − 1) & θ < l ≤ m and 2 ≤ h ≤ Λ_{REV ,l}^{−1}(P[l]) \\ Λ_{REV ,l}(h) & θ < l ≤ m and Λ_{REV ,l}^{−1}(P[l]) < h ≤ |Σ_{l}^{P}|, \end{matrix}

where the symbol χ_{θ} ∈ {Λ_{REV ,θ}(h) | h = 1, …, Λ_{REV ,θ}^{−1}(P[θ]) − 1} is defined for algorithm R:θ, such that,

\frac{Ω_{REV} (π_{first}^{θ}(χ_{θ})) + Λ_{REV ,θ}^{−1}(P[θ]) − Λ_{REV ,θ}^{−1}(χ_{θ})}{π_{first}^{θ}(χ_{θ})} ≤

\frac{Ω_{REV} (π_{first}^{θ}(σ)) + Λ_{REV ,θ}^{−1}(P[θ]) − Λ_{REV ,θ}^{−1}(σ)}{π_{first}^{θ}(σ)}

∀σ ∈ {Λ_{REV ,θ}(h) | h = 1, …, Λ_{REV ,θ}^{−1}(P[θ]) − 1} .

The algorithms R:θ are constructed from three parts. The first part is used in positions l = 1, …, θ − 1, and is exactly identical to algorithm REV. The second part is used in position l = θ and is identical to algorithm REV, except that the order in which P[θ] and χ_{θ} are compared is exchanged. In the third part that is used in positions l = θ + 1, …, m, the relative comparison order of the symbols is the same as in algorithm REV, except that P[l] is compared first.

We prove next that the algorithms R:θ defined above are similar enough to algorithm REV to satisfy claims which are closely related to those given in Lemma 2.16 and Lemma 2.17. Unfortunately, in the analysis of the algorithms R:θ, we run across some special cases that require that we slightly change the definition above.

Definition 2.21 Let θ̂ = min {θ | P[θ] ≠ P[1]}. A position θ, such that P[θ] ≠ P[1], is said to be <π, l > malignant if the following conditions hold:

π = π_{1}^{P[1..l−1]};

π < θ ≤ l − π;

P[h] = P[1] for all h = 1, …, θ̂ − 1 and h = θ̂ + 1, …, π; P[l] ∉ {P[1], P[θ̂]}; and

P[l − π] = P[θ̂].

Notice that for a given pattern P[1..m], if θ_{1} is < π_{1}, l_{1} > malignant and θ_{2} is <π_{2}, l_{2} > malignant, then π_{1} = π_{2} and l_{1} = l_{2}.

If θ is <π, l > malignant, then we change the definition of algorithm R:θ at position l, and define Λ_{R:θ,l}(h) = Λ_{KMP ,l}(h), for h = 1, 2, 3. Namely,

Λ_{R:θ,l}(h) = \{ \begin{matrix}P[l] & h = 1 \\ P[θ̂] & h = 2 \\ P[1] & h = 3. \end{matrix}

Lemma 2.22 The cost function of algorithm R:θ satisfies for l = 1, …, m, and π ∈ Π^{P[1..l−1]}:

1. If π < θ and l − π < θ, then

Ω_{R:θ}(l − 1) + Λ_{R:θ,l}^{−1}(P[l − π]) ≤ Ω_{R:θ}(π) + Ω_{R:θ}(l − π),

except if l = θ and P[l − π] = χ_{θ}, where

Ω_{R:θ}(θ − 1) + Λ_{R:θ,θ}^{−1}(χ_{θ}) =
Ω_{R:θ}(π) + Ω_{R:θ}(θ − π) + Λ_{REV ,θ}^{−1}(P[θ]) − Λ_{REV ,θ}^{−1}(χ_{θ}).

2. If π < θ and l − π ≥ θ, then

Ω_{R:θ}(l − 1) + Λ_{R:θ,l}^{−1}(P[l − π]) ≤ Ω_{R:θ}(π) + Ω_{R:θ}(l − π).

3. If π ≥ θ and l − π < θ, then

Ω_{R:θ}(l − 1) + Λ_{R:θ,l}^{−1}(P[l − π]) ≤ Ω_{REV} (θ) + π − θ + Ω_{R:θ}(l − π),

except if θ is <π_{1}^{P[1..l−1]}, l > malignant and P[l − π] = P[1], where

Ω_{R:θ}(l − 1) + Λ_{R:θ,l}^{−1}(P[l − π]) = Ω_{REV} (θ) + π − θ + Ω_{R:θ}(l − π) + 1.

4. If π ≥ θ, and l − π ≥ θ > θ̂, then^{4}

Ω_{R:θ}(l − 1) + Λ_{R:θ,l}^{−1}(P[l − π]) ≤

Ω_{REV} (θ) + (1 + \frac{1}{θ̂})(π − θ) + Ω_{R:θ}(l − π).

4We ommit the inequality for the case θ = θ̂.

Proof. We prove the four inequalities separately. From the definition of algorithm R:θ,

Ω_{R:θ}(l) = Ω_{REV} (l)  for l = 1, …, θ − 1,
Ω_{R:θ}(θ) ≤ Ω_{REV} (θ) − 1,
Ω_{R:θ}(l) = Ω_{R:θ}(θ) + l − θ  for l = θ + 1, …, m.

1. If π = 0, then the claim follows by the definition of the cost function.

If l = θ and P[l − π] = χ_{θ}, then by Lemma 2.16,

Ω_{R:θ}(θ − 1) + Λ_{R:θ,θ}^{−1}(χ_{θ}) =
Ω_{R:θ}(θ − 1) + Λ_{REV ,θ}^{−1}(P[θ]) =
Ω_{R:θ}(π) + Ω_{R:θ}(θ − π) + Λ_{REV ,θ}^{−1}(P[θ]) − Λ_{REV ,θ}^{−1}(χ_{θ}).

Recalling that algorithm R:θ is identical to algorithm REV in positions l = 1, …, θ − 1, and that at position l = θ,

Λ_{R:θ,θ}^{−1}(σ) ≤ Λ_{REV ,θ}^{−1}(σ) for σ ∈ Σ_{θ}^{P} \ {χ_{θ}} ,

the claim follows for l = 1, …, θ, by Lemma 2.16. It remains to prove the claim for θ < l < θ + π. For the positions h = θ, …, l − 1, we prove by induction that:

Ω_{R:θ}(h) ≤ Ω_{R:θ}(π) + Ω_{R:θ}(h − π) − 1.

The basis of the induction for h = θ holds since Ω_{R:θ}(θ) ≤ Ω_{REV} (θ) − 1, and the inductive step holds since:

Ω_{R:θ}(h) = Ω_{R:θ}(h − 1) + 1 ≤ Ω_{R:θ}(π) + Ω_{R:θ}(h − π) − 1.

Finally, since l − π < θ and Λ_{R:θ,l}^{−1}(P [l − π]) ≤ Λ_{REV ,l−π}^{−1}(P [l − π]) + 1, by the inductive hypothesis we get that,

Ω_{R:θ}(l − 1) + Λ_{R:θ,l}^{−1}(P[l − π]) ≤
Ω_{R:θ}(l − 1) + Λ_{REV ,l−π}^{−1}(P[l − π]) + 1 ≤
Ω_{R:θ}(π) + Ω_{R:θ}(l − π − 1) + Λ_{REV ,l−π}^{−1}(P[l − π]) =
Ω_{R:θ}(π) + Ω_{R:θ}(l − π).

2. If π = 0, then the claim follows by the definition of the cost function.

The claim we wish to prove is equivalent to showing that:

π + Λ_{R:θ,l}^{−1}(P[l − π]) − 1 ≤ Ω_{R:θ}(π).

Let d_{g} = max {|Σ_{h}^{P}| | h = 1, …, g}. Since π ∈ Π^{P[1..l−1]}, by Proposition 2.6,

Λ_{R:θ,l}^{−1}(P[l − π]) − 1 ≤ d_{l} − 1 ≤ d_{π}.

Therefore, if d_{π} ≥ 3, then by Lemma 2.20,

π + Λ_{R:θ,l}^{−1}(P[l − π]) − 1 ≤ π + d_{π} ≤ π + 2^{d_{π}−1} − 1 ≤ Ω_{R:θ}(π). It remains to prove the claim for d_{π} = 2. In this case, the inequality

π + Λ_{R:θ,l}^{−1}(P[l − π]) − 1 ≤ Ω_{R:θ}(π),

might be violated if and only if Ω_{REV} (π) = π + 1 and Λ_{R:θ,l}^{−1}(P[l − π]) = d_{l} = 3, which is equivalent to saying that θ is < π, l > malignant. But by the (modified) definition of algorithm R:θ, Λ_{R:θ,l}(3) = P[1], and thus P[l − π] = P[1], in contradiction to θ being <π, l > malignant.

3. The claim we wish to prove is equivalent to showing that:

Ω_{R:θ}(θ) + l − π − 1 + Λ_{R:θ,l}^{−1}(P[l − π]) ≤ Ω_{REV} (θ) + Ω_{R:θ}(l − π) If θ is not <π_{1}^{P[1..l−1]}, l > malignant or if P[l − π] ≠ P[1], then since l > θ:

Λ_{R:θ,l}^{−1}(P[l − π]) ≤ Λ_{REV ,l−π}^{−1}(P[l − π]) + 1.

So it suffices to show that:

Ω_{R:θ}(θ) + l − π + Λ_{REV ,l−π}^{−1}(P[l − π]) ≤ Ω_{REV} (θ) + Ω_{R:θ}(l − π). But, by the definition of algorithm R:θ, Ω_{R:θ}(θ) ≤ Ω_{REV} (θ) − 1, and,

l − π + Λ_{REV ,l−π}^{−1}(P[l − π]) ≤ Ω_{R:θ}(l − π) + 1,

establishing the claim. If θ is <π_{1}^{P[1..l−1]}, l > malignant and P[l − π] = P[1], then

Λ_{R:θ,l}^{−1}(P[l − π]) = Λ_{REV ,l−π}^{−1}(P[l − π]) + 2 = 3,

and the claim follows.

4. We first prove that:

Ω_{R:θ}(l − 1) + Λ_{R:θ,l}^{−1}(P[l − π]) ≤

Ω_{REV} (θ) + π − θ + Ω_{R:θ}(l − π) + ⌊log_{2} \frac{2π}{θ + θ̂}⌋,

which is equivalent to showing that:

Λ_{R:θ,l}^{−1}(P[l − π]) − 1 ≤ Ω_{REV} (θ) − θ + ⌊log_{2} \frac{2π}{θ + θ̂}⌋.

Let d_{g} = max {|Σ_{h}^{P}| | h = 1, …, g}. Since π ∈ Π^{P[1..l−1]}, by Proposition 2.6,

Λ_{R:θ,l}^{−1}(P[l − π]) − 1 ≤ d_{l} − 1 ≤ d_{π}.

If Ω_{REV} (θ) − θ ≥ 4 or if Ω_{REV} (θ) − θ = 3 and d_{θ} = 2, then by Lemma 2.12 and by Lemma 2.20,

d_{π} ≤ d_{θ} + ⌊log_{2} \frac{π}{θ + 1}⌋ + 1 ≤ Ω_{REV} (θ) − θ + ⌊log_{2} \frac{2π}{θ + θ̂}⌋.

If Ω_{REV} (θ) − θ = d_{θ} = 3, then d_{θ} = d_{θ−1} + 1, and by Lemma 2.12,

d_{π} ≤ d_{θ} + ⌊log_{2} \frac{π}{θ} ⌋ ≤ Ω_{REV} (θ) − θ + ⌊log_{2} \frac{2π}{θ + θ̂}⌋.

Since θ > θ̂, the only remaining possibility is that Ω_{REV} (θ) − θ = d_{θ} = 2. Then, by a close inspection of the possible pattern prefixes P[1..θ + θ̂], d_{θ+θ̂−1} = 2, and by Lemma 2.12,

d_{π} ≤ Ω_{REV} (θ) − θ + ⌊log_{2} \frac{2π}{θ + θ̂}⌋.

But,

⌊log_{2} \frac{2π}{θ + θ̂}⌋ ≤ \frac{π − θ}{θ̂} ,

establishing that

Ω_{R:θ}(l − 1) + Λ_{R:θ,l}^{−1}(P[l − π]) ≤

Ω_{REV} (θ) + (1 + \frac{1}{θ̂})(π − θ) + Ω_{R:θ}(l − π). □

The constraints in Lemma 2.14 are redundant also for the algorithms R:θ.

Lemma 2.23 The characteristic constants of the algorithms R:θ are given as:

C_{R:θ} = max \{C_{REV} (θ − 1), \frac{Ω_{REV} (π_{first}^{θ}(χ_{θ})) + Λ_{REV ,θ}^{−1}(P[θ]) − Λ_{REV ,θ}^{−1}(χ_{θ})}{π_{first}^{θ}(χ_{θ})}\} .

Proof. The proof is almost identical to the proof of Lemma 2.17, using Lemma 2.22 instead of Lemma 2.16. If θ = θ̂, then C_{R:θ} = 2, by Inequality 1 and Lemma 2.15. The constraints arising from Inequalities 1 and 2, imply that:

C_{R:θ} ≥ max \{C_{REV} (θ − 1), \frac{Ω_{REV} (π_{first}^{θ}(χ_{θ})) + Λ_{REV ,θ}^{−1}(P[θ]) − Λ_{REV ,θ}^{−1}(χ_{θ})}{π_{first}^{θ}(χ_{θ})}\} .

The other constraints are dominated by those above, since for l ≥ θ > θ̂,

\frac{Ω_{R:θ}(l)}{l} ≤ \frac{Ω_{REV} (θ) + l − θ}{l} ≤ \frac{Ω_{REV} (θ)}{θ},

and since,

\frac{Ω_{REV} (θ) + (1 + \frac{1}{θ̂})(l − θ)}{l} ≤ max \{\frac{Ω_{REV} (θ)}{θ}, \frac{Ω_{REV} (θ̂)}{θ̂}\} .

But,

\frac{Ω_{REV} (θ)}{θ} ≤

max \{\frac{Ω_{REV} (π_{first}^{θ}(χ_{θ})) + Λ_{REV ,θ}^{−1}(P[θ]) − Λ_{REV ,θ}^{−1}(χ_{θ})}{π_{first}^{θ}(χ_{θ})}, \frac{Ω_{REV} (θ − π_{first}^{θ}(χ_{θ}))}{θ − π_{first}^{θ}(χ_{θ})}\} .

If θ is < π_{1}^{P[1..l−1]}, l > malignant and P[l − π] = P[1], then the remaining constraint araising from case 3 in Lemma 2.22 is also dominated by the constraints above, since by Lemma 2.16,

\frac{Ω_{REV} (θ) + π − θ + 1}{π} ≤

max \{\frac{Ω_{REV} (π_{first}^{θ}(χ_{θ})) + Λ_{REV ,θ}^{−1}(P[θ]) − Λ_{REV ,θ}^{−1}(χ_{θ})}{π_{first}^{θ}(χ_{θ})}, 1 + \frac{1}{π − π_{first}^{θ}(χ_{θ})}\} ,

establishing the claim. □

Given any static prefix-matching algorithm A, define

ρ(A) = min {l | 1 ≤ l ≤ m and Λ_{A,l}^{−1}(P[l]) < Λ_{REV ,l}^{−1}(P [l])} .

If ρ(A) is defined above, then P[ρ(A)] ≠ P[1], and algorithm R:ρ(A) is also defined.

Theorem 2.24 Given any static prefix-matching algorithm A, then either

C_{R:ρ(A)} ≤ C_{A} or C_{REV} ≤ C_{A}.

Proof. If ρ(A) is not defined, then Ω_{REV} (l) ≤ Ω_{A}(l), for l = 1, …, m, and by Inequality 2,

C_{A} ≥ max_{l=1,...,m} \{\frac{Ω_{A}(l)}{l}\} ≥ max_{l=1,...,m} \{\frac{Ω_{REV} (l)}{l}\} = C_{REV} .

Assume that ρ(A) is defined. Then, Ω_{REV} (l) ≤ Ω_{A}(l), for l = 1, …, ρ(A) − 1, and by Inequality 2,

C_{A} ≥ max_{l=1,...,ρ(A)−1} \{\frac{Ω_{REV} (l)}{l}\} .

Since Λ_{A,ρ(A)}^{−1}(P[ρ(A)]) < Λ_{REV ,ρ(A)}^{−1}(P[ρ(A)]), there must be at least one symbol

χ ∈ {Λ_{REV ,ρ(A)}(h) | h = 1, …, Λ_{REV ,ρ(A)}^{−1}(P[ρ(A)]) − 1} ,

such that Λ_{A,ρ(A)}^{−1}(χ) ≥ Λ_{REV ,ρ(A)}^{−1}(P[ρ(A)]). But then, by Inequality 1,

\frac{Ω_{REV} (π_{first}^{ρ(A)}(χ_{ρ(A)})) + Λ_{REV ,ρ(A)}^{−1}(P[ρ(A)]) − Λ_{REV ,ρ(A)}^{−1}(χ_{ρ(A)})}{π_{first}^{ρ(A)}(χ_{ρ(A)})} ≤

\frac{Ω_{REV} (π_{first}^{ρ(A)}(χ)) + Λ_{REV ,ρ(A)}^{−1}(P[ρ(A)]) − Λ_{REV ,ρ(A)}^{−1}(χ)}{π_{first}^{ρ(A)}(χ)} ≤

\frac{Ω_{A}(ρ(A) − 1) + Λ_{A,ρ(A)}^{−1}(χ) − Ω_{A}(ρ(A) − π_{first}^{ρ(A)}(χ))}{π_{first}^{ρ(A)}(χ)} ≤ C_{A},

and by Lemma 2.23, C_{A} ≥ C_{R:ρ(A)}. □

By the last theorem one can find an optimal static algorithm among the m or fewer algorithms R:θ, 2 ≤ θ ≤ m, and algorithm REV. Thus, we define the static algorithm REVERSE OPTIMAL, or RO for short, to be the algorithm among algorithms R:θ and REV with the smallest characteristic constant. We define C_{on−line}^{P[1..m]} = C_{RO(P[1..m])}.

Example. Consider the pattern P[1..10] = ‘abaacabacb’. Then, C_{R:2} = 2, C_{R:5} = \frac{5}{3}, C_{R:7} = \frac{5}{3}, C_{R:9} = \frac{12}{7}, C_{R:10} = \frac{16}{9}, and C_{REV} = \frac{17}{10}. Thus, algorithm RO can be either algorithm R:5 or algorithm R:7.

Remark. If the pattern contains only two distinct symbols, then the analysis above is substantially simplified. The simplified proof for this special case, which captures the main ideas, was sketched in the conference extended abstract [8].

2.6 The lower bound

By the observations made before, static algorithms must make at least C_{on−line}^{P[1..m]}× (n − m) + m symbol comparisons. We prove that the same lower bound holds for any on-line algorithm.

Theorem 2.25 Any on-line prefix-matching algorithm must make at least C_{on−line}^{P[1..m]} × (n − m) + m symbol comparisons.

Proof. The proof is similar to the proof of Theorem 2.24. Recall that C_{on−line}^{P[1..m]} = C_{RO}. We prove by induction that the number of symbol comparisons made by any on-line algorithm, when reaching text position t, just before comparing the text symbol T [t], is at least

C_{RO} × (k_{0}^{t} − 1) + Ω_{REV} (t − k_{0}^{t}),

and that Ω_{REV} (l)/l < C_{RO}, for l = 1, …, t − k_{0}^{t}. The inductive base clearly holds for t = 1. We assume that the inductive hypothesis holds at text position t and show how an adversary can force the inductive hypothesis to hold at text position t + 1.

Let l = t − k_{0}^{t} + 1. Observe that by answering comparisons made by the on-line algorithm as unequal, an adversary will eventually force the algorithm to compare T [t] to all symbols in Σ_{l}^{P}. If (Ω_{REV} (l − 1) + |Σ_{l}^{P}|)/l ≥ C_{RO}, then the adversary forces the algorithm to compare T [t] to all symbols in Σ_{l}^{P}, giving unequal answers, resulting in k_{0}^{t+1} = t+1, and maintaining the inductive hypothesis.

Otherwise, let Λ^{−1}(σ) be the number of comparisons that the on-line algorithm makes at text position t until comparing σ ∈ Σ_{l}^{P} to T [t]. Notice that Λ^{−1}(σ) is not known to the adversary in advance. Then, if Λ^{−1}(P[l]) ≥ Λ_{REV ,l}^{−1}(P[l]), the adversary sets T [t] = P[l] and the inductive hypothesis is maintained by the definitions. Observe that by Lemma 2.17, this situation might not continue until l = m, since C_{RO} ≤ C_{REV}.

If Λ^{−1}(P[l]) < Λ_{REV ,l}^{−1}(P[l]), then the adversary answers that T [t] ≠ P[l] and the algorithm must continue comparing the symbols in Σ_{l}^{P}. There must be at least one symbol χ ∈ {Λ_{REV ,l}(h) | h = 1, …, Λ_{REV ,l}^{−1}(P[l]) − 1}, such that

Λ^{−1}(χ) ≥ Λ_{REV ,l}^{−1}(P[l]). The adversary sets T [t] = χ. Then, by the definition of the algorithms RO and R:θ, C_{RO} ≤ C_{R:l}, and by the inductive hypothesis and by Lemma 2.23, we get that k_{0}^{t+1} = k_{0}^{t} + π_{first}^{l}(χ), and

\frac{Ω_{REV} (l − 1) + Λ^{−1}(χ) − Ω_{REV} (l − π_{first}^{l}(χ))}{π_{first}^{l}(χ)} ≥

\frac{Ω_{REV} (π_{first}^{l}(χ)) + Λ_{REV ,l}^{−1}(P[l]) − Λ_{REV ,l}^{−1}(χ)}{π_{first}^{l}(χ)} ≥ C_{R:l},

establishing the inductive claim.

Once the inductive claim is established, recalling that Ω_{REV} (l) ≥ l and that C_{RO} ≥ 1, we get that the number of comparisons made by the algorithm is at least

C_{RO} × (k_{0}^{t} − 1) + Ω_{REV} (t − k_{0}^{t}) ≥ C_{RO} × (n − m) + m. □

Remark. The lower bound given above could be expressed in a tighter form. However, our technique will always leave some gap between the lower and upper bounds due to boundary situations. Observe that as the end of the text is reached, there is no need to consider the whole pattern, but only its prefix that can still occur within the text. Thus, it makes sense to use at text position t, the static algorithm RO(P[1.. min(m, n − k_{0}^{t} + 1)]), that depends on t. Notice that this algorithm is either some fixed algorithm R:θ, or algorithm REV, and therefore, it might not be static over the whole text. In addition, since C_{RO(P[1..l])} is non-decreasing in l, it also makes sense, in many cases, to break ties between the characteristic constants C_{R:θ} and C_{REV}, in favour of using the algorithm R:θ with smaller value of θ.

Nevertheless, in some cases, optimal static algorithms do not give the best on-line solution. For example, consider the pattern P[1..4] = ‘abac’ and a text of length 4. The optimal static algorithm can be forced by an adversary to make 7 comparisons, while an algorithm that will compare the text symbol T [2], first to ‘b’ and then to ‘a’, a comparison order that can never be followed by an optimal static algorithm, will make at most 6 comparisons.

2.7 Infinite length patterns

The prefix-matching problem can be analogously defined for infinite length patterns P[1..∞] by observing that the lengths of the pattern prefixes that occur in the text can not exceed the text length. We define,

C_{on−line}^{P[1..∞]} = lim_{m→∞} lim_{n→∞} \frac{c_{on−line}^{P[1..m]}(n)}{n} = lim_{m→∞} C_{on−line}^{P[1..m]}.

The constant C_{on−line}^{P[1..∞]} is always well defined since C_{on−line}^{P[1..m]} is non-decreasing in m and bounded above by Lemma 2.15. We prove next that the characteristic constants of infinite length patterns cover the whole real interval [1..2].

Lemma 2.26 Given any real constant α, 1 ≤ α ≤ 2, there exists an infinite length pattern P[1..∞], such that, C_{on−line}^{P[1..∞]} = α.

Proof. The proof constructs for any given α, 1 ≤ α ≤ 2, an infinite length pattern P[1..∞] over the alphabet {‘a’, ‘b’}, whose characteristic constant C_{on−line}^{P[1..∞]} is equal to α. The pattern is defined inductively by setting P[1] = ‘a’, and, for l = 2, 3, …,

P[l] = \{ \begin{matrix}‘b’ & if \frac{Ω_{REV (P[1..l−1])}(l−1)+2}{l} ≤ α \\ ‘a’ & otherwise. \end{matrix}

By Corollary 2.19, C_{REV (P[1..l])} ≤ α. We prove that C_{R:l} ≥ α, for all l, and that,

C_{on−line}^{P[1..∞]} = lim_{l→∞} C_{REV (P[1..l])} = α.

If P[1..∞] contains finitely many symbols ‘a’, then lim_{l→∞} C_{REV (P[1..l])} = α = 2, by Corollary 2.19. If P[l] = ‘b’, then algorithm R:l is defined. Let π = π_{first}^{l}(‘a’). If π + 1 < l, then P[π + 1] = ‘a’, and by Lemma 2.23,

C_{R:l} ≥ \frac{Ω_{REV} (π) + 1}{π} ≥ \frac{Ω_{REV} (π + 1) + 1}{π + 1} ≥ α.

If π + 1 = l, then let h = max {g | 1 ≤ g < l and P[g] = ‘a’}. By Lemma 2.23 and by the definition of P[h] = ‘a’,

C_{R:l} ≥ \frac{Ω_{REV} (π) + 1}{π} ≥ \frac{Ω_{REV} (h) + 1}{h} ≥ α.

Assume by contradiction that there exists an ϵ > 0, such that α−C_{REV (P[1..l])} ≥ ϵ, for all l. Let h be a position of P[1..∞], such that h ≥ 1/ϵ and P[h] = ‘a’. Then, by Corollary 2.19,

\frac{Ω_{REV} (h − 1) + 2}{h} = \frac{Ω_{REV} (h)}{h} + \frac{1}{h} ≤ C_{REV (P[1..h])} + ϵ ≤ α,

in contradiction to the definition of P[h] = ‘a’. □

3 Off-line prefix-matching

The analysis of off-line prefix-matching algorithms is complicated by the greater freedom they possess. Breslauer, Colussi and Toniolo [7] showed that for the pattern ‘ab^{m−1}’ off-line algorithms are not better than on-line algorithms. Nevertheless, off-line algorithms can be superior to on-line algorithms in certain cases as we show next.

Lemma 3.1 There exists pattern strings for which off-line prefix-matching algorithms require fewer symbol comparisons than on-line algorithms.

Proof. Consider the pattern P[1..7] = ‘aaaabbb’. This pattern belongs to the family of patterns discussed in the example in Section 2.3. It is not difficult to verify that C_{on−line}^{‘aaaabbb’} = \frac{7}{5} and thus, on-line prefix-matching algorithms require about \frac{7}{5}n symbol comparisons. We show next that there exists an off-line prefix-matching algorithm that requires only about \frac{4}{3}n symbol comparisons. (The lower bound proof of Breslauer, Colussi and Toniolo [7] can be applied almost unchanged to this pattern, showing that this bound is tight for off-line algorithms, up to a small additive constant.)

The off-line algorithm relies on the fact that the optimal static algorithm for the pattern P[1..7] is R:6, while the optimal static algorithm for the pattern P[1..6] is REV. The off-line algorithm examines a single text position ahead to help it decide whether to proceed as algorithm R:6 or as algorithm REV.

Observe that the comparison order functions Λ_{R:6,l} and Λ_{REV ,l} are identical for l = 1, …, 5. The off-line algorithm proceeds in the same manner as these on-line algorithms as long as t − k_{0}^{t} + 1 ≤ 5. When t − k_{0}^{t} + 1 = 6, the off-line algorithm compares the text symbol T [k_{0}^{t} + 9] to ‘a’. If T [k_{0}^{t} + 9] = ‘a’, then the algorithm proceeds as algorithm R:6, and otherwise as algorithm REV. In both cases, the off-line algorithm will avoid comparing T [k_{0}^{t} + 9] to ‘a’ again. It is straightforward to verify that this off-line algorithm makes at most \frac{4}{3}n symbol comparisons. □

4 The self-prefix problem

In this section we consider the special case of the prefix-matching problem where the pattern and the text are the same string and all symbol comparisons are accounted^{5}. This problem, which we call the self-prefix problem, is the essence of the pattern preprocessing step of the prefix-matching algorithm. Throughout this section we assume that the input to the self-prefix problem is the pattern string P[1..m].

Proposition 4.1 The periods lengths π_{1}^{P[1..l]}, for l = 1, …, m, can be computed from the output of the self-prefix problem Φ[1..m], and vice versa, in O(m) time without making any extra symbol comparisons.

Observe that the Knuth-Morris-Pratt string-matching algorithm computes in its pattern preprocessing step, the so called failure function, f(l) = l−π_{1}^{P[1..l]}, which is essentially the same as the prefix period lengths π_{1}^{P[1..l]}, for l = 1, …, m.

Clearly, if the text is identical to the pattern, then there must be an occurrence of the pattern starting at the first position of the text. Since we do not wish to spend any labour to discover this trivial fact, we formally define the text T [1..m − 1] to be P[2..m]. Thus, in the self-prefix problem we always have that:

5In contrast to the unaccounted pattern preprocessing step in the discussion about on-line prefix-matching algorithms.

k_{h}^{t} = π_{h+1}^{P[1..t]} for t = 1, …, m − 1 and h = 0, …, |Π^{P[1..t]}| − 2.

On-line self-prefix algorithms, which are defined analogously to on-line prefixmatching algorithms, always compare the symbol T [t] = P[t+1], t = 1, …, m− 1, to the symbols σ ∈ Σ_{t−π_{1}^{P[1..t]}+1}^{P}.

The self-prefix problem can be solved by any on-line static prefix-matching algorithm A. Denote by ω_{A}(l), the number of symbol comparisons made by the static prefix-matching algorithm A, when used to solve the self-prefix problem on the input prefix P[1..l]. Then,

ω_{A}(l) = \begin{cases}0 & l = 1 \\ ω_{A}(l − 1) + Λ_{A,l−π_{1}^{P[1..l−1]}}(P[l]) & l = 2, …, m and P[l] ∈ Σ_{l−π_{1}^{P[1..l−1]}}^{P} \\ ω_{A}(l − 1) + |Σ_{l−π_{1}^{P[1..l−1]}}^{P}| & l = 2, …, m and P[l] ∉ Σ_{l−π_{1}^{P[1..l−1]}}^{P}. \end{cases}

Let μ(P[1..l]) be the number of non-empty unbordered prefixes of the string P[1..l]. We first prove some upper bounds on the number of symbol comparisons made by the self-prefix algorithm REV.

Lemma 4.2 The number of symbol comparisons made by the self-prefix algorithm REV satisfies:

ω_{REV} (m) = Ω_{REV} (m) − μ(P[1..m]).

Proof. We prove by induction on l = 1, …, m, that:

ω_{REV} (l) = Ω_{REV} (l) − μ(P[1..l]).

The base of the induction for l = 1 clearly holds. Assume that the inductive hypothesis holds for l − 1. If P[l] ∈ Σ_{l−π_{1}^{P[1..l−1]}}^{P}, then P [1..l] is bordered and by

the definition of algorithm REV, by Proposition 2.6 and by Lemma 2.8,

ω_{REV} (l) = Ω_{REV} (l − 1) + Λ_{REV ,l−π_{1}^{P[1..l−1]}}(P[l]) − μ(P[1..l − 1])
= Ω_{REV} (l) − μ(P[1..l]).

Otherwise, P [1..l] is unbordered and,

ω_{REV} (l) = Ω_{REV} (l − 1) + |Σ_{l−π_{1}^{P[1..l−1]}}^{P}| − μ(P[1..l − 1])
= Ω_{REV} (l − 1) + |Σ_{l}^{P}| − μ(P[1..l])
= Ω_{REV} (l) − μ(P[1..l]). □

The pattern preprocessing of the Knuth-Morris-Pratt [32] string-matching algorithm makes in some cases as many as 2m − 4 symbol comparisons. We show next that the self-prefix algorithm REV is more efficient.

Corollary 4.3 The number of symbol comparisons made by the self-prefix algorithm REV is at most 2m − ⌈log_{2} m⌉ − 2.

Proof. Let P[1..u_{1}], P[1..u_{2}], …, be all the unbordered prefixes of P[1..m], such that 1 = u_{1} < ⋯ < u_{h}, and u_{h} = m whether P[1..m] is bordered or not. Then, ω_{REV} (u_{1}) = 0, and by Lemma 2.17 and Corollary 2.18, for g = 2, …, h,

ω_{REV} (u_{g}) ≤ ω_{REV} (u_{g−1}) + ⌊C_{REV (P[1..u_{g−1}])} × (u_{g} − u_{g−1})⌋
≤ ω_{REV} (u_{g−1}) + 2(u_{g} − u_{g−1}) − ⌈\frac{u_{g}}{u_{g−1}} − 1⌉.

Expanding the last inequality,

ω_{REV} (m) ≤ 2m − 2 − ∑_{g=2}^{h}⌈\frac{u_{g}}{u_{g−1}} − 1⌉ ≤ 2m − ⌈log_{2} m⌉ − 2. □

Notice that the last bound is tight for infinitely many strings, since the selfprefix algorithm REV will make 2m − log_{2} m − 2 symbol comparisons when presented with the input strings P[1..m] = Δ_{h}[1..2^{h}] that are defined in Section 2.1.

As long that the input string P[1..m] contains at most two distinct symbols, algorithm REV achieves better bounds. The next upper bound is tight with respect to the lower bound given by Breslauer, Colussi and Toniolo [7] for on-line self-prefix algorithms. Notice that we do not assume a priori that there are at most two distinct symbols in P[1..m] since in that case inequality to one alphabet symbol would imply equality to the other and m − 1 symbol comparisons would suffice.

Corollary 4.4 The number of symbol comparisons made by the self-prefix algorithm REV as long that the input string P[1..m] contains at most two distinct symbols is at most 2m − ⌈2\sqrt{m}⌉.

Proof. By Lemma 2.17 and Corollary 2.18,

C_{REV (P[1..m])} ≤ 2 − \frac{1}{μ(P[1..m])}.

But, by Lemma 4.2,

ω_{REV} (m) ≤ ⌊C_{REV (P[1..m])} × m⌋ − μ(P[1..m])
≤ 2m − ⌈\frac{m}{μ(P[1..m])}⌉ − μ(P[1..m])
≤ 2m − ⌈2\sqrt{m}⌉. □

We are now ready to prove the main upper and lower bounds for on-line self-prefix algorithms.

Theorem 4.5 There exists an on-line self-prefix algorithm that makes at most 2m − ⌈\sqrt{2m}⌉ symbol comparisons. This is roughly tight for on-line self-prefix algorithms.

Proof. We describe an on-line self-prefix algorithm that makes about 2m − ⌈\sqrt{2m}⌉ symbol comparisons and prove that this is roughly the best possible for on-line algorithms (up to an additive constant 2). Let ω(h) denote the number of symbol comparisons made by the on-line self-prefix algorithm on the pattern prefix P[1..h]. The self-prefix algorithm starts making comparisons in the same order as the static self-prefix algorithm REV until it reaches the smallest position ζ, such that C_{REV (P[1..ζ])} > C_{R:l_{ζ}}, where algorithm R:l_{ζ} is the algorithm with the smallest characteristic constant for 2 ≤ l_{ζ} ≤ ζ. From position ζ + 1 until the end of the string P[1..m] the algorithm follows the comparison order of the static self-prefix algorithm R:l_{ζ}. If no such position ζ is ever reached, then by Lemma 4.2,

ω(m) = ω_{REV} (m) ≤ ⌊C_{REV} × m⌋ − μ(P[1..m]).

Otherwise, P[1..ζ] must be unbordered by Lemma 2.17 and Lemma 2.23. By the minimality of ζ, C_{REV (P[1..ζ])} = Ω_{REV} (ζ)/ζ and C_{REV (P[1..ζ])} ×ζ = ⌊C_{R:l_{ζ}} × ζ⌋ + 1. Therefore, by Lemma 4.2,

ω(m) ≤ ω_{REV} (ζ) + ⌊C_{R:l_{ζ}} × (m − ζ)⌋
= Ω_{REV} (ζ) + ⌊C_{R:l_{ζ}} × (m − ζ)⌋ − μ(P[1..ζ])
= ⌊C_{REV (P[1..ζ])} × ζ⌋ + ⌊C_{R:l_{ζ}} × (m − ζ)⌋ − μ(P[1..ζ])
≤ ⌊C_{R:l_{ζ}} × m⌋ − μ(P[1..ζ]) + 1.

The αβ decomposition of P[1..m] is defined as follows: α_{1} is the number of symbols at the beginning of P[1..m] that are equal to P[1]; β_{1} is the number of following symbols that are different from P[1]; α_{2} is the number of following symbols that is equal to P[1]; β_{2} is the number of following symbols that are different from P[1]; and so on. Let δ_{h} = ∑_{g=1}^{h}(α_{g} +β_{g}) and let b be the smallest integer such that δ_{b} = m. E.g. the αβ decomposition of P[1..9] = ‘aabbcacca’ is α_{1} = 2, β_{1} = 3, α_{2} = 1, β_{2} = 2, α_{3} = 1 and β_{3} = 0; δ_{1} = 5, δ_{2} = 8, δ_{3} = 9 and b = 3.

The proof distinguishes between the following cases.

1. If β_{2} = 0, then the algorithm follows the comparison order of algorithm REV. The number of symbol comparison made is at most m − 1. From now on assume that β_{2} ≥ 1.

2. If α_{1} ≥ 2, notice that if β_{1} ≥ 2, then algorithm R:α_{1}+2 is defined and C_{R:α_{1}+2} ≤ \frac{5}{3}; otherwise, if β_{1} = 1, then C_{R:δ_{1}+α_{2}+1} ≤ \frac{5}{3}. If the on-line self-prefix algorithm does not reach the position ζ defined above, then C_{REV} ≤ \frac{5}{3}. Since μ(P[1..m]) ≥ 2,

ω(m) = ω_{REV} (m) ≤

⌊C_{REV} × m⌋ − μ(P[1..m]) ≤ ⌊\frac{5}{3}m⌋ − 2 ≤ 2m − ⌈\sqrt{2m}⌉.

If the position ζ defined above is reached, then C_{R:l_{ζ}} ≤ \frac{5}{3} and μ(P[1..ζ]) ≥ 3. But then,

ω(m) ≤ ⌊C_{R:l_{ζ}} × m⌋ − μ(P[1..m]) + 1 ≤ ⌊\frac{5}{3}m⌋ − 2 ≤ 2m − ⌈\sqrt{2m}⌉.

3. The most complicated case is where α_{1} = 1. If α_{2} = 1 and P[δ_{1}+2] = P[2], or if α_{2} ≥ 2, then C_{R:δ_{1}+α_{2}+1} ≤ 2 − 1/(δ_{1} + 1). If the algorithm does not reach the position ζ defined above, then C_{REV} ≤ 2 − 1/(δ_{1} + 1) and μ(P[1..m]) ≥ δ_{1}. Thus,

ω(m) = ω_{REV} (m) ≤ ⌊C_{REV} × m⌋ − μ(P[1..m])
≤ 2m − ⌈\frac{m}{δ_{1} + 1}⌉ − δ_{1}
≤ 2m − ⌈\sqrt{2m}⌉.

If the algorithm reaches the position ζ defined above, then C_{R:l_{ζ}} ≤ 2 − 1/(δ_{1} + 1) and μ(P[1..ζ]) ≥ δ_{1} + 1. Hence,

ω(m) ≤ ⌊C_{R:l_{ζ}} × m⌋ − μ(P[1..ζ]) + 1 ≤

2m − ⌈\frac{m}{δ_{1} + 1}⌉ − δ_{1} ≤ 2m − ⌈\sqrt{2m}⌉.

We have isolated the remaining case where α_{2} = 1 and P[δ_{1} + 2] ≠ P[2]. Let d be the largest integer such that α_{g} = 1 and P[δ_{g−1} + 2] ≠ P[2], for all g = 2, …, d. Then, C_{R:l} = 2, for all 1 ≤ l ≤ δ_{d} such that algorithm R:l is defined and μ(P[1..δ_{d}]) = δ_{d} − d + 1 ≥ δ_{d}/2 + 1.

We get similarly to the other cases above that C_{R:δ_{d}+α_{d+1}+1} ≤ 2−1/(δ_{d} + 1). If the algorithm does not reach the position ζ defined above, then C_{REV} ≤ 2 − 1/(δ_{d} + 1) and μ(P[1..m]) ≥ δ_{d}/2 + 1. Therefore,

ω(m) = ω_{REV} (m) ≤ ⌊C_{REV} × m⌋ − μ(P[1..m])
≤ 2m − ⌈\frac{m}{δ_{d} + 1}⌉ − \frac{δ_{d} + 1}{2}
≤ 2m − ⌈\sqrt{2m}⌉.

If the algorithm reaches the position ζ, then C_{R:l_{ζ}} ≤ 2 − 1/(δ_{d} + 1) and μ(P[1..m]) ≥ δ_{d}/2 + 2. Hence,

ω(m) ≤ ⌊C_{R:l_{ζ}} × m⌋ − μ(P[1..m]) + 1
≤ 2m − ⌈\frac{m}{δ_{d} + 1}⌉ − \frac{δ_{d} + 1}{2}
≤ 2m − ⌈\sqrt{2m}⌉.

To see that this is roughly the best possible for on-line algorithms consider the pattern P[1..m] that starts with the prefix P[1..δ] = ‘abac_{1}ac_{2} … ac_{h−1}ac_{h}’, such that δ = ⌈\sqrt{2m}⌉ is even and c_{i} ∉ \{‘a’, ‘b’\}. Then, any on-line self-prefix algorithm makes \frac{3}{2}δ − 1 symbol comparisons on the pattern prefix P[1..δ], and by carefully examining the proof of Theorem 2.25, at least C_{REV (P[1..δ])} × (m − δ) − 1 = (2 − 1/δ)(m − δ) − 1 comparisons on the remaining suffix. This sums up to at least 2m − ⌈\sqrt{2m} + 3/2⌉ symbol comparisons. □

Example. Consider the strings P[1..m] = Δ_{h}[1..2^{h}], h ≥ 3, that are defined in Section 2.1. Then, C_{R:2} = 2, C_{R:4} = 2, C_{R:6} = \frac{9}{5} and C_{REV (P[1..8])} = \frac{15}{8}. Thus, the optimal static prefix-matching algorithm RO is algorithm R:6 and C_{RO} = \frac{9}{5}. The self-prefix algorithm that is used in Theorem 4.5 is also the static algorithm R:6, since algorithm REV that is used on the input prefix P[1..8] before the algorithm decides to use algorithm R:6, is used only based on its definition on the input prefix P[1..4], which is identical to that of algorithm R:6. On the other hand, consider any string P[1..m], whose prefix P[1..8] = ‘ababacac’. Then, C_{R:2} = 2, C_{R:4} = \frac{5}{3}, C_{R:6} = \frac{7}{4}, C_{R:8} = \frac{11}{6} and C_{REV (P[1..8])} = \frac{7}{4}. Thus, the optimal static prefix-matching algorithm RO is algorithm R:4 and C_{RO} = \frac{5}{3}. However, the self-prefix algorithm that is used in Theorem 4.5 is not static, since it behaves as algorithm REV on the input prefix P[1..8] before its decides to behave as algorithm R:4.

Remark. Breslauer, Colussi and Toniolo [7] proved a 2m − ⌈2\sqrt{m}⌉ lower bound for the self-prefix problem. They fail to mention, however, that their proof holds for on-line algorithms, but not for general off-line algorithms, for which the same proof gives only a 2m − ⌈2\sqrt{2m}⌉ + 1 lower bound. We have designed an off-line algorithm (not given here) that makes at most 2m−⌈2\sqrt{m}⌉ symbol comparisons. We suspect that this can be improved.

5 Implementation details

In this section we show that any given static prefix-matching algorithm A, which is described by its comparison order, can be implemented in the standard random access machine computational model [1] in linear time and space. The same techniques are used to implement the on-line self-prefix algorithm from Theorem 4.5 and the optimal static prefix-matching algorithm RO, including the pattern preprocessing that creates it, in linear time and space. The implementation details somewhat resemble those of the string-matching algorithm of Breslauer and Galil [9].

We assume that the description of the static prefix-matching algorithm A(P[1..m]) includes the delay |Σ_{l}^{P}| and the period lengths π_{1}^{P[1..l]}, for l = 1, …, m, and the comparison order functions of algorithm A, that are given as:

π_{first}^{l}(Λ_{A,l}(h)) for l = 1, …, m and h = 1, …, |Σ_{l}^{P}|.

Notice that the functions Λ_{A,l}(h) need not be a part of the description since,

Λ_{A,l}(h) = P[l − π_{first}^{l}(Λ_{A,l}(h))].

The delay |Σ_{l}^{P}| can also be computed from π_{1}^{P[1..l]}, for l = 1, …, m, since by Proposition 2.6,

|Σ_{l}^{P}| = \{ \begin{matrix}|Σ_{l−π_{1}^{P[1..l−1]}}^{P}| & if π_{1}^{P[1..l]} < l \\ |Σ_{l−π_{1}^{P[1..l−1]}}^{P}| + 1 & otherwise. \end{matrix}

The reason that we choose to represent the comparison order functions by π_{first}^{l}(Λ_{A,l}(h)) is that the function π_{first}^{l}(σ) is indexed by an alphabet symbol σ ∈ Σ_{l}^{P}, which is difficult to implement efficiently without making additional symbol comparisons. The description of an algorithm requires O(m) space, by Lemma 2.11.

Lemma 5.1 Any given static prefix-matching algorithm A(P[1..m]) can be implemented in O(n) time with constant auxiliary space.

Proof. The generic implementation of the static algorithm A(P[1..m]) is given in Figure 2. The implementation clearly does not make any extraneous symbol comparisons and uses constant auxiliary space, apart from the output array Φ[1..n] that is used only to store the results of the computation.

Let l = t − k_{0}^{t} + 1. By Lemma 2.9 and Lemma 2.5, the members k_{i}^{t} ∈ K^{t} are grouped into |Σ_{l}^{P}| classes according to the symbols P[t − k_{i}^{t} + 1] ∈ Σ_{l}^{P}. If the algorithm reaches the conclusion that T [t] ≠ σ, for some σ ∈ Σ_{l}^{P}, then it sets Φ[k_{i}^{t}] = t − k_{i}^{t}, for all members k_{i}^{t} ∈ K^{t}, such that,

k_{i}^{t} ∈ {k_{0}^{t} + π + τ | π = π_{first}^{l}(σ) and τ ∈ Π^{P[1..l−π]} and τ < l − π} .

When the algorithm reaches the end of the text, there might still be members k_{i}^{n+1} ∈ K^{n+1}, such that the pattern prefixes that start at these positions of the text continues until the end of the text. The algorithm sets Φ[k_{i}^{n+1}] = n − k_{i}^{n+1} + 1, for all k_{i}^{n+1} ∈ K^{n+1}.

The total time spent by the algorithm is O(n), since the algorithm repeats the main loop n times and assigns values to each of the n entries Φ[h] of the output array only once. □

– The implementation of the static prefix-matching algorithm A(P[1..m]). k = 1 – k is k_{0}^{t} until it is updated to be k_{0}^{t+1}. for t = 1 to n do

h = 1 l = t − k + 1

– Find a symbol in Σ_{l}^{P} that matches T [t].

while h ≤ |Σ_{l}^{P}| and T [t] ≠ Λ_{A,l}(h) do

h = h + 1

– Terminate the pattern prefixes that start at positions k_{i}^{t} ∈ K^{t}, such that – P[t − k_{i}^{t} + 1] ≠ T [t]. (Lemma 2.5, Lemma 2.9 and Proposition 2.4.) for g = 1 to |Σ_{l}^{P}| do

if g ≠ h then – T [t] ≠ Λ_{A,l}(g). κ = k + π_{first}^{l}(Λ_{A,l}(g)) while κ ≤ t do

Φ[κ] = t − κ

κ = κ + π_{1}^{P[1..t−κ+1]}

end end

if h ≤ |Σ_{l}^{P}| then – A matching symbol was found.

if l = m and π_{first}^{l}(Λ_{A,l}(h)) = 0 then Φ[k] = m – A complete occurrence of P[1..m] was found. k = k + π_{1}^{P[1..m]}

else

k = k + π_{first}^{l}(Λ_{A,l}(h))

else – No match was found.

k = t + 1

end

– Terminate all the remaining pattern prefixes. (Lemma 2.5 and Proposition 2.4.) while k ≤ n do

Φ[k] = n − k + 1 k = k + π_{1}^{P[1..n−k+1]}.

end

Figure 2: The generic static prefix-matching algorithm.

Lemma 5.2 The self-prefix algorithm and the pattern preprocessing step that constructs the optimal static prefix-matching algorithm RO(P[1..m]) can be implemented in O(m) time and space.

Proof. By Proposition 4.1, in order to solve the self-prefix problem it suffices to compute the period lengths π_{1}^{P[1..l]}, for l = 1, …, m. The pattern preprocessing implements the algorithm in Theorem 4.5, constructs algorithm REV and all the algorithms R:θ, and computes their characteristic constants C_{R:θ} and C_{REV}. The algorithms REV (P[1..l]) and R:θ(P[1..l]) are constructed as soon as π_{1}^{P[1..l]} is given, so they can be used immediately, already at the next pattern position. The choice of which algorithm to use at the following pattern positions and which algorithm will be algorithm RO is made by comparing the characteristic constants of these algorithms.

Recall that the static algorithms R:θ are constructed from three parts. The first part is identical to algorithm REV, while the second and third parts are small variations on algorithm REV. Let algorithm M be defined at positions l, such that P[l] ≠ P[1], as^{6}:

Λ_{M,l}(h) = \{ \begin{matrix}Λ_{REV ,l}(h) & 1 ≤ h ≤ |Σ_{l}^{P}| and h ∉ \{Λ_{REV ,l}^{−1}(P [l]), Λ_{REV ,l}^{−1}(χ_{l})\} \\ P[l] & h = Λ_{REV ,l}^{−1}(χ_{l}) \\ χ_{l} & h = Λ_{REV ,l}^{−1}(P[l]), \end{matrix}

where χ_{l} is defined in Section 2.5. Algorithm E is defined such that,

Λ_{E,l}(h) = \{ \begin{matrix}P[l] & θ < l ≤ m and h = 1 \\ Λ_{REV ,l}(h − 1) & θ < l ≤ m and 2 ≤ h ≤ Λ_{REV ,l}^{−1}(P[l]) \\ Λ_{REV ,l}(h) & θ < l ≤ m and Λ_{REV ,l}^{−1}(P[l]) < h ≤ |Σ_{l}^{P}|. \end{matrix}

Our construction builds the three algorithms REV, M and E. Then, algorithm R:θ is given as:

Λ_{R:θ,l}(h) = \{ \begin{matrix}Λ_{REV ,l}(h) & l = 1, …, θ − 1 \\ Λ_{M,θ}(h) & l = θ \\ Λ_{E,l}(h) & l = θ + 1, …, m. \end{matrix}

With the exception that if θ is < π, l > malignant, then Λ_{R:θ,l}(h) = Λ_{M,l}(h), for h = 1, 2, 3. (It so happens that algorithm M has the right comparison order in this case. Notice that it is possible to test if θ is malignant in constant time without making any extra symbol comparisons.)

This definition in three parts allows to construct the algorithms R:θ in O(m) time and their description to be stored in O(m) space. The construction of these algorithms proceeds as the period lengths π_{1}^{P[1..l]} are being computed using the previously constructed algorithms. Observe that π_{1}^{P[1..l]} is computed by a single iteration of the main loop in Figure 2.

6Algorithm M is not used at positions l, such that P[l] = P[1], and it can be defined arbitrarily, or left undefined, at these positions.

At the beginning of this section we have shown how to compute |Σ_{l}^{P}|, given the period lengths π_{1}^{P[1..l]}. By the definition of algorithm REV and by Proposition 2.6,

Λ_{REV ,l}(h) = \{ \begin{matrix}Λ_{REV ,l−π_{1}^{P[1..l−1]}}(h) & h = 1, …, |Σ_{l−π_{1}^{P[1..l−1]}}^{P}| \\ P[l] & if |Σ_{l}^{P}| > |Σ_{l−π_{1}^{P[1..l−1]}}^{P}| and h = |Σ_{l}^{P}|. \end{matrix}

The static algorithms M and E are constructed by appropriately modifying the comparison order functions of algorithm REV. The characteristic constants C_{REV (P[1..l])} and C_{R:l} can be computed efficiently by Lemma 2.17 and Lemma 2.23. The construction of the static prefix-matching algorithms described above and the computation of their characteristic constants takes O(|Σ_{l}^{P}|) time at position l, amounting to O(m) time over the whole input string P[1..m], by Lemma 2.11. □

The following theorem is an immediate consequence of Lemma 5.1 and Lemma 5.2.

Theorem 5.3 The optimal static prefix-matching algorithm RO(P[1..m]), including its preprocessing step, can be implemented in O(n+m) time using O(m) auxiliary space.

6 Conclusions

We have been able to obtain roughly tight bounds on the number of comparisons required by on-line self-prefix algorithms and almost tight bounds for on-line prefix-matching algorithms with any given pattern. We hope that our techniques and results can prove useful in improving the bounds for the string-matching problem and in resolving some of the following problems.

1. What is the exact number of symbol comparisons required in on-line prefix-matching algorithms as a function of the pattern string and the text length? In off-line algorithms? If the pattern preprocessing is also accounted?

2. How many comparisons are required in general off-line self-prefix matching algorithms?

3. For which pattern strings off-line algorithms require fewer symbol comparisons than on-line?

4. Do comparisons of pairs of text symbols help in off-line prefix-matching algorithms? Paterson, Tassa and Zwick [36] have recently shown that comparisons of pairs of text symbols can help in the string-matching problem.

7 Acknowledgments

We thank Raffaele Giancarlo for his comments on an early version of this paper.

References

[1] A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.

[2] A. Amir, G. Benson, and M. Farach. An alphabet-independent approach to two-dimensional pattern-matching. SIAM J. Comput., 23(2):313–323, 1994.

[3] A. Apostolico and R. Giancarlo. The Boyer-Moore-Galil string searching strategies revisited. SIAM J. Comput., 15(1):98–105, 1986.

[4] R.S. Boyer and J.S. Moore. A fast string searching algorithm. Comm. of the ACM, 20:762–772, 1977.

[5] D. Breslauer. Fast Parallel String Prefix-Matching. Theoret. Comput. Sci., 137(2):269–278, 1995.

[6] D. Breslauer. Saving Comparisons in the Crochemore-Perrin String Matching Algorithm. Theoret. Comput. Sci., to appear.

[7] D. Breslauer, L. Colussi, and L. Toniolo. Tight Comparison Bounds for the String Prefix-Matching Problem. Inform. Process. Lett., 47(1):51–57, 1993.

[8] D. Breslauer, L. Colussi, and L. Toniolo. On the Exact Complexity of the String Prefix-Matching Problem. In Proc. 2nd European Symposium on Algorithms, number 855 in Lecture Notes in Computer Science, pages 483–494. Springer-Verlag, Berlin, Germany, 1994.

[9] D. Breslauer and Z. Galil. Efficient Comparison Based String Matching. J. Complexity, 9(3):339–365, 1993.

[10] R. Cole. Tight Bounds on the Complexity of the Boyer-Moore String Matching Algorithm. SIAM J. Comput., 23(5):1075–1091, 1994.

[11] R. Cole, M. Crochemore, Z. Galil, L. Ga̧sieniec, R. Hariharan, S. Muthukrishnan, K. Park, and W. Rytter. Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. In Proc. 34th IEEE Symp. on Foundations of Computer Science, pages 248–258, 1993.

[12] R. Cole and R. Hariharan. Tighter Bounds on the Exact Complexity of String Matching. In Proc. 33rd IEEE Symp. on Foundations of Computer Science, pages 600–609, 1992.

[13] R. Cole, R. Hariharan, M. Paterson, and U. Zwick. Tighter Lower Bounds on the Exact Complexity of String Matching. SIAM J. Comput., 24(1):30– 45, 1995.

[14] L. Colussi. Correctness and efficiency of string matching algorithms. Inform. and Control, 95:225–251, 1991.

[15] L. Colussi. Fastest Pattern Matching in Strings. J. Algorithms, 16(2):163– 189, 1994.

[16] M. Crochemore. Off-line serial exact string searching. Technical Report 92.1, Institut Gaspard Monge, Université de Marne la Vallée, Marne la Vallée, France, 1992.

[17] M. Crochemore. String-matching on ordered alphabets. Theoret. Comput. Sci., 92:33–47, 1992.

[18] M. Crochemore, L. Ga̧sieniec, and W. Rytter. Turbo-BM. Technical Report 92.61, Laboratoire Informatique Théorique et Programmation, Université Paris 7, Paris, France, July 1992.

[19] M. Crochemore, T. Lecroq, A. Czumaj, L. Ga̧sieniec, S. Jarominek, W. Plandowski, and W. Rytter. Speeding Up Two String-Matching Algorithms. In Proc. 9th Symp. on Theoretical Aspects of Computer Science, number 577 in Lecture Notes in Computer Science, pages 589–600. Springer-Verlag, Berlin, Germany, 1992.

[20] M. Crochemore and D. Perrin. Two-way string-matching. J. Assoc. Comput. Mach., 38(3):651–675, 1991.

[21] M. Crochemore and W. Rytter. Periodic Prefixes in Texts. In R. Capocelli, A. De Santis, and U. Vaccaro, editors, Proc. of the Sequences ’91 Workshop: “Sequences II: Methods in Communication, Security and Computer Science”, pages 153–165. Springer-Verlag, Berlin, Germany, 1993.

[22] Z. Galil. Optimal parallel algorithms for string matching. Inform. and Control, 67:144–157, 1985.

[23] Z. Galil and R. Giancarlo. On the exact complexity of string matching: lower bounds. SIAM J. Comput., 20(6):1008–1020, 1991.

[24] Z. Galil and R. Giancarlo. The exact complexity of string matching: upper bounds. SIAM J. Comput., 21(3):407–437, 1992.

[25] Z. Galil and K. Park. Truly Alphabet-Independent Two-Dimensional Pattern Matching. In Proc. 33th IEEE Symp. on Foundations of Computer Science, pages 247–256, 1992.

[26] Z. Galil and J. Seiferas. Time-space-optimal string matching. J. Comput. System Sci., 26:280–294, 1983.

[27] L. Ga̧sieniec and K. Park. Work-Time Optimal Parallel Prefix Matching. In Proc. 2nd European Symposium on Algorithms, number 855 in Lecture Notes in Computer Science, pages 471–482. Springer-Verlag, Berlin, Germany, 1994.

[28] L. Ga̧sieniec, W. Plandowski, and W. Rytter. Constant-space string matching with smaller number of comparisons: sequential sampling. In Proc. 6th Symp. on Combinatorial Pattern Matching, number 937 in Lecture Notes in Computer Science, pages 78–89. Springer-Verlag, Berlin, Germany, 1995.

[29] L.J. Guibas and A.M. Odlyzko. A New Proof of the Linearity of the Boyer-Moore String Matching Algorithm. SIAM J. Comput., 9(4):672–682, 1980.

[30] C. Hancart. On Simon’s string searching algorithm. Inform. Process. Lett., 47(2):95–99, 1993.

[31] R. Hariharan and S. Muthukrishnan. Optimal Parallel Algorithms for Prefix Matching. In Proc. 21th International Colloquium on Automata, Languages, and Programming, number 820 in Lecture Notes in Computer Science, pages 203–214. Springer-Verlag, Berlin, Germany, 1994.

[32] D.E. Knuth, J.H. Morris, and V.R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6:322–350, 1977.

[33] T. Lecroq. A variation on the Boyer-Moore algorithm. Theoret. Comput. Sci., 92:119–144, 1992.

[34] M. Lothaire. Combinatorics on Words. Addison-Wesley, Reading, MA., U.S.A., 1983.

[35] G.M. Main and R.J. Lorentz. An O(n log n) algorithm for finding all repetitions in a string. J. Algorithms, 5:422–432, 1984.

[36] M. Paterson, S. Tassa, and U. Zwick. Looking for Mum and Dad. In preparation, 1994.

[37] R.V. Rivest. On the Worst Case Behavior of String-Searching Algorithms. SIAM J. Comput., 6:669–674, 1977.

[38] U. Zwick and M.S. Paterson. Lower bounds for string matching in the sequential comparison model. Manuscript, 1991.

Recent Publications in the BRICS Report Series

RS-95-46 Dany Breslauer, Livio Colussi, and Laura Toniolo. On the Comparison Complexity of the String Pre�x-Matching Problem. August 1995. 39 pp. Appears in Leeuwen, editor, Algorithms - ESA ’94: Second Annual European Symposium proceedings, LNCS 855, 1994, pages 483�494.

RS-95-45 Gudmund Skovbjerg Frandsen and Sven Skyum. Dynamic Maintenance of Majority Information in Constant Time per Update. August 1995. 9 pp.

RS-95-44 Bruno Courcelle and Igor Walukiewicz. Monadic Second-Order Logic, Graphs and Unfoldings of Transition Systems. August 1995. 39 pp. To be presented at CSL ’95.

RS-95-43 Noam Nisan and Avi Wigderson. Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version). August 1995. 17 pp. To appear in 36th Annual Conference on Foundations of Computer Science, FOCS ’95, IEEE, 1995.

RS-95-42 Mayer Goldberg. An Adequate Left-Associated Binary Numeral System in the λ-Calculus. August 1995. 16 pp.

RS-95-41 Olivier Danvy, Karoline Malmkj�r, and Jens Palsberg. Eta-Expansion Does The Trick. August 1995. 23 pp.

RS-95-40 Anna Ing� olfsd� ottir and Andrea Schalk. A Fully Abstract Denotational Model for Observational Congruence. August 1995. 29 pp.

RS-95-39 Allan Cheng. Petri Nets, Traces, and Local Model Checking. July 1995. 32 pp. Full version of paper appearing in Proceedings of AMAST ’95, LNCS 936, 1995.

RS-95-38 Mayer Goldberg. G� odelisation in the λ-Calculus. July 1995. 7 pp.

RS-95-37 Sten Agerholm and Mike Gordon. Experiments with ZF Set Theory in HOL and Isabelle. July 1995. 14 pp. To appear in Proceedings of the 8th International Workshop on Higher Order Logic Theorem Proving and its Applications, LNCS, 1995.