DIMACS TR: 94-54
Simple Uniform Preprocessing for Linear-time Pattern Matching
Author: Dan Gusfield
ABSTRACT
We show that a simple algorithm developed first in \cite{MLZ} can be
used to provide a uniform linear-time preprocessing method for a
variety of linear- time pattern matching algorithms. Most notably
this yields a simple, understandable linear-time preprocessing method
for the {\it strong} good- suffix shift rule in the Boyer-Moore
algorithm. We know of no other correct, fully explained method for the
strong rule that has been published. In addition, this approach yields
a related method for strong preprocessing of the Knuth-Morris-Pratt
algorithm, for real-time finite-state-machine matching, and for a
modification of a ``Boyer-Moore-like" algorithm due to Apostolico and
Giancarlo that is closer to the true Boyer-Moore and yet allows a
simple proof of linear worst case running time.
Paper only.
DIMACS Home Page