Tighter Lower Bounds on the Exact Complexity of String Matching.
This paper considers the exact number of character comparisons needed to  find all occurrences of a pattern of length $m$ in a text of length $n$ using on-line and general algorithms. For on-line algorithms, a lower bound of about  $(1+\frac{9}{4(m+1)})\cdot n$ character comparisons is obtained. For general algorithms, a lower bound of about $(1+\frac{2}{m+3})\cdot n$ character comparisons is obtained. These lower bounds complement an on-line upper bound  of about $(1+\frac{8}{3(m+1)})\cdot n$ comparisons obtained recently by Cole and Hariharan.  The lower bounds are obtained by finding patterns with interesting combinatorial properties. It is also shown that for some patterns off-line algorithms can be more efficient than on-line algorithms.
Introduction
. The classical string matching problem is the problem of finding
all occurrences of a pattern in a text String matching is among
the most extensively studied problems in computer science. A survey of the various
algorithms devised for it can be found in [Ah90].
Among the most efficient algorithms devised for string matching are algorithms
that gain information about the pattern and text only by performing comparisons
between pattern and text characters. Such algorithms need not have any prior knowledge
of the (possibly infinite) alphabet from which the pattern and text are drawn.
We investigate the exact comparison complexity of string matching in this model and
obtain lower bounds on the number of comparisons required (in the worst case). These
lower bounds allow the algorithms to preprocess the pattern (but not the text). The
lower bounds remain valid even if the algorithms do know the alphabet in advance
provided that the alphabet contains a character not appearing in the pattern.
Two kinds of comparison based algorithms have been studied. An on-line algorithm
is an algorithm that examines text characters only in a window of size m sliding
monotonically to the right; furthermore, the window can slide to the right only when
all matching pattern instances to the left of the window or aligned with the window
have been discovered. A general (or off-line) algorithm is an algorithm that can access
both the pattern and the text in an unrestricted manner.
Perhaps the most widely known linear time algorithms for string matching are
the Knuth-Morris-Pratt [KMP77] and Boyer-Moore [BM77] algorithms. We refer to
them as the KMP and BM algorithms, respectively. The KMP algorithm makes at
most comparisons and this bound is tight. The exact complexity of the BM
algorithm was an open question until recently. It was shown in [KMP77] that the BM
algorithm makes at most 6n comparisons if the pattern does not occur in the text.
y Courant Institute, New York University, New York 10012. The first two authors were supported
in part by NSF grants CCR-8902221, CCR-8906949, CCR-9202900 and CCR-8901484.
z Department of Computer Science, University of Warwick, Coventry CV4 7AL, England. This
author was supported in part by the ESPRIT BRA Programme of the EC under contracts #3075
(ALCOM) and #7141 (ALCOM II). A part of this work was carried out while this author was visiting
Tel Aviv University.
x Department of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. A part of this
work was carried out while this author was visiting the University of Warwick.
Guibas and Odlyzko [GO80] reduced this to 4n under the same assumption. Cole
finally proved an essentially tight bound of 3n \Gamma n=m) comparisons for the
BM algorithm, whether or not the pattern occurs in the text.
The versions of the KMP and BM algorithms considered in the preceding paragraph
are comparison based. It is interesting to note that both algorithms have
variants that are not purely comparison based and do not fall into the category of
algorithms considered in this paper. The failure function of the KMP algorithm
[KMP77] yields finite automata that perform string matching by reading each character
exactly once. However, simulations of these automata require prior knowledge
of the alphabet and the number of comparisons needed to simulate each transition
depends on the alphabet size. Transitions can be simulated in unit time by using text
characters to address an array of pointers, but this is not allowed in our model.
The standard BM algorithm [BM77] uses two shift functions to determine the
distance to shift the pattern when a mismatch occurs. One of these shift functions,
the occurrence shift , gives the rightmost position in the pattern in which the unmatched
text character occurs. An efficient implementation of this shift function is
again alphabet dependent. The second shift function used by the BM algorithm is
comparison based. The analysis of Cole [Cole91] shows that the occurrence shift function
does not improve the worst case behaviour of the BM algorithm. This occurrence
shift function is very important in practice, however, as it ensures sublinear time in
various probabilistic settings (see [BGR90]). For a study of how the KMP, BM and
other algorithms behave in practice the reader is referred to [HS91].
Apostolico and Crochemore [AC89] gave a simple variant of the KMP algorithm
which makes at most 3
comparisons. Apostolico and Giancarlo [AG86] gave a variant
of the BM algorithm which makes at most 2n \Gamma m+1 comparisons. Crochemore et al.
showed recently that remembering just the most recently matched portion
reduces the upper bound of BM from 3n to 2n comparisons.
Recently, Galil and Giancarlo [CGG90],[GG92] analyzed and modified a string
matching algorithm designed by Colussi [Coll91] ; they showed it makes at most 4
comparisons. In fact, [GG92] give this bound in a sharper form as a function of
the period z of the pattern; the bound becomes n
g.
Galil and Giancarlo [GG91] have also shown that any on-line algorithm for string
matching must perform at least 4
comparisons for some strings (the string
aba is an example). It will be shown here that this lower bound also applies to general
algorithms, if only pattern-text comparisons are allowed.
The algorithm of Galil and Giancarlo [GG92] is efficient for relatively short pat-
terns. It may become inefficient for longer patterns. Breslauer and Galil [BG92] and
Cole and Hariharan [CH92] have shown that the string matching problem becomes
easier as the length of the pattern increases. Breslauer and Galil [BG92] developed an
algorithm that performs at most (1 +O( logm
character comparisons for texts of
length n and patterns of length m. Cole and Hariharan [CH92] obtained an algorithm
that performs at most (1 +O( 1
comparisons. As we shall see, this is essentially
tight.
Galil and Giancarlo [GG91] showed that any on-line algorithm must perform at
least
comparisons for some patterns of odd length m, and that
any (general) algorithm must perform at least (1
comparisons for
some patterns of length m.
In this work we improve the lower bounds for both on-line and off-line algorithms.
We also show that for certain patterns off-line algorithms can be more efficient than
TIGHTER LOWER BOUNDS ON STRING MATCHING 3
on-line algorithms. Some of our lower bounds apply in a model in which both text-
text and pattern-text comparisons are allowed. We suspect that for some patterns
text-text comparisons can improve the efficiency of string matching algorithms.
Our improved lower bounds are the following: for on-line algorithms that use
only pattern-text comparisons, a lower bound of (1
comparisons is obtained, for 1. For on-line algorithms that
are allowed to use both pattern-text and text-text comparisons, a lower bound of
character comparisons is obtained, for
algorithms, that are allowed to use both pattern-text and
text-text comparisons, a lower bound of (1
comparisons
is obtained, for 2. We also get an off-line lower bound of3 \Delta character comparisons for only pattern-text comparisons are
allowed.
The on-line lower bounds presented come very close to the on-line upper bound of
obtained by Cole and Hariharan [CH92]. The worst-case comparison
complexity of string matching is therefore almost exactly determined. It is asymptotically
of the form (1
algorithms 9
3 and for general
algorithms
3 .
Our work builds on the work of Galil and Giancarlo [GG91]. Our point of view,
however, is a bit different. Galil and Giancarlo [GG91] investigated the number of
comparisons required only as a function of n, the text length, and m, the pattern
length. We are interested in the number of comparisons required as a function of the
text length and the specific pattern sought.
In the next section we explain, in more detail, the rules of the string matching
game in the comparison model setting. In Section 3 we describe the adversary arguments
that lie at the heart of our lower bounds proofs. The off-line lower bounds
presented in Section 4 follow almost immediately from the arguments of Section 3.
A specific lower bound is obtained for every pattern. This lower bound depends on
the first and second periods of the pattern (see next section). These off-line lower
bounds are shown to be tight for an interesting family of patterns. Exploiting the
additional restrictions placed on on-line algorithms, we obtain, in Sections 5 and 6,
improved on-line lower bounds. The lower bound of Section 5 depends again on the
first and second periods of the patterns. Additional periods and more complicated
combinatorial structures are used in Section 6. In section 7 we obtain some on-line
upper bounds (for strings of the form a k ba ' ) that match the on-line and some of the
off-line lower bounds of Sections 4 and 5. Finally, in Section 8 we exhibit a pattern
(abaa) for which an off-line algorithm (it is actually on-line with a small look-ahead)
performs better than any on-line algorithm.
A preliminary version of this paper has appeared in [CHPZ93].
2. Preliminaries. The algorithms we consider are allowed to access the text
and the pattern only through queries of the form To
each such query the algorithm is supplied with a 'yes' or `no' answer. An algorithm
is charged only for the queries it makes; all other computations are free of charge.
Algorithms may adaptively choose their queries depending on the answers to earlier
queries. An algorithm in this model may be viewed as a sequence of decision trees.
Similar comparison models are used to study comparison problems such as sorting,
searching and selection.
For a string w, let c(w) denote the minimal constant for which there exists a string
matching algorithm that finds all occurrences of the pattern w in a text of length n
using at most c(w) comparisons (between text and pattern characters and
between pairs of text characters). A variant of c(w) is c   (w) in which the algorithm
is not allowed to compare pairs of text characters. Obviously c(w) - c   (w).
In the definition of c(w) and c   (w), we allow unrestricted off-line algorithms that
have random access to all the characters of the text. By contrast, we define c k (w) and
c
k (w) to be the corresponding minimal constants when the algorithms have access to
the text only through a sliding window of size jwj+k (where jwj denotes the length of
w). Furthermore, the algorithm is only allowed to slide the window past a text position
when it has already reported whether an occurrence of the pattern starts at that text
position. Algorithms using a sliding window of size jwj (i.e., are traditionally
called on-line algorithms. We call algorithms that use larger windows, finite look-ahead
or window algorithms. Clearly c(w) - c k (w) - c 0 (w) for any k - 0. We show
in Section 8 that for some w and some k, c k (w) ! c 0 (w). More specifically, we show
there that c 4 (abaa) ! c 0 (abaa). This means that for some patterns, algorithms that
use larger windows may be more efficient than all algorithms that use smaller windows.
It is still an open problem whether there exists a string w for which c(w) ! c k (w) for
every k - 0. That is, it is not known whether there exists strings for which an optimal
off-line algorithm is better than any finite look-ahead algorithm. It is clear however
that c k (w) is non-increasing in k. The following Lemma is also easily established.
Lemma 2.1. For any string w we have lim k!1 c k
Proof. Let c(n) be the number of comparisons required, in the worst case, to find
all occurrences of w in a text of length n using an unrestricted algorithm. By the
definition of c(w) we get that c(n) - c(w) o(n). For every
consider now the following algorithm with look-ahead k. The algorithm finds
all occurrences of w in its window of size k+ jwj using at most c(k
The window is then slid by k positions and the same process is repeated. The
number of comparisons performed by this algorithm on a text of length n is at most
where
and -
d k (w) is some constant (depending on w and k). In particular we get that
(w). It is now easy to check that lim k!1 - c k (w) = c(w) and therefore
c(w). It is clear however that lim k!1 c k (w) - c(w) and the required
equality follows.
It is easy to see that 1 - c(w) - c 0 (w); c   (w) - c
0 (w) for every string w. The
KMP algorithm shows that 1 - c
for every w. The algorithm of Galil and
Giancarlo [GG92] shows that 1 - c
3 , for every w. The algorithm of Breslauer
and Galil [BG92] shows that 1 - c
m for every string of length m. Fi-
nally, the algorithm of Cole and Hariharan [CH92] shows that 1 - c
for every string w of length m. The algorithms (of [KMP77],[GG92],[BG92],[CH92])
mentioned here are all on-line and they use only pattern-text comparisons.
Galil and Giancarlo [GG91] showed that c
m+3 for some
patterns of odd length m. We show that for infinitely many values of m there exists
strings of length m for which c
4(m+1) . We also show that
TIGHTER LOWER BOUNDS ON STRING MATCHING 5
for infinitely many values of m there exists strings of length m for which c
7m+27 . This shows that the algorithm of Cole and Hariharan is not far from
being optimal. We further show that c   (w) - c(w)
m+3 for some patterns of
showing essentially that the lower bounds obtained by [GG91] for
on-line algorithms also hold for general algorithms.
Let w be a string of length m. We say that z (1 - z - m) is a period of w if
and only if be the minimal period of
period exists since m is always a period of w.) Let z 2 be the minimal
period of w which is not divisible by z 1 . If such a second period does not exist we
set z 1. We call z 1 the period of w and z 2 the second period of w. Periodicity
properties play a major role in the sequel.
It is well known (see, e.g., [KMP77]) that if z 1 and z 2 are periods of w and if
period of w. If z 1 and z 2 are
the first and second periods of w then gcd(z 1 ; z 2 ) is not a period of w and, as a
consequence, 2.
3. Adversary arguments. Our lower bounds are derived using an adversary
that fills in the text while answering the algorithm's queries. The adversary always
'tiles' the text with (overlapping) occurrences of the pattern. Every character of
the text eventually becomes part of an occurrence, which the algorithm must find.
Consequently the algorithm must establish the identity of each text character and
it can achieve this only by getting at least one 'yes' answer for each position. The
adversary tries to avoid giving 'yes' answers whenever possible. It gives a `yes' answer
only when a 'no' answer would either contradict a previous answer or prevent it from
completely tiling the text. The arguments of this section are generalizations of similar
arguments of Galil and Giancarlo [GG91].
The statement, made above, that at least one 'yes' answer must be obtained by
the algorithm for each text position covered by an occurrence of the pattern seems
obvious. It is indeed immediate if only pattern-text comparisons are allowed. A
slightly more complicated argument is needed to handle the possibility of text-text
comparisons.
Lemma 3.1. A comparison based algorithm can be certain about the identity of s
text characters in a text t only after receiving at least s 'yes' answers.
Proof. We construct a graph G which has one vertex for each text position and one
vertex for each of the k distinct symbols which appear in the pattern w. Every edge
in G corresponds to a 'yes' answer received by the algorithm. If a `yes' answer was
given to a query then an edge is added between the vertex corresponding
to t[j] and the vertex corresponding to the symbol at w[i]. If a 'yes' answer was given
to a query then an edge is added between the vertices corresponding to
t[i] and t[j].
At any stage of the algorithm the graph G constructed so far represents the
positive information known about the characters in the text. The text positions corresponding
to vertices in components of G which contain a pattern symbol vertex are
the only text positions where the identity of the character is known. Since the alphabet
size is unlimited, the character at any other text position is not yet determined.
Since a component of size p containing a pattern symbol vertex has
and at least edges, the total numbers of known text positions is at most the
total number of 'yes' answers.
Next we describe a scheme using which the adversary can give any algorithm a
relatively large number of 'no' answers. We begin with a simple example.
6 COLE, HARIHARAN, PATERSON, AND ZWICK
The pattern string is aba, and let 1. We consider the
family of text strings of length n defined as follows. Place a's
in positions 3j, for of all texts t v . In positions 3j
simplicity, we number the positions here from 0). This
family may be depicted schematically as:
ba
ab
a
ba
ab
a
ba
ab
Finding all occurrences of aba in a text string from F is equivalent to determining
the index vector v 2 f0; 1g r . An adversary can force at least one 'no' answer before
revealing each bit of v.
The following definition generalises the properties of the example.
Definition 3.2. Let w be a string. A family of
texts of length n is said to be r-separating for w if there exist distinct indices
r such that:
1. for every r and for every i, the text t v contains an
occurrence of w starting at position u 0
if and only if v and an occurrence of w
at position u 1
if and only if v
2. the answer to any query of the form 'w[i] = t[j]?' is either `yes' for all texts
or 'no' for all texts t v , or `yes' for a text t v if and only if v fixed
1g.
The following Lemma is easily established. Its proof is omitted.
Lemma 3.3. If is an r-separating family then the answer
to a text-text query either `yes' for all texts t v , or 'no' for all t v , or
'yes' for t v if and only if v k1 = '' 1 , or `yes' for t v if and only if v k1 \Phi v
'yes' in t v if and only if v k1
1g.
In the example given before Definition 3.2, there is no text-text query whose
answer is 'yes' if and only if v k1
1g. Such a situation may arise however for patterns w that contain
more than two distinct characters.
We are now ready to prove:
Lemma 3.4. If F is an r-separating family for w then, for any comparison-based
algorithm for w, there exists a text t v 2 F for which the algorithm receives at least r
'no' answers before being able to locate all the occurrences of w in t v .
Proof. The adversary maintains a set E containing linear equations over the
binary field GF(2) in the variables v any stage, there is at least one
vector v 2 f0; 1g r that satisfies all the equations of E, and if a vector v 2 f0; 1g r
satisfies all the equations of E then the text t v is consistent with all answers given so
far by the adversary. Further, the number of equations in E is at most the number
of 'no' answers given by the adversary. At the beginning and as no query has
been made, all texts are still possible. This is how the adversary responds to a new
query:
If the answer to the query is the same for all texts t v for which v is a solution of
E, the adversary responds with this common answer. The set E remains unchanged
and all the invariants remain satisfied.
Otherwise, the adversary answers with a 'no'. It then adds an equation to E in
the following way. As the answer to the current query is not the same for all the texts
in F , there exist, by Definition 3.2 and by Lemma 3.3, either a single equation e 1 or
TIGHTER LOWER BOUNDS ON STRING MATCHING 7
two equations e 1 and e 2 such that the answer to the query is 'yes' in t v if and only if
If the answer to the query, according to t v , is 'yes' if and only if e 1 is satisfied,
then e 1 , the equation obtained from e 1 by complementing its free coefficient, is added
to E. If the answer to the query, according to t v , is 'yes' if and only if both e 1 and e 2
are satisfied, then at least one of e 1 and e 2 is independent of the equations of E, as
otherwise the answer would have been the same for all surviving texts. If e 1 does not
depend on E then the equation e 1 is added to E, otherwise e 2 is added. It is easy to
verify that all the required invariants are still satisfied.
The algorithm's task is done only when there is a unique solution to E. This
happens only when the set E contains at least r equations. An equation is added to
only as a result of a 'no' answer. The adversary can therefore give the algorithm
at least r 'no' answers.
Lemmas 3.1 and 3.4 can be combined together to give a lower bound of n
if, in every text t v of the separating family F used in Lemma 3.4, every text position
is covered by an occurrence of the pattern w. Such separating families will be
constructed in the next section.
4. Off-line lower bounds.
Theorem 4.1. If w is a string and z 1 ; z 2 are its first and second periods then
z1+z2 .
Proof. Assume without loss of generality that
For every v 2 f0; 1g r construct a text t v of length n in which, for every
occurrences of w start at j(z 1 and either at j(z 1 or at j(z 1
according to whether v 1. It is easy to verify that
is an r-separating family for w where u 0
for This construction is depicted in Figure 1 (note that z 1
Consider now a comparison-based algorithm A that finds all occurrences of w in a
string of length n. According to Lemma 3.4, A gets at least r 'no' answers for at
least one text t v0 , where v 0 2 f0; 1g r . It is also easy to see that every text t v , and in
particular t v0 , is completely covered with occurrences of w. According to Lemma 3.1,
A must therefore get at least n 'yes' answers on t v0 . In total, A must make, in the
worst case, at least n
z1+z2 comparisons for a text of length n.
As an example, note that for the string aba, z
5 . The separating family used to obtain this lower bound may be depicted
as:
ba
ab
aba
ba
ab
aba
ba
ab
This family has the property that, in every text of the family, every position is covered
by an occurrence of aba. The separating family for aba given after Definition 3.2 did
not have this property.
As a further example, note that for the string abaa we have z
and therefore c(abaa) - 8
7 . In Section 8 it will be shown that this bound is tight,
7 . We will see from Theorem 7.1 that c 0
4 . This provides
an example of a string for which off-line algorithms can be more efficient than on-line
algorithms.
Theorem 4.2. If w is a string, z 1 ; z 2 are its first and second periods, and 2z
z2 .
8 COLE, HARIHARAN, PATERSON, AND ZWICK
Fig. 1. The configuration used to prove that c(w)
Fig. 2. A configuration used to show that c(w)
Proof. The proof is very similar to the proof of Theorem 4.1. A separating family,
in which every text is almost completely tiled with occurrences of w, may be obtained
this time without using occurrences of w that are common to all the texts of the
family.
Assume that 1. For every v 2 f0; 1g r , construct
a text t v of length n in which, for occurrences of w start at jz 2 if
at 1. It is again easy to check that is an
r-separating family for w where this time u 0
r. The construction is depicted in Figure 2. Note that if z are
periods of w then so is 2z As every position in a text t v , except
perhaps the first and last z positions, is covered by an occurrence of w. Thus,
as in the proof of Theorem 4.1, we can show that any algorithm must perform, in the
worst case, at least n(1
As an example, for the string aabaa we have z
and therefore c(aabaa) - 5
4 . The separating family used this time is:
ba
ab
aa
ba
ab
aa
ba
ab
Theorem 4.3. c
3 .
Proof. The upper bound will follow from Theorem 7.1. The lower bound does not
TIGHTER LOWER BOUNDS ON STRING MATCHING 9
follow from Theorem 4.2 as the condition jwj is not satisfied. A specialized
argument is needed in this case. The argument given here assumes that only pattern-
text comparisons are allowed. It does not seem to extend in a simple manner to the
case in which both pattern-text and text-text comparisons are allowed.
The lower bound is obtained using the separating family for aba given after Definition
3.2. A complication arises however as texts in this family are not completely
covered by occurrences of aba.
Assume that 1. The adversary starts by putting a's in
all text positions 3j, for It will set positions 3j to either ab or
ba only after replying with a 'no' to at least one query concerning these positions.
The adversary answers the queries of the algorithm in the following way. If the
queried text position was already set by the adversary, the answer consistent with this
setting is returned. If the query is 't[3j
and position 3j + k has not yet been set, the adversary responds with a 'no'. It then
sets positions 3j to either ab or ba, whichever is consistent with its 'no'
answer.
All text positions of the form 3j eventually be covered by
occurrences of aba. The adversary therefore forces at least one 'no' answer and two
'yes' answers for each such pair. Positions of the form 3j are not necessarily covered
by occurrences of aba. If, however, position 3j is not covered by such an occurrence,
then positions are set to ba and positions 3j +1; 3j +2 are set to ab. An
algorithm must still query position 3j at least once in such a case, to either verify or
rule out an occurrence of aba starting at position 3j \Gamma 1. This completes the proof.
For a non-periodic string w (i.e., a string with z 1), the above
theorems give only the trivial lower bound, c(w) - 1. This bound is tight however as
the many string matching algorithms (see, e.g., those of [Coll91],[GG91] and [CH92])
perform at most n comparisons when searching for a non-periodic pattern in a text
of length n.
As a corollary to Theorem 4.2 we get
Corollary 4.4. For k; ' - 2 we have c(a k ba '
.
Proof. It is easy to check that the first and second periods of are
1. The claim follows immediately from Theorem 4.2.
In Section 7 it will be shown that the bounds given in Corollary 4.4 are tight. They
can even be matched using on-line algorithms. As a further Corollary to Theorem 4.2
(or Corollary 4.4) we get
Corollary 4.5. For every there exists a string
wm(= a k ba k ) of length m such that any algorithm that finds all the occurrences of
wm in a text of length n must make at least
comparisons in the
worst case.
We know (see last paragraph of Section 2) that if z 1 and z 2 are the first and
second periods of w then z 1 2. As z 2 - z we get that z 2 - d jwj+3
e.
Corollary 4.5 is therefore the strongest result of its kind implied by Theorem 4.2.
5. On-line lower bounds - I. In this short section we show that the lower
z2 , obtained for off-line algorithms only when 2z
for on-line algorithms even if this condition does not hold.
Theorem 5.1. If w is a string and z 2 is its second period then c 0 (w)
z2 .
Fig. 3. The configuration used to prove that c 0 (w)
Proof. Suppose that an on-line algorithm has just found an occurrence of w in
the text. The window will now be slid by at most z 1 positions to the right. Place
two copies of w shifted by z 1 and z 2 positions below w, as shown in Figure 3. Denote
these copies by w 0 and w 00 . Since z is not a period of w, the two copies w 0
and w 00 must disagree in at least one position after the end of the found occurrence
of w. The adversary will extend the found occurrence of w by either w 0 or w 00 in a
way that will force the algorithm to get at least one 'no' answer. If the algorithm
makes a query whose answer is identical under both continuations, the adversary
gives the algorithm this common answer. At some stage the algorithm has to make
a query that distinguishes between the two noncompatible continuations. No matter
what this query is, the adversary answers it by 'no'. The adversary now chooses the
continuation consistent with this 'no' and answers all further questions accordingly,
until the algorithm finds the chosen occurrence. By then the algorithm has either
made at least z queries and can slide the window by only z 1 positions, or has
made at least z 2 +1 queries and can slide the window by only z 2 positions. Note that
to verify an occurrence of the pattern in the text, the algorithm must get at least one
'yes' answer for each character of this occurrence. This process will be repeated again
and again forcing the algorithm to make at least (1
queries on a text
of length n.
In the next section we obtain, using more complicated arguments, better lower
bounds for on-line algorithms (see Corollaries 6.3 and 6.5).
6. On-line lower bounds - II. In (the proof of) Theorem 5.1 it was shown
that for every non-periodic pattern the adversary can force any algorithm to make at
least one mistake (i.e., get at least one 'no' answer) for each occurrence of the pattern
used in the tiling of the text. Now we show that for certain patterns the adversary
can force any algorithm to make at least two mistakes for each such occurrence. The
algorithm of Cole and Hariharan [CH92] makes at most two mistakes for each such
occurrence, so no adversary can force all algorithms to make at least three mistakes
for each occurrence of the tiling.
Theorem 6.1. Let w be a string of length m and let z
periods of w such that for every 1 is not a period of w.
(i) If none of the multi-sets fw[m contains a
character exactly
zk .
(ii) In addition, if none of the multi-sets f(w[m+
contains exactly
zk .
Before proceeding with the proof of this theorem, we try to clarify the conditions
appearing in it. Consider k copies of w, positioned in an array of k
numbered columns numbered where the copy
in the i th row is shifted z i positions to the right with respect to the copy in the 0 th
TIGHTER LOWER BOUNDS ON STRING MATCHING 1112134511211213451121
(a) The set up hw
(b) The set up hw 12 ; 9; 11; 12i
Fig. 4. Two simple setups in which Theorem 6.1 can be applied
row. Such arrays are depicted in Figure 4(a) for the string
in Figure 4(b) for the string w
with z contains the
characters appearing in column in the array corresponding
to w. The requirement in clause (i) above is that, in each column that lies after the
end of the copy of the 0 th row, but at or before the end of any of the other copies,
no character appears in all but one of the rows. It is easy to check that in both cases
depicted in Figure 4 this condition is satisfied. Note that when
requires that the three characters in such a column will either all be equal or all be
distinct.
To check the condition of clause (ii) above, one needs to look at pairs of such
columns and compare the pair of characters appearing in each row. The number j of
equal pairs is required to satisfy j 6= k \Gamma 1. It is easily verified that this condition is satisfied
in the array of w but not in the array of w
Thus for w 10 we obtain c
5 , while for w 12 we can only infer c
6 .
Proof. The proof (of both statements) is a simple extension of the proof of Theorem
5.1. Suppose that an on-line algorithm has just found an occurrence of w in
the text. The window can be slid at most z 1 positions to the right. Below w, place
k copies of w shifted by z positions respectively (the reader may refer to

Figure

3 imagining that k instead of just two copies appear there). Since none of
is a period of w, each pair of copies must disagree in at least one position after
the end of the found occurrence of w. The adversary will extend the found occurrence
of w by one of the k copies in a way that will force the algorithm to get at least
two 'no' answers. If the algorithm asks a question whose answer under the above k
continuations is the same, the adversary gives the algorithm this common answer. At
some stage the algorithm has to make a query to which the answer is 'yes' according
to some of the continuations, and 'no' according to the rest of them. The adversary
will answer this query with a 'no'. Conditions (i) and (ii) imply that at least two continuations
are consistent with this 'no' answer. The adversary now gives the common
answers to all queries that do not distinguish between the remaining continuations.
At some stage the algorithm has to make another query to which both answers are
possible. Again, the adversary answers this with a 'no'. At least one continuation
is consistent with all the replies given by the adversary. The adversary chooses one
of them and answers all subsequent queries accordingly, until the algorithm finds the
next occurrence of w. By then the algorithm has made at least z
and it can slide the window by only z i positions.
We will henceforth say that is a setup if w is a string, and
are periods of w, and none of z is a period of
w. The string w 10 is the shortest string for which a setup satisfying the conditions of
Theorem 6.1 can be obtained. The string w 12 is the shortest string for which a setup
that satisfies condition (i), but not condition (ii), of Theorem 6.1 can be obtained.
The two last statements were verified using a computer search.
We next show how to obtain from each setup satisfying the conditions of Theorem
6.1 an infinite sequence of such setups. This helps in the investigation of the
asymptotic number of comparisons required as the length of the pattern strings tends
to infinity. The infinite sequence is obtained by padding the basic setup.
Let u and v be strings. pad(u; v) denotes the string obtained by placing a copy
of v before and after each character of u. Thus pad (121;
general 1. We now have
Theorem 6.2. If hw; z is a setup satisfying the conditions of Theorem
6.1 and if w
Proof. If the setup hw; z satisfies the conditions of Theorem 6.1 then so
does the setup hw ' To see this, note at first that ('
indeed a period of w that none of ('
for i 6= j, is such a period. To verify the first condition of Theorem 6.1, note that
every column in the setup hw ' is either a column of the
or an all-zero column. The second condition is verified in a
similar way. The statement of the Theorem then follows from Theorem 6.1, applied
to and from the fact that 1+ 2
Theorem 6.2 motivates the search for setups hw; z satisfying the conditions
of Theorem 6.1 for which 2(jwj is as high as possible. The best such
setup that we have found with is the following, hw
For this setup, 2(jwj
4 . As a corollary to Theorem 6.2 we obtain
Corollary 6.3. For every there exists a string wm
of length m such that any on-line algorithm that finds all the occurrences of wm in a
text of length n must make at least
comparisons in the worst
case.
Using a computer enumeration we have verified that no better setup with
possible with a pattern of length at most 250. However, better setups that satisfy the
first condition of Theorem 6.1 can be obtained by using four instead of three overlaps.
Let
The following Lemma is easily verified.
Lemma 6.4. The setups hu k
satisfy the first condition of Theorem 6.1.
TIGHTER LOWER BOUNDS ON STRING MATCHING 13
The setup hu 1 ; 20; 29; 32; 34i for example is1211213331211213331212112133312112112112133312112133312121121333121121As ju k we get as a corollary
Corollary 6.5. For every there exists a string
wm(= length m such that any on-line algorithm that uses only pattern-text
comparisons to find all the occurrences of wm in a text of length n must make at least
comparisons in the worst case.
Corollary 6.5 is asymptotically better than Corollary 6.3 and it is the best on-line
bound we have obtained. We have verified using a computer search that no better
setup with four or five overlaps can be obtained using strings of length at most 250.
We believe that if hw; z is a setup satisfying the conditions of Theorem 6.1
then
8 jwj. If this is true, then the result of Corollary 6.5 is essentially the best
that can be obtained using our methods.
7. On-line upper bounds. The next theorem exhibits an interesting family of
strings for which Theorem 5.1 is tight.
Theorem 7.1. For every k; ' - 1 we have c 0 (a k ba '
Proof. The lower bound is a corollary of Theorem 5.1. A matching upper bound
is fairly straightforward for the case k - ', but needs more care when k ? '. We will
describe an algorithm that works in both cases.
Algorithm for a k ba '
The algorithm is described as a sequence of steps, in each of which a text character
is compared to the aligned pattern character. In the case of a mismatch or if an
occurrence of the pattern has been verified, the window is shifted along to the next
position at which a pattern occurrence is possible. We represent the state of the
algorithm before each step by an information string uxv, where u 2 f0; ag k , v 2
ag ' , and x 2 f0; A; bg, describing (part of) the current knowledge the algorithm
has about the text characters in the window. A '0' in the information string indicates
that no information is available on the corresponding position. An 'a' (or a `b')
indicates that the character in that position is known to be an a (or a b). An 'A'
(or a 'B') indicates that the character in the corresponding position is known not to
be an a (or a b). The state can be written in the specified form because, after any
necessary window shift, the information string must be consistent with the pattern.
Our algorithm makes only 'a?' and `b?' queries, and we choose to forget any negative
information represented by 'B'. We shall call the 1)-st position in the window the
b-position and all the others a-positions. An a-position is always queried for an a. A
b-position is always queried for a b.
In terms of the information strings, the algorithm is simply described.
IF there is some 0 in the information string
THEN query the rightmost 0
Ag query the b-position .
14 COLE, HARIHARAN, PATERSON, AND ZWICK
This procedure is repeated until the text string is exhausted. To prove the upper
bound we first establish the following pair of invariants.
Invariants
(i) If
(ii) If does not contain the subword a '+1 .
Invariant (i) holds because x can only become b after an information string of the
form u0a ' , and following any shift we again have x 6= b.
For Invariant (ii), while no tests in u are made, and the only a's shifted
into u come from v. These are separated from the previous contents of u by the 'x'
of the previous information string.
Nearly all comparisons can be associated with text positions in the following way.
Any query made at an a-position is associated with the corresponding text position.
When and the b-position is queried, a b result is associated with that text
position. If the result is B then care is needed since, if ' ! k, this result will be
represented as a 0 in u. However, in this case a shift of size ' +1 will be made and, by
Invariant (ii), at least one 0 will be shifted out from the information string. The query
is associated with the text character corresponding to any one such 0. The remaining
case is when and the b-position is queried. Such a query is not associated with
any text position. We note that after such a query a shift of 1
made, and that the resulting information string will have
is made in any step which changes clearly an accumulative shift of at
least positions must occur between any two such 'extra' queries. The
upper bound follows.
As a corollary we get that Theorem 5.1 is also tight for all members of the a k ba '
family to which it can be applied.
Corollary 7.2. For k; ' - 2 we have c(a k ba '
maxfk;'g+2 .
8. Look-ahead is useful. In this section we present a string matching algo-
rithm, specifically tailored for the string abaa. The algorithm uses a window of size
eight and its performance matches the general lower bound obtained for abaa using
Theorem 4.1. Thus, 8
4 and abaa is therefore a
string for which look-ahead is useful.
The abaa algorithm presented here sheds some light on the intricacy of optimal
string matching algorithms. The description of it is quite complicated. Optimal
algorithms for longer strings may have even more complicated descriptions.
Algorithm for the string abaa
The algorithm requires a window of size 8. A state of the algorithm is given as
an information string oe 2 [ 8
k=1 f0; a; A; b; Bg k , where oe represents information known
about the text symbols in (a prefix of) the window. To describe the algorithm, we
specify for each state the next query to be made, the amount of shift and the next
state corresponding to the two possible answers. We represent a? queries and b?
queries by a single or double underline, respectively, under the appropriate symbol of
the information string. For example, in state P in Table 1, an a? query is made at
the fourth position in the window.
For certain information strings, the task of finding all pattern occurrences decomposes
into two logically disjoint tasks, checking occurrences in some finite prefix and
checking in the remainder. Such a state is represented in the tables by a pair of states
with the connective \Phi. For example, in state R of Table 1, if the seventh symbol is
found not to be an a then it is sufficient to check separately for occurrences within
TIGHTER LOWER BOUNDS ON STRING MATCHING 15
transitions
state inf. & query match mismatch
state shift state shift
R a00a000

Table
The main transition table of the abaa algorithm.
new state
state inf. & query match mismatch worst-case cost
A a0aa
G a00a00a D \Phi B F 4

Table
The secondary transition table of the abaa algorithm.
R
U
4,5
Fig. 5. The transition diagram of the abaa algorithm.
the first five positions (state F ) and in the text string beginning at the sixth position
(state Q).

Table

shows, for each finite subproblem which arises in this way, the next
query to be made and the number of queries required in the worst case to resolve
that subproblem. The latter is computed recursively by following the transitions in

Table

2. A ' p
' in

Table

2 indicates that a full occurrence of the pattern has been found
and the treatment of the current subproblem is finished. A '-' indicates that the
treatment of the current subproblem has ended without finding such an occurrence.
In

Table

1, the main part of the algorithm is presented. The graph showing the
transitions between states of Table 1 is given in Figure 5. The corresponding number
of comparisons to make the transition and finish any consequent subproblem and
the resulting shift is shown on each arrow. It can be verified that the worst case
corresponds to iterating the cycle PRS, and this proves that c 4 (abaa) - 8
7 .
9. Concluding remarks. What is the hardest string to find? The, perhaps
disappointing, answer is aba (or mum and dad and so on). We know that c
3 for any string w ([GG92]). We believe that c
this is not established yet (except for jwj - 8 [CH92]). This would imply
that aba, and its like, are strictly the hardest strings to find. It is interesting to note
that while we have shown here that c
3 , the exact value
of c(aba) is not known yet. We only know that 6
3 .
The task of computing the exact value of c
0 (w) or any of the other three variants,
for every given pattern w, seems at present to be very hard. The constants c
can in principle be computed algorithmically since an on-line algorithm can have only
a finite number of states representing the current information and only a finite number
of possible next queries. Among optimal on-line algorithms for each w, there are some
in which the next query depends only on the information state, and there is only a
finite, though huge, number of different algorithms of this kind for every w. The task
of finding c(w) and c   (w) may be even harder. We do not know at present whether
c(w) and c   (w) are always rational, although it would be very odd if they were not.
A small gap still remains between our lower bounds and the upper bounds of
Cole and Hariharan [CH92]. While closing this gap will have no practical value, we
think that it may reveal many interesting properties of strings and string matching
algorithms.

Acknowledgment

. The authors thank an anonymous referee for suggestions
which improved the paper.



--R

Algorithms for finding patterns in strings
The Boyer-Moore-Galil string searching strategies revisited
Optimal canonization of all substrings of a string
Analysis of Boyer-Moore type string searching algorithms
Efficient comparison based string matching
A fast string matching algorithm
Tight bounds on the complexity of the Boyer-Moore algorithm
Correctness and efficiency of pattern matching algorithms
Tighter upper bounds on the comparison complexity of string matching
Which patterns are hard to find?
On the Exact Complexity of String Matching
Speeding Up Two String-Matching Algorithms
On the Exact Complexity of String Matching: Lower Bounds
On the Exact Complexity of String Matching: Upper Bounds
A new proof of the linearity of the Boyer-Moore string searching algorithm

Fast pattern matching in strings
--TR
string matching;complexity;lower bounds;comparisons;pattern matching