A New Family of String Pattern Matching Algorithms.
Bruce W. Watson, Richard E. Watson · TU/e Research Portal · 1997
Abstract. Even though the eld 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 navely solves the problem. Through a series of correctness preserving predicate strengthenings, and imple-mentation choices, we derive ecient variants of this algorithm. This paper also presents one of the rst 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).