TP2

UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
MESTRADO EM INFORMÁTICA
PROJETO DE ANÁLISE DE ALGORITMOS

Ana Christina de Oliveira Bringuente
Rodrigo Fernandes Calhau

Casamento de Padrão com Busca Exata e Aproximada

Vitória – ES
2009

Sumário
1

Introdução ......................................................................................................... 2

2

Casamento exato .............................................................................................. 3
2.1 Boyer-Moore-Horspool – BMH .......................................................................... 3
2.1.1

Descrição.............................................................................................. 3

2.1.2

Análise .................................................................................................. 4

2.2 Boyer-Moore-Horspool-Sunday – BMHS .......................................................... 5
2.2.1

Descrição.............................................................................................. 5

2.2.2

Análise .................................................................................................. 7

2.3 Shift-And Exato ................................................................................................. 7

3

2.3.1

Descrição.............................................................................................. 7

2.3.2

Análise .................................................................................................. 9

Casamento Aproximado.................................................................................... 9
3.1 Shift-And Aproximado ....................................................................................... 9
3.1.1

Descrição.............................................................................................. 9

3.1.2

Análise ................................................................................................ 11

3.2 Programação