The Prague Stringology Club Workshop '97
Bruce W. Watson and Richard E. Watson
A New Family of String Pattern Matching Algorithms
| Abstract: |
| Even though the field of pattern matching has been well studied, there are still many interesting algorithms to be discovered. In this paper, we present a new family of single keyword pattern matching algorithms. We begin by deriving a common ancestor algorithm, which naively solves the problem. Through a series of correctness preserving predicate strengthenings, and implementation choices, we derive efficient variants of this algorithm. This paper also presents one of the first algorithms which could be used to do a minimal number of match attempts within the input string (by maintaining as much information as possible from each match attempt). |
| Download paper: |  |
 |
| PostScript |