Fast Pattern Matching in Strings
1977; Society for Industrial and Applied Mathematics; Volume: 6; Issue: 2 Linguagem: Inglês
10.1137/0206024
ISSN1095-7111
AutoresDonald E. Knuth, James H. Morris, Vaughan Pratt,
Tópico(s)semigroups and automata theory
ResumoAn 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.
Referência(s)