TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

Projeto e Analise de Algoritmos

Por:   •  4/12/2019  •  Trabalho acadêmico  •  1.597 Palavras (7 Páginas)  •  166 Visualizações

Página 1 de 7

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

...

Baixar como (para membros premium)  txt (9.7 Kb)   pdf (201 Kb)   docx (78.6 Kb)  
Continuar por mais 6 páginas »
Disponível apenas no TrabalhosGratuitos.com