Saving Comparisons in the Crochemore-Perrin String Matching Algorithm

摘要: Abstract: "Crochemore and Perrin discovered an elegant linear- time constant-space string matching algorithm that makes at most 2n - m symbol comparison. This paper shows how to modify their algorithm to use fewer comparisons. Given any fixed [element]> 0, the new algorithm takes linear time, uses constant space, and makes at most [formula] symbol comparisons. If O(log m) space is available, then the algorithm makes at most [formula] 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 - m symbol comparisons and use sub-linear space."