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 ←length [P] //'p' pattern to be matched 2. Π [1] ← 0 3. k ← 0 4. for q ← 2 to m 5. do while k > 0 and P [k + 1] ≠ P [q] 6. do k ← Π [k] 7. If P [k + 1] = P [q] 8. then k← k + 1 9. Π [q] ← k 10. Return Π
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 ← length [T] 2. m ← length [P] 3. Π← COMPUTE-PREFIX-FUNCTION (P) 4. q ← 0 // numbers of characters matched 5. for i ← 1 to n // scan S from left to right 6. do while q > 0 and P [q + 1] ≠ T [i] 7. do q ← Π [q] // next character does not match 8. If P [q + 1] = T [i] 9. then q ← q + 1 // next character matches 10. If q = m // is all of p matched? 11. then print 'Pattern occurs with shift' i - m 12. q ← Π [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.