Algoritmo de Knuth-Morris-Pratt

Um algoritmo de comparação de strings procura um índice m em uma string S, onde se encontra a string W.

Um algoritmo simples para encontrar a resposta é procurar na string S pelo primeiro caracter da string W. Uma vez que os caracteres coincidem comparam-se os caracteres subsequentes, se um for diferente, a comparação inicia-se novamente pelo primeiro caracter de W, comparando-o com o próximo caracter de S.

Embora o custo de execução deste algoritmo seja O(N), ou seja, N comparações de caracteres, onde N é o tamanho da string S, no pior caso, o algoritmo executa N * k (O(Nk)) comparações, onde k é o tamanho da string W.

O algoritmo de Knuth-Morris-Pratt (KMP), foi desenvolvido por Donald Knuth, e Vaughan Pratt, e independentemente, por James H. Morris. Os três publicaram um artigo descrevendo o algoritmo em 1977. O algoritmo utiliza informações das comparações anteriores para diminuir o número total de comparações, reduzindo o custo do algoritmo, no pior caso, para O(N + k).

O algoritmo KMP utiliza uma função de falha que pré-calcula quanto a string W deve ser movida em relação a string S quando a comparação dos caracteres falhar. Com esse avanço maior da string, o número de comparações é reduzido, pois não é necessário comparar novamente os caracteres do início da string W, quando existe repetição do prefixo no meio (ou final) da string.

Quando o tamanho do alfabeto utilizado aumenta, aumenta também a chance de que a comparação dos caracteres falhe, diminuindo a eficiência do algoritmo.

Exemplo do algoritmo

Para entender melhor o algoritmo, acompanhe um exemplo de execução do mesmo, para as seguintes strings:

S = bacbabababacaab
W = ababaca

Ao iniciar a comparação, os caracteres na primeira posição das duas strings são diferentes. Dessa forma, a próxima etapa de comparação começará pelo segundo caracter da string S, porém, recomeçará pelo primeiro caracter da string W.

S = bacbabababacaab
W = ababaca

Ao comparar o segundo caracter de W com o terceiro caracter de S, os caracteres não são iguais. No entanto, como o erro ocorreu apenas no segundo carcter de W, não há informação suficiente que se possa aproveitar para diminuir o número de comparações futuras, então a procura recomeçará com o primeiro caracter de W e o terceiro caracter de S.

S = bacbabababacaab
W =  ababaca

Nas próximas duas rodadas de comparação, apesar de haver caracteres iguais na seqüência das strings, o primeiro caracter de W não encontra correspondência com o caracter sendo comparado em S, portanto, só é possível avançar um caracter em S.

S = bacbabababacaab
W =   ababaca

S = bacbabababacaab
W =    ababaca

Novamente, a diferença ocorre no segundo caracter, não sendo possível aproveitar as comparações já realizadas.

S = bacbaabababacaab
W =     ababaca

Neste ponto da execução do algoritmo, foi possível comparar até o sexto caracter da string W, quando ocorre a diferença dos caracteres. Nesta posição, o algoritmo pode utilizar a informação das comparações anteriores, e não precisa começar a comparação pelo primeiro caracter de W, mas pode assumir que os três primeiros caracteres são iguais, e recomeçar a comparação apenas a partir do quarto caracter.

S = bacbaabababacaab
W =      ababaca

Sabendo qual caracter ocasionou o resultado negativo da comparação, é possível saber que existe um sufixo no padrão sendo procurado, que equivale a um prefixo do padrão, nesse exemplo, a substring aba, possibilitando assim que não seja necessário comparar novamente os primeiros caracteres do padrão.

S = bacbaabababacaab
W =        ababaca

Nesse ponto da comparação, todos os caracteres da string W possuem equivalente na string S, encontrando um resultado que é o índice do primeiro caractere que se alinha com o padrão.

S = bacbaabababacaab
W =        ababaca

Pseudo-código do algoritmo Knuth-Morris-Pratt

O Algoritmo 1 mostra o psedo-código da pesquisa de string utilizando o algoritmo de Knuth-Morris-Pratt.

Pesquisa utilizando o algoritmo Knuth-Morris-Pratt.

algorithm kmp_search(S, W):
   m = 0
   i = 0
   T = kmp_table(W)

   while m + i < S.length:
       if W[i] == S[m + i]:
           if i == W.length - 1:
               return m
           i++
       else:
           if T[i] > -1:
               m += i - T[i]
               i = T[i]
           else:
               m++
               i = 0

   error "String not found"

Para que o algoritmo KMP possa ser utilizado, é necessária a criação da tabela de falha de comparação de caracteres, fornecida pela função kmp_table(), utilizada no algoritmo anterior. Essa função é descrita no Algoritmo 2.

Construção da tabela de falha do algoritmo Knuth-Morris-Pratt.

algorithm kmp_table(W):
   T = int[W.length]
   T[0] = -1
   T[1] = 0

   pos = 2
   candidate = 0

   while pos < W.length do
       if W[pos-1] == W[candidate]:
           candidate++
           T[pos] = candidate
           pos++
       else:
          if candidate > 0:
              candidate = T[candidate]
          else:
              T[pos] = 0
              pos++