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

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.)
4. Calcule a função prefixo 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
         

   quando o alfabeto é A={a,b}.
5. Mostre que, se todos os caracteres do padrão P[1..m] são distintos, o algoritmo ingênuo 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 ingênuo é
   (n-m+1)(1-d^-m)/(1-d^-1) <= 2(n-m+1).
   (Suponha que o algoritmo ingênuo pára as comparações assim que encontra um caractere do padrão que não casa com o correspondente do texto, ou quando encontra uma ocorrência do padrão.) Assim sendo, para cadeias de caracteres aleatórias, o algoritmo ingênuo é bastante eficiente.
7. 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.
8. Mostre como determinar as ocorrências de um padrão P[1..m] em um texto T[1..n] examinando a função prefixo para a cadeia de caracteres PT (concatenação de P com T).
9. Descreva um algoritmo linear 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.
10. 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?
11. 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).