Projeto e Analise de Algoritmos
Por: Bawher Junio • 4/12/2019 • Trabalho acadêmico • 1.597 Palavras (7 Páginas) • 209 Visualizações
PONTIFÍCIA UNIVERSIDADE CATÓLICA DE GOIÁS
ESCOLA DE CIÊNCIAS EXATAS E DA COMPUTAÇÃO
GRADUAÇÃO EM ENGENHARIA DE COMPUTAÇÃO
[pic 1]
TRABALHO T1N2
BAWHER JUNIO SOUSA
GOIÂNIA
2019
BAWHER JUNIO SOUSA
T1N2
Trabalho apresentado à Escola de Ciências Exatas e da Computação, da Pontifícia Universidade Católica de Goiás, como parte dos requisitos para a obtenção da aprovação na disciplina de Projeto e Analise de Algoritmos 2.
Professor: Nilson Cardoso Amaral
GOIÂNIA
2019
ALGORITMO KMP
Visão geral do pré-processamento:
- O algoritmo KMP pré-processa pat [ ] e constrói um lps auxiliar [ ] de tamanho m (igual ao tamanho do padrão) que é usado para pular caracteres durante a correspondência.
- nome lps indica o prefixo adequado mais longo, que também é sufixo. Um prefixo adequado é o prefixo com toda a cadeia não permitida. Por exemplo, os prefixos de "ABC" são "", "A", "AB" e "ABC". Os prefixos adequados são "", "A" e "AB". Sufixos da string são "", "C", "BC" e "ABC".
- Procuramos lps em sub-padrões. Mais claramente, focamos nas sub-cadeias de padrões que são prefixo e sufixo.
- Para cada sub-padrão pat [0..i] em que i = 0 a m-1, lps [i] armazena o comprimento do prefixo adequado máximo correspondente, que também é um sufixo do sub-padrão pat [0..i].
Código C++:
1 #include
2 void computeLPSArray(char* pat, int M, int* lps);
3 using namespace std;
4 // Imprime ocorrências de txt [] em pat []
5 void KMPSearch(char* pat, char* txt)
6 {
7 int M = strlen(pat);
8 int N = strlen(txt);
9
10 // crie lps [] que conterá o prefixo mais longo
11 // valores para o padrão
12 int lps[M];
13
14 // Pré-processe o padrão (calcule a matriz lps [])
15 computeLPSArray(pat, M, lps);
16
17 int i = 0; // índice para txt []
18 int j = 0; // índice para pat []
19 while (i < N) {
20 if (pat[j] == txt[i]) {
21 j++;
22 i++;
23 }
24
25 if (j == M) {
26 printf(" Padrao encontrado no indice %d ", i - j);
27 j = lps[j - 1];
28 }
29
30 // incompatibilidade após j correspondências
31 else if (i < N && pat[j] != txt[i]) {
32 // Não corresponde aos caracteres lps [0..lps [j-1]],
33 // eles vão combinar de qualquer maneira
34 if (j != 0)
35 j = lps[j - 1];
36 else
37 i = i + 1;
38 }
39 }
40 }
41
42 // Preenche lps [] para determinado padrão [0..M-1]
43 void computeLPSArray(char* pat, int M, int* lps)
44 {
45 // comprimento do prefixo do prefixo mais longo anterior
46 int len = 0;
47
48 lps[0] = 0; // lps [0] é sempre 0
49
50 // o loop calcula lps [i] para i = 1 a M-1
51 int i = 1;
52 while (i < M) {
53 if (pat[i] == pat[len]) {
54 len++;
55 lps[i] = len;
56 i++;
57 }
58 else // (pat[i] != pat[len])
59 {
60
61 // Isso é complicado. Considere o exemplo.
62 // AAACAAAA ei = 7. A ideia é semelhante
63 // para pesquisar a etapa.
64 if (len != 0) {
65 len = lps[len - 1];
66
67 }
68 else // if (len == 0)
69 {
70 lps[i] = 0;
71 i++;
72 }
73 }
74 }
75 }
76
77 int main()
78 {
79 char txt[] = "ESCREVER É ESQUECER. A LITERATURA É A MANEIRA MAIS AGRADÁVEL DE
...