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