MAC0121 - Lista 5 - Busca de padrão e hashing

1. Calcule o vetor pref usado as duas versões do algoritmo Boyer-Moore, bem como a terceira versão, que junta as duas heurísticas, 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 de cada versão?

         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.
3. Calcule o vetor alcance para o padrão

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

4. Mostre que, se todos os caracteres do padrão P[1..m] são distintos, o algoritmo trivial que busca P em um texto T[1..n] pode ser modificado para consumir tempo O(n).
5. Suponha que o padrão P e o texto T são cadeias de caracteres de comprimentos m e n respectivamente, escolhidas aleatoriamente de um alfabeto A_d = {0,1,...,d-1}, onde d >= 2. Mostre que o número esperado de comparações caractere a caractere feita pelo laço implícito na comparação dentro do laço principal do algoritmo trivial é
   (n-m+1)(1-d^-m)/(1-d^-1) <= 2(n-m+1).
   Assim sendo, para cadeias de caracteres aleatórias, o algoritmo trivial é bastante eficiente.
6. Suponha que o padrão P pode conter ocorrências de um caracter vão Ø, que pode ser casado a uma cadeia arbitrária de caracteres (inclusive com a cadeia vazia). Por exemplo, o padrão abØ baØ c ocorre no texto cabccbacbacab de duas maneiras diferentes:
   cabccbacbacab e
   cabccbacbacab.
   Note que o caracter vão pode ocorrer um número arbitrário de vezes no padrão, mas não ocorre no texto nenhuma vez. Descreva um algoritmo polinomial para determinar se um tal padrão ocorre em um texto T, e analise o consumo de tempo do seu algoritmo.
7. Descreva um algoritmo para determinar se um texto T é uma rotação cíclica de uma outra cadeia de caracteres T'. Por exemplo, arco e coar são rotações uma da outra.
8. Suponha que desejamos percorrer uma lista ligada de comprimento n onde cada elemento contem uma chave k junto com um valor de hash h(k). Cada chave é uma longa cadeia de caracteres. Como podemos tirar vantagem dos valores de hash quando fazemos uma busca por um elemento com uma dada chave?
9. Declare um tipo struct celula, com dois campos: chave (int) e apont (apontador para struct celula). Usando esse tipo, escreva uma implementação das funções

      int h(int m, int k);
   
      int busca(apont T[], int m, int k);
   
      void insere (apont T[], int m, int k);
   
      void remove (apont T[], int m, int k); 
   

   em que h é a função dada em aula no item (a).