On the Comparison Complexity of the String Prefix-Matching Problem

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 string-matching
algorithm that is used in several comparison efficient string-matching
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.