Aula 14 - CasPadrao_Boyer Moore Horspool

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Algoritmo 
Boyer-Moore-Horspool
Lívia N. Andrade
Definições
Em 1977, foi publicado o algoritmo Boyer-Moore(BM);
A idéia é pesquisar no padrão no sentido da direita para a esquerda, o que torna o algoritmo muito rápido.
C A C B A C
A A B C A C C A C B A C
Texto
Padrão
Sentido da comparação
Qual o ganho desse tipo de pesquisa???
Funcionamento do Boyer-Moore (BM)
O BM pesquisa o padrão P em uma janela que desliza ao longo do texto T.
Para cada posição desta janela, o algoritmo pesquisa por um sufixo da janela que casa com um sufixo de P, com comparações realizadas no sentido da direita para a esquerda.
Se não acontecer uma desigualdade, então uma ocorrência de P ocorre em T.
Senão, o algoritmo calcula um deslocamento que o padrão deve ser deslizado para a direita antes que uma nova tentativa de casamento se inicie.
O BM propõe duas heurísticas para calcular o deslocamento: ocorrência e casamento.
Heurística Ocorrência 
Alinha a posição no texto que causou a colisão com o primeiro caractere no padrão que casa com ele;
A partir da posição 6, da direita para a esquerda, existe uma colisão na posição 4 de T, entre B do padrão e C do texto.
Logo, o padrão deve ser deslocado para a direita até o primeiro caractere no padrão que casa com c.
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
Heurística Ocorrência 
Alinha a posição no texto que causou a colisão com o primeiro caractere no padrão que casa com ele;
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
Heurística Ocorrência 
Alinha a posição no texto que causou a colisão com o primeiro caractere no padrão que casa com ele;
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
Heurística Ocorrência 
Alinha a posição no texto que causou a colisão com o primeiro caractere no padrão que casa com ele;
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
Heurística Ocorrência 
Alinha a posição no texto que causou a colisão com o primeiro caractere no padrão que casa com ele;
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
Heurística Casamento
Ao mover o padrão para a direita, faça-o casar com o pedaço do texto anteriormente casado.
Novamente, a partir da posição 6, da direita para a esquerda, existe uma colisão na posição 4 de T.
Neste caso, o padrão deve ser deslocado para a direita até casar com o pedaço do texto anteriormente casado, no caso AC, deslocando o padrão 3 posições à direita.
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
Heurística Casamento
Ao mover o padrão para a direita, faça-o casar com o pedaço do texto anteriormente casado.
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
Heurística Casamento
Ao mover o padrão para a direita, faça-o casar com o pedaço do texto anteriormente casado.
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
Escolha da Heurística
O algoritmo BM escolhe a heurística que provoca o maior deslocamento do padrão.
Várias propostas de simplificação ocorreram ao longo dos anos.
As propostas que produzem os melhores resultados são as que consideram apenas a heurística ocorrência.
A simplificação mais importante é devida a Horspool em 1980.
Boyer-Moore-Horspool
Em 1980, Horspool apresentou uma simplificação no algoritmo BM, tão eficiente quanto o algoritmo original, ficando conhecida como Boyer-Moore-Horspool (BMH).
Pela extrema simplicidade de implementação e comprovada eficiência, o BMH deve ser escolhido em aplicações de uso geral que necessitam realizar casamento exato de cadeias.
Boyer-Moore-Horspool
Executa mais rápido do que o algoritmo BM original.
Parte da observação de que qualquer caractere já lido do texto a partir do último deslocamento pode ser usado para endereçar a tabela de deslocamentos.
Endereça a tabela com o caractere no texto correspondente ao último caractere do padrão.
Tabela de Deslocamentos
Para pré-computar o padrão o valor inicial de todas as entradas na tabela de deslocamentos é feito igual a m.
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
Padrão
m = 6
C A C B A C
Pq o caracter que não aparece no padrão, deslocará m posições.
15
Tabela de Deslocamentos
A seguir, apenas os m − 1 primeiros caracteres do padrão são usados para obter os outros valores da tabela.
1
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
Padrão
m = 6
C A C B A C
A está a 1 posição de C
Pq o caracter que não aparece no padrão, deslocará m posições.
16
Tabela de Deslocamentos
A seguir, apenas os m − 1 primeiros caracteres do padrão são usados para obter os outros valores da tabela.
1
6
2
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
Padrão
m = 6
C A C B A C
A está a 1 posição de C
B está a 2 posições de C
Pq o caracter que não aparece no padrão, deslocará m posições.
17
Tabela de Deslocamentos
A seguir, apenas os m − 1 primeiros caracteres do padrão são usados para obter os outros valores da tabela.
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
Padrão
m = 6
C A C B A C
A está a 1 posição de C
B está a 2 posições de C
C está a 3 posições de C
Pq o caracter que não aparece no padrão, deslocará m posições.
18
Pseudocódigo do algoritmo 
Boyer-Moore-Horspool
Vetor da tabela deslocamento
i += d[ T[k - 1] ]
Pre-processamento do Padrão
(cria tabela deslocamento)
i += d[ T[k - 1] ]
coloca m para todas as posições do vetor deslocamento, inclusive para as posições ocupadas pelos caracteres do padrão
i += d[ T[k - 1] ]
Percorre o padrão e atualiza o valor das variáveis existentes nele
Padrão
C A C B A C
i += d[ T[k - 1] ]
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 6
k = 6
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 6
k = 5
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 6
k = 4
i = i + d[ T[k] ]
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = i + d[ T[k] ]
i = 6 + 3 => 9
Reiniciar a comparação, com o texto na posição 9
i = 6
k = 4
Exemplo de execução do
algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 9
k = 9
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 9
k = 8
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 9
k = 7
i = i + d[ T[k] ]
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 9
k = 7
i = i + d[ T[k] ]
i = 9 + 3 => 12
Reiniciar a comparação, com o texto na posição 12
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 12
k = 12
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 12
k = 11
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 12
k = 10
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 12
k = 9
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 12
k = 8
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 12
k = 7
Exemplo de execução do algoritmo
Texto
Padrão
1
2
3
4
5
6
7
8
9
10
11
12
A
A
B
C
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
C
A
C
B
A
C
1
6
2
6
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
A B C D E F G H I J K L M N
6
6
O P Q R S T U V W X Y Z
i = 12
k = 7
Comparando caractere com caractere.
Enquanto os caracteres forem iguais, vai caminhando para o caractere da esquerda
i += d[ T[k - 1] ]
Caracteres diferentes.
O i receberá seu valor mais o valor definido na tabela de deslocamentos
i += d[ T[k - 1] ]
Exercício 39 da lista
Considerando o algoritmo de Boyer-Moore-Horspool, faça:
Mostre os valores das entradas na tabela de deslocamentos para o padrão “ABRACADABRA”.
Mostre como seriam os deslocamentos do padrão “ABRACADABRA” no texto:
“ABRCCADABRACACAABRACADABRAABRABRACADABRA”
Exercício 39 da lista
Valores das entradas na tabela de deslocamentos.
Padrão: ABRACADABRA
Com a tabela já criada, você já pode iniciar a execução do algoritmo.
3
11
2
11
6
11
4
1
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
A B C D E F G H I J K L M N
11
11
O P Q R S T U V W X Y Z
B. Deslocamentos do Padrão no Texto
A
B
R
C
C
A
D
A
B
R
A
C
A
C
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
3
2
6
4
11
11
1
11
11
A B C D E ... R ... Z
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
i = 11
k = 11
B. Deslocamentos do Padrão no Texto
A
B
R
C
C
A
D
A
B
R
A
C
A
C
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
3
2
6
4
11
11
1
11
11
A B C D E ... R ... Z
i = 11
k = 4
i = i + d[ T[k] ]
i = 11 + 6 => 17
A invés de fazer todo o calculo, apenas verifique na tabela de deslocamento o quanto você deve deslocar com o padrão
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
B. Deslocamentos do Padrão no Texto
A
B
R
C
C
A
D
A
B
R
A
C
A
C
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
3
2
6
4
11
11
1
11
11
A B C D E ... R ... Z
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
B. Deslocamentos do Padrão no Texto
A
B
R
C
C
A
D
A
B
R
A
C
A
C
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
3
2
6
4
11
11
1
11
11
A B C D E ... R ... Z
Verificar na tabela de deslocamento o quanto deve ser deslocado para o caractere B
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
B. Deslocamentos do Padrão no Texto
A
B
R
C
C
A
D
A
B
R
A
C
A
C
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
3
2
6
4
11
11
1
11
11
A B C D E ... R ... Z
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
B. Deslocamentos do Padrão no Texto
A
B
R
C
C
A
D
A
B
R
A
C
A
C
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
3
2
6
4
11
11
1
11
11
A B C D E ... R ... Z
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
B. Deslocamentos do Padrão no Texto
A
B
R
C
C
A
D
A
B
R
A
C
A
C
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
3
2
6
4
11
11
1
11
11
A B C D E ... R ... Z
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
B. Deslocamentos do Padrão no Texto
A
B
R
C
C
A
D
A
B
R
A
C
A
C
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
3
2
6
4
11
11
1
11
11
A B C D E ... R ... Z
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
B. Deslocamentos do Padrão no Texto
A
B
R
C
C
A
D
A
B
R
A
C
A
C
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
3
2
6
4
11
11
1
11
11
A B C D E ... R ... Z
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
B. Deslocamentos do Padrão no Texto
A
B
R
C
C
A
D
A
B
R
A
C
A
C
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
3
2
6
4
11
11
1
11
11
A B C D E ... R ... Z
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
B. Deslocamentos do Padrão no Texto
A
B
R
C
C
A
D
A
B
R
A
C
A
C
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
3
2
6
4
11
11
1
11
11
A B C D E ... R ... Z
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
B. Deslocamentos do Padrão no Texto
A
B
R
C
C
A
D
A
B
R
A
C
A
C
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
A
B
R
A
C
A
D
A
B
R
A
3
2
6
4
11
11
1
11
11
A B C D E ... R ... Z
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
Bibliografias consultadas
Livros:
Projeto de algoritmos com implementações em PASCAL e C – Nivio Ziviani
Algoritmos: Teoria e Prática - CORMEN et. al.