Time-space-optimal string matching

摘要

Any string-matching algorithm requires at least linear time and a constant number of local storage locations. We design and analyze an algorithm which realizes both asymptotic bounds simultaneously. This can be viewed as completely eliminating the need for the tabulated “failure function” in the linear-time algorithm of Knuth, Morris, and Pratt. It makes possible a completely general implementation as a Fortran subroutine or even as a six-head finite automaton.