DIMACS TR: 94-54

Simple Uniform Preprocessing for Linear-time Pattern Matching

Author: Dan Gusfield


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