-
Notifications
You must be signed in to change notification settings - Fork 4
/
knuthMorrisPratt.c
67 lines (53 loc) · 1.31 KB
/
knuthMorrisPratt.c
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*
Autor: Fabricio Andrade
Data: 13/01/20
Algoritmo: Knuth Morris Pratt
Obs1: Não são utilizados comandos de limpar tela
para evitar problemas com diferentes SO's
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void knuthMorrisPratt(char *texto, char *palavra, int tamanhoTexto, int tamanhoPalavra)
{
int contador=0;
//armazena o índice da próxima melhor correspondência
int proximos[tamanhoPalavra+1];
for (int i = 0; i < tamanhoPalavra + 1; i++){
proximos[i] = 0;
}
for (int i = 1; i < tamanhoPalavra; i++)
{
int j = proximos[i+1];
while (j > 0 && palavra[j] != palavra[i]){
j = proximos[j];
}
if (j > 0 || palavra[j] == palavra[i]){
proximos[i+1] = j + 1;
}
}
for (int i = 0, j = 0; i < tamanhoTexto; i++)
{
if (*(texto + i) == *(palavra + j))
{
if (++j == tamanhoPalavra){
contador++;
}
}
else if (j > 0) {
j = proximos[j];
i--;
}
}
printf("\nHouve %d ocorrencia(s) do padrao %s\n",contador, palavra);
}
// Program to implement knuthMorrisPratt Algorithm in C
int main()
{
char texto[] = "ABCABAABCABAC";
char palavra[] = "ABA";
int tamanhoTexto = strlen(texto);
int tamanhoPalavra = strlen(palavra);
knuthMorrisPratt(texto, palavra, tamanhoTexto, tamanhoPalavra);
return 0;
}