Saving comparisons in the Crochemore-Perrin string matching algorithm
| Author(s) : | Dany Breslauer, |
| Publisher : | N/A |
| Publication Date : | 1996 |
| ISSN : | N/A |
| Abstract : | 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 modified algorithm takes linear time, uses constant space and makes at most n+ b, |