Knuth-Morris e Pratt apresentam um algoritmo de tempo linear para o problema de correspondência de strings. Um tempo de casamento de O(n) é conseguido evitando a comparação com um elemento de 'S' que tenha sido previamente envolvido em comparação com algum elemento do padrão 'p' a ser casado. ou seja, o retrocesso na string 'S' nunca ocorre

Componentes do algoritmo KMP:

1. A função de prefixo (Π): A função de prefixo, Π para um padrão encapsula o conhecimento sobre como o padrão corresponde à mudança de si mesmo. Esta informação pode ser usada para evitar uma mudança inútil do padrão 'p.' Em outras palavras, isso permite evitar o retrocesso da string 'S.'

2. As correspondências KMP: Com a string 'S', o padrão 'p' e a função de prefixo 'Π' como entradas, encontre a ocorrência de 'p' em 'S' e retorne o número de deslocamentos de 'p' após os quais as ocorrências são encontradas.

A função de prefixo (Π)

O pseudocódigo a seguir calcula a função de prefixo, Π:

 <strong>COMPUTE- PREFIX- FUNCTION (P)</strong> 1. m &#x2190;length [P] //&apos;p&apos; pattern to be matched 2. &#x3A0; [1] &#x2190; 0 3. k &#x2190; 0 4. for q &#x2190; 2 to m 5. do while k &gt; 0 and P [k + 1] &#x2260; P [q] 6. do k &#x2190; &#x3A0; [k] 7. If P [k + 1] = P [q] 8. then k&#x2190; k + 1 9. &#x3A0; [q] &#x2190; k 10. Return &#x3A0; 

Análise do tempo de execução:

No pseudocódigo acima para calcular a função de prefixo, o loop for da etapa 4 à etapa 10 é executado 'm' vezes. Step1 a Step3 levam tempo constante. Portanto, o tempo de execução da função de prefixo de cálculo é O (m).

Exemplo: Calcule Π para o padrão 'p' abaixo:

arraylist e lista vinculada

Solução:

 Initially: m = length [p] = 7 Π [1] = 0 k = 0 

Após a iteração 6 vezes, o cálculo da função de prefixo está completo:

O KMP corresponde:

O KMP Matcher com o padrão 'p', a string 'S' e a função de prefixo 'Π' como entrada, encontra uma correspondência de p em S. O pseudocódigo a seguir calcula o componente de correspondência do algoritmo KMP:

 <strong>KMP-MATCHER (T, P)</strong> 1. n &#x2190; length [T] 2. m &#x2190; length [P] 3. &#x3A0;&#x2190; COMPUTE-PREFIX-FUNCTION (P) 4. q &#x2190; 0 // numbers of characters matched 5. for i &#x2190; 1 to n // scan S from left to right 6. do while q &gt; 0 and P [q + 1] &#x2260; T [i] 7. do q &#x2190; &#x3A0; [q] // next character does not match 8. If P [q + 1] = T [i] 9. then q &#x2190; q + 1 // next character matches 10. If q = m // is all of p matched? 11. then print &apos;Pattern occurs with shift&apos; i - m 12. q &#x2190; &#x3A0; [q] // look for the next match 

Análise do tempo de execução:

O loop for que começa na etapa 5 é executado 'n' vezes, ou seja, enquanto o comprimento da string 'S.' Como as etapas 1 a 4 levam tempos constantes, o tempo de execução é dominado por isso para o loop. Assim, o tempo de execução da função correspondente é O (n).

Exemplo: Dada uma string 'T' e um padrão 'P' da seguinte forma:

Vamos executar o algoritmo KMP para descobrir se 'P' ocorre em 'T'.

Para 'p' a função de prefixo, ? foi calculado anteriormente e é o seguinte:

Solução:

 Initially: n = size of T = 15 m = size of P = 7 

Descobriu-se que o padrão 'P' apresenta complexidade em uma string 'T'. O número total de turnos que ocorreram para que a correspondência fosse encontrada é i-m = 13 - 7 = 6 turnos.