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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.tcs.2012.11.040 | Theoretical Computer Science |
DocType | Volume | ISSN |
Journal | 483 | 0304-3975 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dany Breslauer | 1 | 346 | 26.19 |
Roberto Grossi | 2 | 581 | 57.47 |
Filippo Mignosi | 3 | 569 | 99.71 |