TIGHT COMPARISON BOUNDS FOR THE STRING PREFIX-MATCHING PROBLEM

In the string prefix-matching problem one is interested in finding the longest prefix of a pattern string of length m that occurs starting a t each position of a text string of length n. This is a natural genera lization of the string matching problem where only occurrences of the whole pattern are sought. The Knuth-Morris-Pratt string matching algor ithm can be easily adapted to solve the string prefix-matching problem without making additional comparisons. In this paper we study the exa ct complexity of the string prefix-matching problem in the determinist ic sequential comparison model. Our bounds do not account for comparis ons made in a pattern preprocessing step. The following results are pr esented: (1) A family of linear-time string prefix-matching algorithms that make at most [((2m - 1)/ m)n left perpendicular comparisons. (2) A tight lower bound of [((2m - 1)/m)n left perpendicular comparisons for any string prefix-matching algorithm that has to match the pattern 'ab(m - 1)'. We also consider the special case when the pattern and t he text strings are the same string and all comparisons are accounted. This problem, which we call the string self-prefix problem, is simila r to the failure function that is computed in the pattern preprocessin g of the Knut-Morris-Pratt string matching algorithm and used in sever al other comparison efficient algorithms. By using the lower bound for the string prefix-matching problem we are able to show: (3) A lower b ound of 2m - right perpendicular 2 square-root m left perpendicular co mparisons for the self-prefix problem.