MAC122 - Lista 5 - Busca de padrão

1. Calcule o vetor pref usado no algoritmo KMP para o padrão abaixo:

         a    b    b    a    b    a    b    b    a    a    b 
         

   Quantos "alinhamentos" do padrão acima são testados no texto abaixo, ou seja, quantas posições diferentes do padrão em relação ao texto geraram pelo menos uma comparação entre o padrão e o texto durante a execução do algoritmo KMP?

         a    b    a    b    b    a    a    b    b    a    b    b    a    b    a    b    b    a    a    b    b 
         

2. Escreva uma função que tem como parâmetro duas palavras de mesmo comprimento e determina se uma é permutação cíclica da outra. Sua função deve consumir tempo proporcional ao comprimento das palavras.
3. Modifique o KMP para que imprima todas as posições em que aparece o maior sufixo de uma palavra em um texto. (Em sala, modificamos o KMP para que este imprimisse uma posição em que aparecia o maior sufixo de uma palavra em um texto.)