In this paper we study the exact comparison complexity of the string p
refix-matching problem in the deterministic sequential comparison mode
l with equality tests, We derive almost tight lower and upper bounds o
n the number of symbol comparisons required in the worst case by on-li
nt prefix-matching algorithms for any fixed pattern and variable text.
Unlike previous results on the comparison complexity of string-matchi
ng and prefix-matching algorithms, our bounds are almost tight for any
particular pattern. We also consider the special case where the patte
rn and the text are the same string. This problem, which we call the s
tring self-prefix problem, is similar to the pattern preprocessing ste
p of the Knuth-Morris-Pratt string-matching algorithm that is used in
several comparison efficient string-matching and prefix-matching algor
ithms, including in our new algorithm. We obtain roughly tight lower a
nd upper bounds cn the number of symbol comparisons required in the wo
rst case by on-line self-prefix algorithms. Our algorithms can be impl
emented in linear time and space in the standard uniform cost random-a
ccess-machine model. (C) 1998 Academic Press.