MAC0121 - Lista 5 - Hashing e busca de padrão

1. 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?

2. Declare um tipo struct celula, com dois campos: chave (int) e Link (apontador para struct celula). Usando esse tipo, escreva uma implementação das funções

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

   em que h é é uma função de hash sugerida na aula e a resolução de colisões é por lista encadeada. Para escolher o valor de m e a função de hash, considere uma aplicação em que vão ser armazenados na tabela de hashing cerca de 1000 inteiros.

3. Calcule os vetores ult e alcance, usados nas heurísticas do algoritmo Boyer-Moore, 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 uma das três versões do algoritmo de Boyer-Moore?

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

4. 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
         

5. 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).

6. 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.

7. Escreva uma função que tem como parâmetro duas palavras de mesmo comprimento e determina se uma é permutação cíclica da outra. Por exemplo, arco e coar são rotações uma da outra.