On the Comparison Complexity of the String Prefix-Matching Problem
Dany Breslauer August 1995 |

## 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 Our algorithms can be implemented in linear time and space in the standard uniform-cost random-access-machine model.
Available as |

Last modified: 2003-06-08 by webmaster.