Saving Comparisons in the Crochemore-Perrin String Matching Algorithm

Crochemore and Perrin discovered an elegant linear-time constant-space string matching algorithm that makes at most 2n \Gamma m symbol comparison. This paper shows how to modify their algorithm to use fewer comparisons. Given any fixed ffl ? 0, the new algorithm takes linear time, uses constant space and makes at most n + b 1+ffl 2 (n \Gamma m)c symbol comparisons. If O(log m) space is available, then the algorithm makes at most n + b 1 2 (n \Gamma m)c symbol comparisons. The pattern preprocessing step also takes linear time and uses constant space. These are the first string matching algorithms that make fewer than 2n \Gamma m symbol comparisons and use sub-linear space. 1 Introduction String matching is the problem of finding all occurrences of a short string P[1::m] that is called a pattern in a longer string T [1::n] that is called a text. In this paper we study the exact comparison complexity of the string matching problem. We usually assume that the only access the algorithm..