Cin – UFPE
Danielle Nathália Gomes da Silva
Anderson Paulo da Silva
{dngs, aps3} @cin.ufpe.br
Recife, Junho de 2008
1
1.
2.
3.
4.
1.
2.
3.
4.
Motivação
Definição
Notação e Terminologia
Algoritmos
Força Bruta Simples
Rabin-Karp
Emparelhamento
por
Finito
Knuth-Moris Pratt.
Autômato
2
Encontra sequências:
 Grupo
de pixels (leitura de um
pergaminho);
 Grupo de índices de um banco de
dados;
 Um texto (no caso de um “search” de
um editor de texto);
 Uma sequência de DNA;
3
Objetivo:
Encontrar uma cadeia de caracteres e
geralmente, todas as ocorrências dessa
cadeia (conhecida como padrão) em um
determinado texto.
4
1.
Força Bruta Simples: Desliza através do texto verificando
caractere a caractere.
2.
Rabin-Karp: Codifica o padrão buscado como uma tabela
hash.
3.
Emparelhamento por Autômato Finito: Para cada padrão é
criado um autômato finito determinístico que o identifica no
texto.
4.
Knuth-Moris Pratt (KMP): Custo linear, Otimização do
simples e do AF. Mais usado para encontrar sequencia de
DNA.
...Força Bruta
AF - 1970
KMP/BM - 1977
KR - 1980
5
Algoritmo
Tempo de préprocessamento
Tempo de
Emparelhamento
Simples
0
Ο((n-m+1)m)
Rabin-Karp
Θ(m)
Ο((n-m+1)m)
Autômato Finito
Ο(m3|∑|)
Θ(n)
Knuth-Morris-Pratt
Θ(m)
Θ(n)
 Com exceção do algoritmo de Força Bruta, todos os outros
que serão apresentados, têm uma etapa anterior ao
emparelhamento, que é fase de pré-processamento do padrão.
 Sendo o tempo total do algoritmo o tempo de processamento
mais o tempo de emparelhamento.
6
Texto é um array de tamanho n  T [ 1 ... n]
Padrão é um array de tamanho m  P [ 1 ... m]
T a b c a a b b c n=8
P s=2 c a a m= 3
s  deslocamento
Com m ≤ n
7
Quando o padrão P ocorre? Quando temos
um deslocamento valido?
1. Se 0 ≤ s ≤ n - m
2. T [s+1 ... s+m] = P [1 ... m]
3. T [s+j] = P [j], para 1 ≤ j ≤ m
8
1.
Se 0 ≤ s ≤ n - m (Possíveis valores de s)
s=0
s=1
s=2
s=3
s=4
s=5
a
b
c
a
a
b
b
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
9
2.
T [s+1 ... s+m] = P [1 ... m]
T a b
P s=2
c
a
a
c
c
c
b
b
c
n=8
m=3
T [2+1 ... 2+3] = P [1 ... 3]
T [3, 4, 5] = P [1, 2, 3]
10
3.
T [s+j] = P [j], para 1 ≤ j ≤ m
T a b
P s=2
c
a
a
b
b
c
c
c
c
m=3
n=8
Verifica para todos os
valores de j
Se j = 3
1 ≤ j ≤ 3, T [2+3] = P [3]
11
∑  Sigma, representa um alfabeto
∑*  Sigma asterisco, conjunto de todas as
cadeias de comprimento finito formadas, usando
caracteres do alfabeto ∑
ε  Cadeia vazia e pertence a ∑*
lXl  Comprimento de X
XY  Concatenação de duas cadeias X e Y. E tem
comprimento lXl + lYl
12
1.Prefixo:
w é prefixo de x, denota-se por w
x, se x=wy para y ∑*. Então se w x,
|w| ≤ |x|. Ex.: ab abcca
2.Sufixo:
w é sufixo de x, denota-se por
w x, se x=yw para y ∑*. Então se w x,
|w| ≤ |x|. Ex.: cca abcca
13
a. Se |x| ≤ |y|, então, x
y.
Prova gráfica do
Lema 32.1
X
Suponha que x,y e z
sejam cadeias tais
que x z e y z.
Z
Y
X
Y
14
b. Se |x|
|y|, então, y
x.
X
Z
Y
X
Y
15
c. Se |x|
|y|, então, y
x.
X
Z
Y
X
Y
16
Trazendo para nosso contexto:
1. Denotaremos o prefixo de k caracteres
P[1...k] do padrão P[1...m] por Pk.
2. Então, P0= ε e Pm=P=P[1...m].
3. Também denota-se para k caracteres
do texto T como Tk.
Objetivo:
Encontrar “s” válidos tal que P T s+m.
17
a
a
b
a
c
b
a
a
c
a
a
c
b
a
a
a
c
b
a
a
a
a
b
a
c
b
a
a
c
a
c
b
a
a
Ilustrando:
a c b
T
P s=0 a a a
s=1
a
s=2
a
a
a
a
a
s=3
a
a
a
a
a
a
a
b
a
c
T 1 ...n
Tk 1 ...k
P 1 ...m
Pk 1 ...k
n=6
m = 3, P
Ts+m -> P
P
P
P
T3
T4
T5
T6
18
O algoritmo de força bruta procura por
todos os deslocamentos s válidos, usando
um loop para verificar a condição de que:
P[1 .. m] = T[s + 1 .. s + m] para cada
n – m + 1 possível valor de s.
19
NAIVE-STRING-MATCHER (T, P)
1
n ← comprimento[T]
2
m ← comprimento[P]
3
4
5
for s ← 0 to n-m
Caminha os possíveis
valores de s
Verifica a condição
de igualdade
do if P[1...m]=T[s+1...s+m]
then imprimir “Padrão ocorre com deslocamento” s
20
O tempo de complexidade deste algoritmo no pior caso é
O((n – m + 1)m). Serão feitas comparações para cada
deslocamento s, de acordo com o tamanho do padrão m.
Considere:
T
b
c
a
a
b
P
a
a
b
b
c
b
c
n=7
m=5
S assume n-m+1 = 3.
=(7-5+1)5
=15
b
c
a
a
b
b
a
a
b
b
c
a
a
b
b
c
a
a
b
b
Se m = n/2, Então
O (n/2 x n)
O (n2/2)
1/2 O(n2)
O(n2)
21
c
c
T
P
0
0
0
0
1
0
0
0
1
0
0
0
0
0
s=0
1 s=1 P[1,2,3,4]=T[2,3,4,5]
0 1
s=2
0 0 1
s=3
0 0 0 1
s=4
0 0 0 1 s=5 P[1,2,3,4]=T[6,7,8,9]
...
0 0 0 1
s=11
0
0
0
0
1
0
1
0
0
0
1
22
Exemplo de busca em texto
T
e
x
t
o
d
e
e
x
e
E
x
e
m
e
x
e
m
e
x
e
m
e
x
e
m
e
x
e
m
e
x
e
m
e
x
e
m
e
x
e
m
e
x
e
m
e
x
e
m p
l
o
p
a
r
a
u
m a
b
u
s
c
a
d
m
23
i
r
e
t
a
Princípio: Transforma o padrão procurado em um
número, seguindo determinadas regras.
 O métodos é baseado em processar a função de
assinatura de cada substring de m-caracteres no
texto e checar se é igual a assinatura da função
da palavra procurada.
 O padrão P ocorre no texto T se o valor
calculado para P for igual ao valor calculado
para qualquer substring X de T, de tamanho m,
tal que | X | = | P |

24


Cada caractere será um dígito decimal
31415 corresponde ao nº decimal 31.415
Os padrões podem ser texto
2
3
5
9
0
2
3
1
4
1
5
...
8
9
3
11
2
6
7
3
9
9
...
0
1
7
8
4
5
2
...
10
11
7
9
11
Por isso precisamos verifica
a condição de igualdade
25
1

Acrescentando notação:
p – número correspondente de P;
ts – número correspondente de T;
d – cardinalidade do alfabeto ;
Então cada caractere é um dígito na base d.
q – número primo, como: 16647133;


Então temos s válidos se, p = ts.
Como calcular p e ts ?
26
Com o alfabeto
P
1
9
9
= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} e | | = 10
1
Temos:
(P[1] * 10 + P[2]) = 19
(19 * 10) + P[3] = 199
(199 * 10) + P[4] = 1991
∑ = alfabeto
|∑| = tamanho de ∑
Dado um caractere, a
representação numérica deste
será sua posição no alfabeto ∑
Generalizando:
P[m] + | | (P[m-1]+ | | (P[m-2] + ... + | | (P[2] + |
P[1]) ))
27

Realiza pré-processamento do padrão P em tempo
2
3
5
9
0
2
3
2
3
5
9
|P| = m
1
4
1
5
2
6
7
3
9
(m)
9
2
1
Usando a regra de Horner, podemos calcular o valor de p no
tempo O (m)
P = P[m]+10(P[m-1]+10(P[m-2] + ... + 10(P[2]+10P[1])...))
Comparar P com as m 1ª posições de T.
O t0 pode ser calculado de modo semelhante, mas os t1 ... tn-m ?
28
Para calcular os ts, com s = 1 ... n-m. Temos s=6.
ts+1 = 10(ts – 10m-1T[s+1]) + T[s+m+1]
ts+1 = 10(31415 – 30000) + 2
Remove o dígito de
mais alta ordem de ts.
ts+1 = 10(1415) + 2
ts+1 = 14152
2
3
5
9
0
2
3
1
4
1
5
...
8
9
3
11
0
2
6
7
3
9
...
1
7
8
4
5
9
2
...
10
11
7
9
11
29
1
10m-1T[s+1] – Remover dígito de mais alta ordem.
1
9
9
1
1
9
9
0
0
2
0
1
4
1
5
2
6
7
3
9
9
2
1
É previamente calculado.
Nesta operação matemática
a complexidade depende do
nº de bits. Custo O(lg m).
1991 – 10m-1
1991 – 1000
991
O dígito de mais alta
ordem foi retirado.
991 x 10
a casa
9910 + 0 = 9910 Acrescenta
decimal para a substring
Faz esse processo
O(n – m)
voltar a ter tamanho m
O(1)
30
Os valores das transformações de P e das substrings de T
são muito grande, quando m e |∑| são muito longos
Ajustando a equação para funcionar em módulo q.
14152 (d(ts – h T[s+1]) + T[s+m+1]) mod q
14152 10(31415 – 3x10000) + 2 (mod 13)
14152 10(7-3x3) + 2 (mod 13)
14152 8 (mod 13)
Onde,
d=| |
h dm-1
3
1
4
1
7
8
5
2
31
Realiza pré-processamento em tempo
(lg m) + (m) + (m) = (m)
 Emparelhamento (matching)
n-m+1 deslocamento possíveis T deve ser calculado com
deslocamento s+1. Processar T no deslocamento s+1 custa O(1),
então transformar todo T leva tempo
(n-m+1)

Quantas comparações possíveis entre o número calculado
p e para t vamos realizar? (n-m+1)
Até agora temos (2(n-m+1)) = (n-m+1)
Processar o texto e fazer
comparações entre dos nº
entre as chaves
32

Análise do pior caso.
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
Entretanto para (n-m+1) deslocamento possíveis, no pior caso,
pode haver necessidade de comparar caractere a caractere de p com
todos os ts. Para comparar o com ts, custa o tamanho do padrão,
O(m), então temos que, o custo de emparelhamento no pior caso é:
(n-m+1) x (m) = ((n-m+1)m)

O custo total do algoritmo é a soma do tempo de préprocessamento com o tempo de emparelhamento.

((n-m+1)m) +
((n-m)m)
(n x m)
(m)
Se m = n/2, Então
O (n/2 x n)
O (n2/2)
1/2 O(n2)
O(n2)
33
Realiza pré-processamento do padrão P em tempo
O(m)
 O tempo de processamento de T O(n)

Pior caso:
 Realiza o emparelhamento de P em T O((n-m+1)m) =
O (m x n)
 Se m= n\2, O (n2)
34
RABIN-KARP-MACHER (T, P, d, q)
1
n ← comprimento[T]
2
m ← comprimento[P]
3
h ← d m-1 mod q
4
p←0
5
t0 ← 0
6
for i ← 1 to m \\ Pré-processamento
7
do p ← (dp + P[i]) mod q
8
t0 ← (t0 + T[i]) mod q
9
10
11
12
13
14
Inicializa o hash(p) da
palavra e do texto, hash(t)
for s ← 0 to n-m \\ Emparelhamento Compara caracteres da
substring com a palavra,
do if p = ts
eliminando o acerto espúrio
then if P [1...m] = T [s + 1 ... s + m]
then “Padrão ocorre no deslocamento” s
if s < n-m
then ts+1 ← (d(ts – T[s+1]h) + T[s+m+1]) mod q
35
Localizar o padrão 31415 no texto
2359023141526739921.
31415 mod 13 = 7,
então, deve-se procurar por todas as
combinações de P onde mod 13 = 7
2359023141526739921
--------8
2359023141526739921
--------9
2359023141526739921
--------3
2359023141526739921
--------11
2359023141526739921
--------0
2359023141526739921
--------1
2359023141526739921
--------7 Comparação bem sucedida
na posição 7
2359023141526739921
--------8
2359023141526739921
--------4
2359023141526739921
--------5
2359023141526739921
--------10
2359023141526739921
--------11
2359023141526739921
--------7 Comparação mal
sucedida
2359023141526739921
--------9
2359023141526739921
--------11
36
Localizar o padrão 31415 no texto
2359023141526739921.
31415 mod 13 = 7,
então, deve-se procurar por todas as
combinações de P onde mod 13 = 7
2359023141526739921
--------8
2359023141526739921
--------9
2359023141526739921
--------3
2359023141526739921
--------11
2359023141526739921
--------0
2359023141526739921
--------1
2359023141526739921
--------7 Comparação bem sucedida
na posição 7
2359023141526739921
--------8
2359023141526739921
--------4
2359023141526739921
--------5
2359023141526739921
--------10
2359023141526739921
--------11
2359023141526739921
--------7 Comparação mal
sucedida
2359023141526739921
--------9
2359023141526739921
--------11
37
 Notação:
 Um
autômato finito é uma 5-tupla (Q, q0, A,
, )
Onde:
Q – Conjunto de estados
q0 - Estado Inicial (q0
Q)
A – Conjunto de estados de aceitação (A
- Alfabeto de entrada finito
- Função de transição
Q)
b, c
c
b, c
b
a
0
a
1
c
b
b
2
a
3
b
4
a
a
c
5
a
a
b, c
b, c
c
Autômato que aceita a string “ababaca”.
6
a
7
Entrada
Estado
a b c
0
1 0
0
1
1
2
0
2
3
0
0
3
1
4
0
4
5
0
0
5
1
4
6
6
7
0
0
7
1
2
0
i
T[i]
Estado
– 1 2 3 4 5 6 7 8 9 10 11
- a b a b a b a c a b a
(Ti) 0 1 2 3 4 5 4 5 6 7 2 3
40
1.


2.
(w) – Função de Estado Final
( ) = q0
(wa) = ( (w), a) para w
*, a
(x) – Função Sufixo
 É o comprimento do mais longo prefixo de P que
é um sufixo de x
 (x) = max{k: Pk
x}
P = ab
 Para um padrão P de comprimento
m, temos (x) = m P x
( )=0
(ccaca) = 1
(ccab) = 2
1.
A função de transição é definida pela
seguinte equação, para qualquer estado “q” e
caractere “a”:
 (q, a) = (P qa).
2.
Uma boa razão intuitiva para a definição
anterior é:
 (Ti) = (Ti)
T[i ] = a b a b a b a c a b a
P=ababaca
b, c
c
b, c
b
a
0
a
1
c
b
b
2
a
3
b
4
a
a
c
5
6
a
a
b, c
b, c
c
43
a
7
T[i ] = a b a b a b a c a b a
P=ababaca
b, c
c
b, c
b
a
0
a
1
c
b
b
2
a
3
b
4
a
a
c
5
6
a
a
b, c
b, c
c
44
a
7
T[i ] = a b a b a b a c a b a
P=ababaca
b, c
c
b, c
b
a
0
a
1
c
b
b
2
a
3
b
4
a
a
c
5
6
a
a
b, c
b, c
c
45
a
7
T[i ] = a b a b a b a c a b a
P=ababaca
b, c
c
b, c
b
a
0
a
1
c
b
b
2
a
3
b
4
a
a
c
5
6
a
a
b, c
b, c
c
46
a
7
T[i ] = a b a b a b a c a b a
P=ababaca
b, c
c
b, c
b
a
0
a
1
c
b
b
2
a
3
b
4
a
a
c
5
6
a
a
b, c
b, c
c
47
a
7
T[i ] = a b a b a b a c a b a
P=ababaca
b, c
c
b, c
b
a
0
a
1
c
b
b
2
a
3
b
4
a
a
c
5
6
a
a
b, c
b, c
c
48
a
7
T[i ] = a b a b a b a c a b a
P=ababaca
b, c
c
b, c
b
a
0
a
1
c
b
b
2
a
3
b
4
a
a
c
5
6
a
a
b, c
b, c
c
49
a
7
T[i ] = a b a b a b a c a b a
P=ababaca
b, c
c
b, c
b
a
0
a
1
c
b
b
2
a
3
b
4
a
a
c
5
6
a
a
b, c
b, c
c
50
a
7
T[i ] = a b a b a b a c a b a
P=ababaca
b, c
c
b, c
b
a
0
a
1
c
b
b
2
a
3
b
4
a
a
c
5
6
a
a
b, c
b, c
c
51
a
7
T[i ] = a b a b a b a c a b a
P=ababaca
b, c
c
b, c
b
a
0
a
1
c
b
b
2
a
3
b
4
a
a
c
5
6
a
a
b, c
b, c
c
52
a
7
FINITE-AUTOMATON-MATCHER(T,
, m)
n comprimento[T]
q 0
for i 1 to n
(n)
do q
(q, T[i])
if q = m
then imprimir “padrão ocorre com deslocamento” i-m
COMPUTE-TRANSITION-FUNCTION(P,
m comprimento[P]
for q 0 to m
do for cada caractere “a”
do k min(m+1, q+2)
repeat k k-1
until Pk Pqa
(q, a) k
return
)
m* m* m*| | = O(m3|
|)



Algoritmo de emparelhamento em tempo linear;
Evita por completo o cálculo da função de
transição;
Evita testes de deslocamento inúteis;
Definição:

A função prefixo para o padrão P é a função:
{1, 2, …, m}  {0, 1, …, m-1} tal que
*[q] = max{k: k<q e Pk

Pq }
Em outras palavras: [q] é o comprimento do
prefixo mais longo de P que também é sufixo de
Pq.
Ôba!
T=100101101010011100
P=10100111
57
Ôba!
T=100101101010011100
P=10100111
58
Êpa!
T = 1 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0Antes do erro a string
“10”foi lida no texto.
P=10100111
Logo o padrão não precisa
ser comparado com a
segunda posição do texto.
59
Êpa!
T=100101101010011100
P=10100111
P=10100111
60
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
61
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
62
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
63
Êpa!
T=100101101010011100
P=10100111
A última substring lida
P=10100111
foi “101”. Logo o padrão
P=10100111
pode avançar 2 posições
a direita
64
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
65
Êpa!
T=100101101010011100
P=10100111
P=10100111
P=10100111
66
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
P=10100111
67
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
P=10100111
68
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
P=10100111
69
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
P=10100111
70
Êpa!
T=100101101010011100
P=10100111
P=10100111
P=10100111
P=10100111
71
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
P=10100111
P=10100111
72
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
P=10100111
P=10100111
73
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
P=10100111
P=10100111
74
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
P=10100111
P=10100111
75
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
P=10100111
P=10100111
76
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
P=10100111
P=10100111
77
Ôba!
T=100101101010011100
P=10100111
P=10100111
P=10100111
P=10100111
P=10100111
78

T=100101101010011100
P=10100111
P=10100111
P=10100111
P=10100111
P=10100111
79
Compute-Prefix-Function(P)
m comprimento[P]
[1] 0
k 0
For q 2 to m
do while k > 0 e P[k+1]
do k
[k]
i
if P[k+1] = P[q]
P[i]
then k k + 1
[i
]
[q] k
return
P[q]
1
2
3
4
5
6
7
8
9
10
a
b
a
b
a
b
a
b
c
a
0
80
Compute-Prefix-Function(P)
m comprimento[P]
[1] 0
k 0
For q 2 to m
do while k > 0 e P[k+1]
do k
[k]
i
if P[k+1] = P[q]
P[i]
then k k + 1
[i
]
[q] k
return
P[q]
1
2
3
4
5
6
7
8
9
10
a
b
a
b
a
b
a
b
c
a
0
0
81
Compute-Prefix-Function(P)
m comprimento[P]
[1] 0
k 0
For q 2 to m
do while k > 0 e P[k+1]
do k
[k]
i
if P[k+1] = P[q]
P[i]
then k k + 1
[i
]
[q] k
return
P[q]
1
2
3
4
5
6
7
8
9
10
a
b
a
b
a
b
a
b
c
a
0
0
1
82
Compute-Prefix-Function(P)
m comprimento[P]
[1] 0
k 0
For q 2 to m
do while k > 0 e P[k+1]
do k
[k]
i
if P[k+1] = P[q]
P[i]
then k k + 1
[i
]
[q] k
return
P[q]
1
2
3
4
5
6
7
8
9
10
a
b
a
b
a
b
a
b
c
a
0
0
1
2
83
Compute-Prefix-Function(P)
m comprimento[P]
[1] 0
k 0
For q 2 to m
do while k > 0 e P[k+1]
do k
[k]
i
if P[k+1] = P[q]
P[i]
then k k + 1
[i
]
[q] k
return
P[q]
1
2
3
4
5
6
7
8
9
10
a
b
a
b
a
b
a
b
c
a
0
0
1
2
3
84
Compute-Prefix-Function(P)
m comprimento[P]
[1] 0
k 0
For q 2 to m
do while k > 0 e P[k+1]
do k
[k]
i
if P[k+1] = P[q]
P[i]
then k k + 1
[i
]
[q] k
return
P[q]
1
2
3
4
5
6
7
8
9
10
a
b
a
b
a
b
a
b
c
a
0
0
1
2
3
4
85
Compute-Prefix-Function(P)
m comprimento[P]
[1] 0
k 0
For q 2 to m
do while k > 0 e P[k+1]
do k
[k]
i
if P[k+1] = P[q]
P[i]
then k k + 1
[i
]
[q] k
return
P[q]
1
2
3
4
5
6
7
8
9
10
a
b
a
b
a
b
a
b
c
a
0
0
1
2
3
4
5
86
Compute-Prefix-Function(P)
m comprimento[P]
[1] 0
k 0
For q 2 to m
do while k > 0 e P[k+1]
do k
[k]
i
if P[k+1] = P[q]
P[i]
then k k + 1
[i
]
[q] k
return
P[q]
1
2
3
4
5
6
7
8
9
10
a
b
a
b
a
b
a
b
c
a
0
0
1
2
3
4
5
6
87
Compute-Prefix-Function(P)
m comprimento[P]
[1] 0
k 0
For q 2 to m
do while k > 0 e P[k+1]
do k
[k]
i
if P[k+1] = P[q]
P[i]
then k k + 1
[i
]
[q] k
return
P[q]
1
2
3
4
5
6
7
8
9
10
a
b
a
b
a
b
a
b
c
a
0
0
1
2
3
4
5
6
0
88
Compute-Prefix-Function(P)
m comprimento[P]
[1] 0
k 0
For q 2 to m
do while k > 0 e P[k+1]
do k
[k]
i
if P[k+1] = P[q]
P[i]
then k k + 1
[i
]
[q] k
return
(m)  Amortizada
P[q]
1
2
3
4
5
6
7
8
9
10
a
b
a
b
a
b
a
b
c
a
0
0
1
2
3
4
5
6
0
1
89
KMP - MATCHER(T, P)
n
comprimento[T]
m
comprimento[P]
Compute-Prefix-Function(P)
q
0
for i
(n)  Amortizada
1 to n
do while q > 0 e P[q+1]
do q
T[i]
[q]
if P[q+1] = T[i]
then q
q+1
if q = m
then print “ Padrão ocorre com deslocamento” i – m
q
[q]
i
1
2
3
4
5
6
7
8
9
10
P[i]
a
b
a
b
a
b
a
b
c
a
T[i]
a
b
a
b
a
b
a
b
a
b
[i
0
0
1
2
3
4
5
6
0
1
]
11
12
13
14
15
a
b
c
a
a
90
Exemplo de busca em texto
Ho o l a - Ho
Ho o l i g a n
Ho o l
Ho o
Ho
o l a
g i r l s
l i k e
i g a n
l i g a
o l i g
Ho
. . . .
n
a n
o l i g a n
. . . . . . . . . . .
Ho o l i g a n s
Ho o l i g a n
91
Inicia a busca comparando-se os caracteres do
final da cadeia;
 Compara as observações anteriores da cadeia,
mesmo artifício do KMP;
 Faz uso de duas heurísticas: mau-caractere e
bom sufixo;
 A escolha da heurística depende da sua
aplicação;
 Texto com grande diversidade de caractere
(mau-caractere);

92
Exemplo de busca em texto
H o o L a H o o L i
H o o l
a
g i
r
l
s
l
i
k e
H o o l
i
g a n
H o o l
i
g a n s
H o o l
i
g a n
g a n
H o o l
i
g a n
H o o l
i
g a n
93
Exemplo de busca em texto
A
s T r i
s t
i
n g
e x a m p l
e
c o n s i
s t
i
s t
i
n g
o f
.
.
.
N g
s t
i
n g
s t
i
n g
s t
n g
i
n g
s t
i
n g
s t
i
n g
94
http://en.wikipedia.org/wiki/String_searching_algorithm
http://dalton.dsc.ufcg.edu.br/edados/index.php/Casament
o_de_Padr%C3%B5es_em_Strings#Vis.C3.A3o_Geral
 Carvalho, Paulo. Oliveira, Deive. Guaracy, Alessandra.
Gomes, Alisson. Albuquerque, Jones. Um Estudo Teórico e
Experimental em Algoritmos Clássicos de Busca em Texto.
UFLA - Universidade Federal de Lavras.
 Silva, Danielle. Fernandes, Carlos. Joab, Rony. Algoritmos
para Busca de Padrões em Sequências. UFRPE –
Universidade Federal Rural de Pernambuco.
Cormen,
Thomas H.; Leiserson, Charles E.; Rivest, Ronald
L.; Stein, Clifford. Introduction to Algorithms, second
edition, MIT Press and McGraw-Hill.
95