Fast Pattern Matching in Strings.

摘要

An algorithm is presented which finds all occurrences of one given string within another,in running time proportional to the sum of the lengths of the strings. The constant of proportionality is low enough to make this algorithm of practical use,and the procedure can also be extended to deal with some more general pattern-matching problems. A theoretical application of the algorithm shows that the set of concatenations of even palindromes, i.e.,the language (alpha(alpha sup R))*,can be recognized in linear time.