Aed3

Universidade Federal de Lavras Departamento de Ciência da Computação

GCC109 – Algoritmos e Estruturas de Dados III
Professor: Denilson Alves Pereira

Trabalho Prático 3
   Data Limite de Entrega: 10/11/2011 Valor: 10 pontos Trabalho em grupo de, no máximo, 4 alunos. O trabalho deve ser entregue pelo Moodle (http://aluno.dcc.ufla.br) e será avaliado junto com os alunos no laboratório. Envie arquivos somente nos formatos txt e pdf (não enviar .doc, .docx, .odt etc.). Arquivos compactados somente .zip e .tar.gz (não enviar .rar, .z etc.). Não use acentos e nem “ç” nos nomes de arquivo. Trabalhos copiados receberão nota zero.





O objetivo do trabalho é implementar e comparar os seguintes algoritmos de casamento de padrão:

 Rabin-Karp. Para definir os valores para a base e o número primo q (módulo q), c onsidere uma máquina com palavra de 32 bits e um vocabulário composto pelos 128 primeiros caracteres do código ASCII.  
Knuth-Morris-Pratt. Boyer-Moore-Horspool.

O programa deve ter os seguintes itens:

•

Uma opção para que o usuário escolha um arquivo contento o texto e depois possa executar várias consultas sobre este texto usando padrões diferentes. Em cada consulta, o usuário pode escolher o algoritmo de casamento de padrão que ele quer usar. Na resposta a uma consulta, o programa deve imprimir todo o texto e destacar cada ocorrência do padrão usando uma cor diferente daquela usada no restante do texto. No final, deve ser impressa a quantidade de ocorrências do padrão no texto. O programa deve ter também uma opção para realização de experimentos com marcação de tempo. Neste caso, faça como no item anterior, mas ao invés de imprimir o texto, imprima somente a quantidade de ocorrências e o tempo gasto pelo algoritmo para encontrá-las, somando-se o tempo de préprocessamento do padrão e o tempo de busca. Use para testes os dois arquivos texto do Trabalho Prático 1. Relate no relatório os testes efetuados. Mostre os resultados de