Aluno: Marco Alves de Alcantara - NUSP: 11221904
Supervisora: Cristina Gomes Fernandes
Resumo:
Abordamos o problema de buscar as ocorrências de palavras num texto realizando um pré-processamento no texto em vez de na palavra, como ocorreria nos algoritmos mais comuns de busca. A vantagem disso é que esse pré-processamento permite que cada busca seja realizada mais eficientemente, já que ele é feito uma única vez antes de começar a fazer as buscas. A desvantagem é que armazenar os dados obtidos após pré-processar o texto ocupa muito mais memória do que pré-processar cada palavra.
Essa abordagem só é preferível em aplicações onde o texto, além de longo, é fixo, já que caso contrário, seria necessário refazer o pré-processamento após cada alteração feita no texto, algo que poderia tornar essa abordagem mais lenta do que algoritmos mais comuns caso essas alterações ocorram frequentemente.
Todas as estruturas de dados e algoritmos abordados pela monografia foram implementados em C++.