TY - JOUR AU - Breslauer, Dany AU - Colussi, Livio AU - Toniolo, Laura PY - 1995/06/16 Y2 - 2024/03/28 TI - On the Comparison Complexity of the String Prefix-Matching Problem JF - BRICS Report Series JA - BRICS VL - 2 IS - 46 SE - Articles DO - 10.7146/brics.v2i46.19947 UR - https://tidsskrift.dk/brics/article/view/19947 SP - AB - In this paper we study the exact comparison complexity of the string<br />prefix-matching problem in the deterministic sequential comparison model<br />with equality tests. We derive almost tight lower and upper bounds on<br />the number of symbol comparisons required in the worst case by on-line<br />prefix-matching algorithms for any fixed pattern and variable text. Unlike<br />previous results on the comparison complexity of string-matching and<br />prefix-matching algorithms, our bounds are almost tight for any particular pattern.<br />We also consider the special case where the pattern and the text are the<br />same string. This problem, which we call the string self-prefix problem, is<br />similar to the pattern preprocessing step of the Knuth-Morris-Pratt string-matching<br />algorithm that is used in several comparison efficient string-matching<br />and prefix-matching algorithms, including in our new algorithm.<br />We obtain roughly tight lower and upper bounds on the number of symbol<br />comparisons required in the worst case by on-line self-prefix algorithms.<br />Our algorithms can be implemented in linear time and space in the<br />standard uniform-cost random-access-machine model. ER -