Algoritmo de Rabin-Karp para busca de substring

Livro de Sedgewick e Wayne: fim da sec.5.3, p.774.  Website do livro: resumo sec.5.3, slides.  Código fonte, documentação, e dados de teste de todos os programas do livro: veja algs4.cs.princeton.edu/code/.

Esta página trata de um algoritmo probabilístico de impressão digital para o problema substring search.

Destaques:

Pré-requisitos:

Algoritmo RK

Resolvendo as dificuldades técnicas

Exercícios 1

  1. Suponha que o tipo int do meu computador é capaz de armazenar apenas números no intervalo -1000000..99999. Mostre como calcular o valor da expressão ((929 - 9*155)*62 + 55) % 997 sem correr o risco de overflow.
  2. (SW 5.3.23)  Escreva um programa rápido que leia caracteres da entrada padrão, um a um, e diga, a cada instante, se a string lida até o momento é um palíndromo. (Dois exemplos de palíndromos:   anilina  e  sopapos.)  Use as mesmas ideias do algoritmo de Rabin-Karp.
  3. Seja R um número inteiro positivo e (dn, dn−1, … , d1, d0) uma sequência de números do conjunto {0,1,…,R−1}. Para cada i, (di, di−1, … , d1, d0) representa um número xi na base R, sendo di o dígito mais significativo e d0 o menos significativo. Mostre como calcular xn a partir de xn−1 eficientemente. Ignore a possibilidade de overflow aritmético.

Implementação do algoritmo RK

Exercícios 2

  1. (SW 5.3.33) Primos aleatórios. Implemente o método longRandomPrime() na classe RabinKarp.  Dica: Um número aleatório de n dígitos é primo com probabilidade proporcional a 1/n.

Versões Monte Carlo e Las Vegas

Exercícios 3

  1. (SW 5.3.25b) Fluxo contínuo (streaming). Acrescente à classe RabinKarp um método search() que receba um fluxo de entrada do tipo In como argumento e procure pelo padrão pat no fluxo de entrada especificado. Não use variáveis de instância adicionais (em particular, não armazene qualquer trecho do texto na memória).
  2. (SW 5.3.26) Rotação cíclica. Escreva um programa que receba duas strings e decida se uma é rotação cíclica da outra. (Por exemplo, example é rotação cíclica de ampleex.)
  3. (SW 5.3.32) Contagem de substrings de comprimento L. Escreva um programa que leia um texto da entrada padrão e calculate o número de substrings de comprimento L distintas que o texto contém.  Por exemplo, o texto cgcgggcgcg tem cinco substrings de comprimento 3 distintas:  cgc, cgg, gcg, ggc, e ggg.  Dica: Insira cada substring de comprimento L em uma tabela de símbolos. Use ideias análogas às do algoritmo de Rabin-Karp.

Exercícios sobre busca de substring

  1. (SW 5.3.36) Texto aleatório. Escreva um programa que receba inteiros M e N como argumentos, gere uma string aleatória txt de comprimento N sobre o alfabeto  0 1  e depois conte o número de ocorrências em txt da substring formada pelos M últimos caracteres de txt.  Nota: O melhor algoritmo para o problema pode depender do valor de M.
  2. (SW 5.3.39) Comparação de algoritmos. Escreva um programa que cronometre os quatro métodos de busca de substring — força bruta, Knuth-Morris-Pratt, Rabin-Karp Monte Carlo, e Rabin-Karp Las Vegas — na execução da tarefa de procurar a string abaixo no livro tale.txt.  Discuta até que ponto seus resultados confirmam as previsões teóricas sobre o desempenho dos algoritmos.
         it is a far far better thing that i do than i have ever done
    

Perguntas e respostas

Valid CSS! Valid HTML 4.01 Strict