String matching is the classical problem of finding all occurrences of a pattern in a text. A real-time string matching algorithm takes worst-case constant-time to check if a pattern occurrence ends at each text location. We derive a real-time variation of the elegant Crochemore–Perrin constant-space string matching algorithm that has a simple and efficient control structure. We use observations about the locations of critical factorizations to deploy two tightly-coupled simplified real-time instances of the Crochemore–Perrin algorithm that search for complementary parts of the pattern whose simultaneous occurrence indicates an occurrence of the complete pattern.

Simple real-time constant-space string matching

MIGNOSI, FILIPPO
2013

Abstract

String matching is the classical problem of finding all occurrences of a pattern in a text. A real-time string matching algorithm takes worst-case constant-time to check if a pattern occurrence ends at each text location. We derive a real-time variation of the elegant Crochemore–Perrin constant-space string matching algorithm that has a simple and efficient control structure. We use observations about the locations of critical factorizations to deploy two tightly-coupled simplified real-time instances of the Crochemore–Perrin algorithm that search for complementary parts of the pattern whose simultaneous occurrence indicates an occurrence of the complete pattern.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/16810
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 4
social impact