n South African Computer Journal - A new family of string pattern matching algorithms : research article
|Article Title||A new family of string pattern matching algorithms : research article|
|© Publisher:||South African Computer Society (SAICSIT)|
|Journal||South African Computer Journal|
|Author||B.W. Watson and R.E. Watson|
|Publication Date||Jun 2003|
|Pages||34 - 41|
|Keyword(s)||D.1.4, E.1, F.2.2, G.2.2, Match attempts, Predicate strengthening and weakening, Reusing match information, Shift distances and Single keyword pattern matching|
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 naïvely 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).
Article metrics loading...