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 - m symbol comparison s. This paper shows how to modify their algorithm to use fewer compari sons. Given any fixed epsilon > 0, the new algorithm takes linear time , uses constant space and makes at most n + right perpendicular 1+epsi lon/2(n - m) left perpendicular symbol comparisons. If O(log m) space is available, then the algorithm makes at most n + right perpendicular 1/2(n - m) left perpendicular symbol comparisons. The pattern preproc essing step also takes linear time and uses constant space. These are the first string-matching algorithms that make fewer than 2n-m symbol comparisons and use sub-linear space.