Compute a tabela de prefixos
para o padrão ababbabbabbababbabb.
Passo 1
O enunciado pede para calcular a tabela de prefixos
do padrão
Isso é parte do algoritmo KMP (Knuth–Morris–Pratt) em que a função
Para resolver isso a gente vai:
1. Entender a definição de
2. Percorrer o padrão de
Passo 2
Teoria rápida (sem pular etapas):
-
por definição (não existe sufixo próprio não vazio em um único caractere). - Para
, a gente tenta estender o maior prefixo-sufixo de comprimento . - Se
, então . - Senão, a gente reduz
até achar um tal que ou . - Se chegou em
e não bate, .
- Se
Passo 3
Vamos indexar
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 …
i: 1 2 3 4 5 6 7 8 …
P[i]: a b a b b a b b …
-
- i=2:
. Compara vs → não bate → . - i=3:
. Compara vs → bate → . - i=4:
. Compara vs → bate → . - i=5:
. Compara vs → falha →
fallback. Compara vs → falha → .
Passo 4
Continuando para i=6…10:
- i=6:
, vs → . - i=7:
, vs → . - i=8:
, vs → fallback a → vs → . - i=9:
, vs → . - i=10:
, vs → .
Passo 5
Para i=11…15:
- i=11:
, vs → fallback → . - i=12:
, vs → . - i=13:
, vs → . - i=14:
, vs → . - i=15:
, vs → .
Passo 6
E finalmente i=16…19:
- i=16:
, vs → . - i=17:
, vs → . - i=18:
, vs → . - i=19:
, vs → .
Resposta
A tabela completa
é: