Casamento de Padrões KMP

Prévia do material em texto

Casamento de Padrões 
Algoritmo Knuth-Morris-Pratt 
Algoritmo KMP 
 Leitura dos caracteres do texto, um a um, da esquerda 
pra direita 
 Primeiro algoritmo cujo tempo é O(n) 
 Pré-processamento do padrão: calcula deslocamentos 
em função apenas do próprio padrão 
 Compara o padrão com ele próprio 
 Por exemplo, suponha P = ababaca e que os 5 primeiros 
caracteres do padrão casaram com o texto mas houve uma 
colisão no 6º caracter 
 Você pode dizer que deslocar somente um caracter para direita não vai 
funcionar (por quê?) 
 O próximo deslocamente a ser testado desloca o padrão 2 caracteres para 
direita 
Cálculo da função prefixo  
 O pré-processamento do padrão leva ao cálculo de [q], 
q=1...m 
 
 [q] = max {k: k < q e Pk ] Pq } 
 
Ou seja [q] é o tamanho do prefixo mais longo 
de P que é um sufixo próprio de Pq 
 
Cálculo da função prefixo : Exemplo 
• Seja o padrão P = ababababca, vamos calcular [q] 
[1] = 0 (q = 1 -> k < q -> k= 0) 
[2] = 0 (P2 = ab -> não existe nenhum prefixo que é sufixo de P2) 
[3] = 1 (P3 = aba -> maior prefixo que é sufixo de P3 é P1 = a) 
[4] = 2 (P4 = abab -> maior prefixo é P2 = ab) 
[5] = 3 (P5 = ababa -> maior prefixo é P3 = aba) 
[6] = 4 (P6 = ababab -> maior prefixo é P4 = abab) 
[7] = 5 (P7 = abababa -> maior prefixo é P5 = ababa) 
[8] = 6 (P8 = abababab -> maior prefixo é P6 = ababab) 
[9] = 0 (P9 = ababababc -> não existe nenhum prefixo que é sufixo) 
[10] = 1 (P10 = ababababca -> maior prefixo é P1 = a) 
 
 
Função prefixo  
5 
Exemplo de Aplicação do Algoritmo 
 i = 1 2 3 4 5 6 7 8 9 10 
P[i] = a b a b a b a b c a 
 [i] = -1 0 0 1 2 3 4 5 6 0 1 
 
Deslocamento: s = (q - [q]) -> q caracteres já casaram 
 abacababababcabababa 
 ababababca s = (3 - [3]) = 3 -1 = 2 
 ababababca s = (1 - [1]) = 1 – 0 = 1 
 ababababca s = (0 - [0]) = 0 – (-1) = 1 
 ababababca s = (10 - [10]) = 10 – 1 = 9 
 ababababaca