Estudante

Paulo Lira Machado
Welton Pereira Macedo
M

Algoritmos e Estruturas de Dados:
Algoritmo de Boyer - Moore e Sequências Numéricas

PALMAS - TO
2013

INTRODUÇÃO

RESUMO: O método de Boyer-Moore é conhecido na literatura por resolver o problema do casamento de padrões. Inicialmente foi apresentado por J Strother Moore e Bob Boyer de forma Implícita.
PALAVRAS-CHAVE: Boyer-Moore, algoritmo, casamento de padrões, padrão no texto.
OBJETIVOS:
(objetivos geral e específico) Identificar, analisar, compreender e implementar através de pesquisas cientificas o método utilizado por Boyer-Moore para a resolução do problema de casamento de padrões, na forma analítica e utilizada em linguagem C. HISTÓRIA: O clássico algoritmo de Boyer-Moore foi publicado por Robert S. Boyer e J. Strother Moore em 1977. O algoritmo foi criado fundamentalmente para resolver o problema do casamento de padrões, que tem como objetivo encontrar todas as ocorrências de um determinado padrão no texto. No artigo original Boyer e Moore (1977), os autores mencionaram que, em 1974, o algoritmo só contava com a heurística do bad-character. Em 1975, eles perceberam que podiam usar a informação do sufixo do padrão que casou com o texto e enunciaram a regra do good suffix, embora não fornecessem o seu modo de cálculo. Após publicarem os resultados, Ben Kuipers, do laboratório de inteligência artificial do M.I.T., leu o artigo e observou que melhorias poderiam ser feitas no algoritmo ao considerar o símbolo que precedia a outra ocorrência da subpalavra e o símbolo que precedia a própria subpalavra que casou com o texto. Assim surgia a regra strong good suffix.

PROBLEMÁTICA: Padrão é uma frase que permite analisar um valor e associar variáveis aos dados que compõem o valor. Casamento de padrão é uma operação envolvendo um padrão e uma expressão que faz a correspondência