Busca em texto com o método de Boyer Moore
Publicado por Danilo Azevedo em 23/07/2014
[ Hits: 5.726 ]
1 2 3 4 5 ... 35 String: W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T 1 2 3 4 5 6 7 Padrão: A T - T H A TFórmulas (usando o padrão):
-3 -2 -1 0 1 2 3 4 5 6 7 $ $ $ $ A T - T H A T 1Calcular o delta2(6): procurar o sufixo de A, que não tenha A como prefixo.
-3 -2 -1 0 1 2 3 4 5 6 7 $ $ $ $ A T - T H A T 4 1Calcular o delta2(5): procurar o sufixo de H, que não tenha tenha H como prefixo.
-3 -2 -1 0 1 2 3 4 5 6 7 $ $ $ $ A T - T H A T 7 4 1Calcular o delta2(4): procurar sufixo de T, que não tenha T como prefixo.
-3 -2 -1 0 1 2 3 4 5 6 7 $ $ $ $ A T - T H A T 8 7 4 1Calcular o delta2(3): ...
-3 -2 -1 0 1 2 3 4 5 6 7 $ $ $ $ A T - T H A T T H A TE portanto, o T H A T no índice -1
-3 -2 -1 0 1 2 3 4 5 6 7 $ $ $ $ A T - T H A T 9 8 7 4 1Calcular o delta2(2) e delta2(1): dá trabalho.
-3 -2 -1 0 1 2 3 4 5 6 7 $ $ $ $ A T - T H A T 11 10 9 8 7 4 1Utilizando delta1 e delta2 para achar o padrão:
1 2 3 4 5 ... 35 W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T A T - T H A TF não ocorre no padrão, logo, delta1(F) = 7
1 2 3 4 5 ... 35 W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T A T - T H A T A T - T H A TOs caracteres não batem (não utiliza delta2), utilizamos o delta1 do caractere encontrado, delta1(-) = 4:
1 2 3 4 5 ... 35 W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T A T - T H A T A T - T H A T A T - T H A T |Os caracteres batem (T e T), utilizamos o máximo entre delta1 e delta2. o sufixo é o T (paramos no A)
1 2 3 4 5 ... 35 W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T A T - T H A T A T - T H A T A T - T H A T A T - T H A T |Os caracteres batem até o caractere A, logo, utilizamos o delta2 que tem sufixo A T (o delta2(5)= 7).
1 2 3 4 5 ... 35 W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T A T - T H A T A T - T H A T A T - T H A T A T - T H A T A T - T H A T
Existe uma distribuição Linux melhor? Como escolher?
Habilitar RPM Fusion no Fedora/RHEL/CentOS (Atualizado)
Criando listas individuais para cada instância da mesma classe em Python
Como instalar o UFO: Alien Invasion no Ubuntu 9.10
Desabilitar o sininho (bell) no terminal
Atenção a quem posta conteúdo de dicas, scripts e tal (2)
Manutenção de sistemas Linux Debian e derivados com apt-get, apt, aptitude e dpkg
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
Como criar um robot em NTSL (Nelogica Trading System Language) para Profitchart
Use o Google PageSpeed Insights para verificar um site
Como Atualizar Fedora 39 para 40
Sistema da Coréia do Norte - Red Star OS (24)
filtrar só as pastas onde tem arquivo (4)
Como adicionar módulo de saúde da bateria dos notebooks Acer ao kernel... (31)
Instalacao Manjaro em notebook com placa de video hibrida [RESOLVIDO] (2)