HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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 [??] the new algorithm takes linear time, uses constant space and makes at most [??] symbol comparisons. If O(log m) space is available, then the algorithm makes at most [??] symbol comparisons. The pattern preprocessing step also takes linear time and uses constant space. These are the first string matching algorithms that make fewer then 2n - m symbol comparisons and use sub-linear space.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 3:42:10 PM
Last modification on : Friday, February 4, 2022 - 3:16:59 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 3:50:52 PM


  • HAL Id : inria-00074535, version 1



Dany Breslauer. Saving comparisons in the Crochemore-Perrin string matching algorithm. [Research Report] RR-2137, INRIA. 1993. ⟨inria-00074535⟩



Record views


Files downloads