Considere a cadeia de DNA
ACACAGAACTTGGCACACGAACGGTC} e o padrão
{ACACGAA}. Mostre o passo a passo da execução do algoritmo KMP para esta instância do problema.
Passo 1
O enunciado pede pra gente rodar o algoritmo KMP (Knuth–Morris–Pratt) pra encontrar o padrão
dentro do texto
Conteúdo: busca de padrão em string usando tabela de prefixos (“lps” ou “π”).
O que vamos precisar:
O que vamos precisar:
- Construir o vetor lps (ou π) do padrão, onde
- Fazer o “pulo” em caso de mismatch usando esse lps.
Passo 2
Construindo o vetor lps pra P = A C A C G A A (índices 0…6):
Definimos j = 0 (tamanho atual do prefixo) e lps[0] = 0.
Para cada i de 1 a 6:
i=1 ©: P[1]≠P[0], não há prefixo→ lps[1]=0.
i=2 (A): P[2]=P[0]=A → j=1 → lps[2]=1.
i=3 ©: P[3]=P[1]=C → j=2 → lps[3]=2.
i=4 (G): P[4]≠P[2]=A → j=lps[1]=0; P[4]≠P[0] → lps[4]=0.
i=5 (A): P[5]=P[0]=A → j=1 → lps[5]=1.
i=6 (A): P[6]≠P[1]=C → j=lps[0]=0; P[6]=P[0]=A → j=1 → lps[6]=1.
Para cada i de 1 a 6:
i=1 ©: P[1]≠P[0], não há prefixo→ lps[1]=0.
i=2 (A): P[2]=P[0]=A → j=1 → lps[2]=1.
i=3 ©: P[3]=P[1]=C → j=2 → lps[3]=2.
i=4 (G): P[4]≠P[2]=A → j=lps[1]=0; P[4]≠P[0] → lps[4]=0.
i=5 (A): P[5]=P[0]=A → j=1 → lps[5]=1.
i=6 (A): P[6]≠P[1]=C → j=lps[0]=0; P[6]=P[0]=A → j=1 → lps[6]=1.
Resultado final:
Passo 3
Agora rodada sobre T com índices i (texto) e j (padrão), iniciando em i=0, j=0:
- i=0,j=0: T[0]=A=P[0] → i=1,j=1
- i=1,j=1: C=C → i=2,j=2
- i=2,j=2: A=A → i=3,j=3
- i=3,j=3: C=C → i=4,j=4
- i=4,j=4: T[4]=A≠P[4]=G → mismatch → j = lps[j-1] = lps[3] = 2
comparar de novo com j=2:
T[4]=A=P[2] → i=5,j=3 - i=5,j=3: T[5]=G≠P[3]=C → j=lps[2]=1; comparar j=1: G≠P[1]=C → j=lps[0]=0;
agora j=0: G≠P[0]=A → i=6,j=0 - i=6,j=0: A=A → i=7,j=1
- i=7,j=1: A≠P[1]=C → j=lps[0]=0; então A=P[0] → i=8,j=1
- i=8,j=1: C=C → i=9,j=2
- i=9,j=2: T=T≠P[2]=A → j=lps[1]=0; T≠P[0] → i=10,j=0
Dali em diante nada “cola” até chegarmos em i=14:
Passo 4
Retomando em i=14,j=0:
i=14: A=A → i=15,j=1
i=15: C=C → i=16,j=2
i=16: A=A → i=17,j=3
i=17: C=C → i=18,j=4
i=18: G=G → i=19,j=5
i=19: A=A → i=20,j=6
i=20: A=A → i=21,j=7 = |P| → padrão completo encontrado!
i=14: A=A → i=15,j=1
i=15: C=C → i=16,j=2
i=16: A=A → i=17,j=3
i=17: C=C → i=18,j=4
i=18: G=G → i=19,j=5
i=19: A=A → i=20,j=6
i=20: A=A → i=21,j=7 = |P| → padrão completo encontrado!
A posição de início no texto é i − j = 21 − 7 = 14 (0-based).
Resposta
O padrão “ACACGAA” ocorre em T começando na posição 15 (1-based), isto é, no índice 14 do texto (0-based).