Simple real-time constant-space string matching

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.

Authors

• Dany Breslauer
• Roberto Grossi
• Filippo Mignosi

Keywords

No keywords are indexed for this paper.