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