Fast Pattern Matching in Strings
Donald E. Knuth, James H. Morris, Vaughan Pratt · SIAM Journal on Computing · 1977
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 ^R\}^*$, can be recognized in linear time. Other algorithms which run even faster on the average are also considered.
Cited by 2,936 works. doi:10.1137/0206024
Authors
References
- The Design and Analysis of Computer Algorithms
- Fast Pattern Matching in Strings
- Efficient string matching
- The art of computer programming. Vol.1: Fundamental algorithms
- On the translation of languages from left to right
- Structured Programming with go to Statements
- STRING-MATCHING AND OTHER PRODUCTS
- Linear Time Simulation of Deterministic Two-Way Pushdown Automata.
- Rapid identification of repeated patterns in strings, trees and arrays
- Programming Techniques: Regular expression search algorithm