Fast Pattern Matching in Strings

作     者：Donald E. Knuth James H. Morris, Jr. Vaughan R. Pratt 

出 版 物：《SIAM Journal on Computing》 

年 卷 期：1977年第6卷第2期

页      面：323-350页

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：pattern string text-editing pattern-matching trie memory searching period of a string palindrome optimum algorithm Fibonacci string regular expression 

摘      要：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 {R} role=presentation{ααspan style=positio