Projeto e Análise de Algoritmos  
Aula 06 Busca de Padrões em Texto  
Edirlei Soares de Lima  
<edirlei@iprj.uerj.br>  
Processamento de Texto  
Cadeia de caracteres: sequência de elementos denominados  
caracteres.  
Os caracteres são escolhidos de um conjunto denominado  
alfabeto.  
Casamento de cadeias de caracteres (string matching) ou  
casamento de padrão (pattern matching): encontrar todas as  
ocorrências de um padrão em um texto.  
Exemplos de aplicação: edição de texto, recuperação de  
informação, estudo de sequências de DNA em biologia  
computacional, ...  
Processamento de Texto  
Texto: arranjo T[1..n] de tamanho n.  
Padrão: arranjo P[1..m] de tamanho m n.  
Os elementos de P e T são escolhidos de um alfabeto finito ꢀ  
de tamanho c.  
Exemplo: = {0, 1} ou = {a, b, ..., z}  
Casamento de cadeias ou casamento de padrão: dados duas  
cadeias P (padrão) de comprimento m e T (texto) de  
comprimento n, onde n m, deseja-se saber as ocorrências  
de P em T.  
Cadeias de Caracteres  
“CGTAAACTGCTTTAATCAAACGC”  
Cadeias de moléculas chamadas bases: adenina (A), guanina (G),  
citosina (C) e timina (T)  
“Projeto e Análise de Algoritmos”  
“http://www.iprj.uerj.br”  
if ( (x==0) && (y!=3) )”  
Encontrando Padrões em Textos  
Exemplo:  
T = “kvjlixapejrbxeenpphkhthbkwyrwamnugzhppfxiyjyanhapfwbghxm  
shrlyujfjhrsovkvveylnbxnawavgizyvmfohigeabgksfnbkmffxjffqbualeytqr  
phyrbjqdjqavctgxjifqgfgydhoiwhrvwqbxgrixydzbpajnhopvlamhhfavoctd  
fytvvggikngkwzixgjtlxkozjlefilbrboignbzsudssvqymnapbpqvlubdoyxkkw  
hcoudvtkmikansgsutdjythzl”  
P = avoctdfytvv”  
Encontrando Padrões em Textos  
(Força Bruta)  
T = a b a c a a b a c c a b a c a b a a b b  
P = a b a c a b  
Objetivo: descobrir se a string P (padrão) está em T  
Força bruta: caminha elemento a elemento da esquerda para  
a direita  
Encontrando Padrões em Textos  
(Força Bruta)  
T = a b a c a a b a c c a b a c a b a a b b  
P = a b a c a b  
1
2
3
4
5
6
7
8
. busca_padrao(t, n, p, m)  
. para i 0 até n - m faça  
. j 0  
O(nm)  
. enquanto (j < m) e t[i + j] == p[j] faça  
j ← j + 1  
. se j == m então  
retorne i  
. retorne "padrão p não encontrado em t"  
.
.
Encontrando Padrões em Textos  
É possível melhorar o algoritmo de força bruta?  
Algoritmo de Boyer-Moore (1976)  
Baseia-se na alta probabilidade de encontrar diferenças em alfabetos  
grandes.  
Por isso, P é comparado com T de trás para frente.  
Quando se encontra uma diferença em T[i], o padrão P dará um salto à  
frente, considerando-se as comparações realizadas.  
Algoritmo de Boyer-Moore  
No algoritmo é necessário considerar 3 casos:  
Caso 1: P não contém x  
Deslocar P para a direita, alinhando P[0] com T[i+1]  
Algoritmo de Boyer-Moore  
No algoritmo é necessário considerar 3 casos:  
Caso 2: A última ocorrência de x em P está algum índice  
menor do que j.  
Deslocar P para a direita, até que a última ocorrência de x fique  
alinhada com T[i].  
Algoritmo de Boyer-Moore  
No algoritmo é necessário considerar 3 casos:  
Caso 3: A última ocorrência de x em P está em algum  
índice maior do que j.  
Deslocar P apenas uma posição para a direita.  
Algoritmo de Boyer-Moore Exemplo  
Algoritmo de Boyer-Moore Exemplo  
Algoritmo de Boyer-Moore  
Através de um pré-processamento, o algoritmo de Boyer-  
Moore calcula uma função L, onde L(x) é definida como:  
o maior índice i tal que P[i] = x;  
-1, caso este índice não exista;  
Exemplo: = {ꢁ, ꢂ, ꢃ, ꢄ}  
P = a b a c a b  
0
1 2 3 4 5  
x
a
b
c
d
L(x)  
4
5
3
-1  
1
2
3
4
5
6
7
8
9
1
1
1
1
1
1
1
1
1
1
. Boyer_Moore(T, n, P, m, , w)  
O(nm)  
.
para k ← 0 até w faça  
. L[k] -1  
. para k ← 0 até m faça  
. L[P[k]] k  
. im - 1  
. jm - 1  
. repita  
. se T[i] == P[j] então  
0. se j == 0 então  
1.  
retorne i  
2. senão  
3.  
4.  
i i - 1  
j j - 1  
5. senão  
6. ii + m - min{j, 1 + L[T[i]]}  
7. jm - 1  
8. enquanto i > n - 1  
9. retorne -1  
Exercício  
1
) Considerando a seguinte cadeia de DNA:  
T = “CTAATCGCTTAATCAAACGC”  
Realize o passo a passo do algoritmo Boyer-Moore  
para verificar se o padrão P = “ATCA” ocorre em T.  
Construa o vetor L e ilustre todos os alinhamentos e  
comparações dos caracteres do padrão P em T.  
Exercícios  
Lista de Exercícios 06 Busca de Padrões em  
Texto  
http://www.inf.puc-rio.br/~elima/paa/  
Leitura Complementar  
Halim e Halim. Competitive Programming,  
3
rd Edition, 2003.  
Capítulo 6: String Processing