Compute a tabela de prefixos pi para o padrão ababbabbabbababbabb.

Passo 1

O enunciado pede para calcular a tabela de prefixos pi do padrão
P = ababbabbabbababbabb
Isso é parte do algoritmo KMP (Knuth–Morris–Pratt) em que a função pi[i] indica o tamanho do maior sufixo próprio de P[1i] que é também um prefixo de P.
Para resolver isso a gente vai:
1. Entender a definição de pi[i].
2. Percorrer o padrão de i=1 até i=n calculando cada pi[i] passo a passo, usando valores já computados (o “fallback” via pi[i-1],pi[dots]).

Passo 2

Teoria rápida (sem pular etapas):
  • pi[1] = 0 por definição (não existe sufixo próprio não vazio em um único caractere).
  • Para i>1, a gente tenta estender o maior prefixo-sufixo de comprimento k = pi[i-1].
    1. Se P[k+1] = P[i], então pi[i] = k+1.
    2. Senão, a gente reduz k pi[k] até achar um k tal que P[k+1]=P[i] ou k=0.
    3. Se chegou em k=0 e não bate, pi[i]=0.

Passo 3

Vamos indexar P de 1 a 19. Para lembrar, os primeiros caracteres são:
i: 1 2 3 4 5 6 7 8 …
P[i]: a b a b b a b b …
  • pi[1]=0
  • i=2: k=pi[1]=0. Compara P[1]=a vs P[2]=b → não bate → pi[2]=0.
  • i=3: k=0. Compara P[1]=a vs P[3]=a → bate → pi[3]=1.
  • i=4: k=pi[3]=1. Compara P[2]=b vs P[4]=b → bate → pi[4]=2.
  • i=5: k=pi[4]=2. Compara P[3]=a vs P[5]=b → falha →
    fallback k=pi[2]=0. Compara P[1]=a vs P[5]=b → falha → pi[5]=0.

Passo 4

Continuando para i=6…10:
  • i=6: k=0, P[1]=a vs P[6]=a pi[6]=1.
  • i=7: k=1, P[2]=b vs P[7]=b pi[7]=2.
  • i=8: k=2, P[3]=a vs P[8]=b → fallback a k=0 P[1]=a vs P[8]=b pi[8]=0.
  • i=9: k=0, P[1]=a vs P[9]=a pi[9]=1.
  • i=10: k=1, P[2]=b vs P[10]=b pi[10]=2.

Passo 5

Para i=11…15:
  • i=11: k=2, P[3]=a vs P[11]=b → fallback k=0 pi[11]=0.
  • i=12: k=0, P[1]=a vs P[12]=a pi[12]=1.
  • i=13: k=1, P[2]=b vs P[13]=b pi[13]=2.
  • i=14: k=2, P[3]=a vs P[14]=a pi[14]=3.
  • i=15: k=3, P[4]=b vs P[15]=b pi[15]=4.

Passo 6

E finalmente i=16…19:
  • i=16: k=4, P[5]=b vs P[16]=b pi[16]=5.
  • i=17: k=5, P[6]=a vs P[17]=a pi[17]=6.
  • i=18: k=6, P[7]=b vs P[18]=b pi[18]=7.
  • i=19: k=7, P[8]=b vs P[19]=b pi[19]=8.

Resposta

A tabela completa pi[119] é:
[0,,0,,1,,2,,0,,1,,2,,0,,1,,2,,0,,1,,2,,3,,4,,5,,6,,7,,8]

Exercícios relacionados