Considere a cadeia de DNA T= ACACAGAACTTGGCACACGAACGGTC} e o padrão P = {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
P = ACACGAA
dentro do texto
T = ACACAGAACTTGGCACACGAACGGTC
Conteúdo: busca de padrão em string usando tabela de prefixos (“lps” ou “π”).
O que vamos precisar:
  • Construir o vetor lps (ou π) do padrão, onde
lps[i] = maior tamanho de um prefixo próprio de P[0i] que seja também sufixo óé
  • 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.
Resultado final:
lps = [0,;0,;1,;2,;0,;1,;1]

Passo 3

Agora rodada sobre T com índices i (texto) e j (padrão), iniciando em i=0, j=0:
  1. i=0,j=0: T[0]=A=P[0] → i=1,j=1
  2. i=1,j=1: C=C → i=2,j=2
  3. i=2,j=2: A=A → i=3,j=3
  4. i=3,j=3: C=C → i=4,j=4
  5. 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
  6. 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
  7. i=6,j=0: A=A → i=7,j=1
  8. i=7,j=1: A≠P[1]=C → j=lps[0]=0; então A=P[0] → i=8,j=1
  9. i=8,j=1: C=C → i=9,j=2
  10. 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!
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).

Exercícios relacionados