Algoritmo de Knuth-Morris-Pratt
O algoritmo de Knuth–Morris–Pratt procura a ocorrência de uma "palavra" W
dentro de um "texto" S
empregando a simples técnica de que quando aparece uma diferença, a palavra tem em si a informação necessária para determinar onde começar a próxima comparação.
O algoritmo foi inventado por Donald Knuth e Vaughan Pratt e independentemente por James Morris em 1977, embora os três tenham-no publicado conjuntamente.
Exemplo:
abcdabd
0 - sempre começa com 0
00 - na substring "ab" não há prefixo e sufixo próprios iguais
000 - idem para "abc"
0000 - idem para "abcd"
00001 - na substring "abcda", o prefixo próprio "a", que inicia a substring, é igual ao sufixo próprio "a", que termina a substring
000012 - na substring "abcdab", o prefixo próprio "ab", que inicia a substring, é igual ao sufixo próprio "ab", que termina a substring
0000120 - na substring "abcdabd" não há prefixo e sufixo próprios iguais
![]() | Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.
|