Dados o padrão p e o texto s, de tamanhos m=9 e n=27 respectivamente:

p = ababaabab

s = abababaabaababaababaabababb





(a) gere a tabela de prefixos π de acordo com a função de prefixos vista em sala, escre-

vendo-a como um vetor de posições |1. .m]

(b) realize a busca de p em s com o algoritmo KMP, preenchendo na folha de respostas

uma tabela com o valor de cada i (índice da posicão atual no texto) e todos os valores

de q (poção do padrão atualmente "casada" como texto) para cada iteração i do laço

principal. Siga o modelo com anotações abaixo:

3

4

6

0 (iniciou e terminou o laço valendo 0)

7

0,1 (iniciou o laço com 0e aumentou para 1)

5 2.3

1,2

34

4,2,0,1 (iniciou o laço com 4, diminuiu para 2 e 0, aumentando depois para 1)

12