include stdio include stdlib include string void prefix char int pi in

 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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void prefix(char *s, int *pi)
{
int t = 0, i = 1;
pi[0] = 0;
int m = strlen(s);
while (i < m) {
while (t > 0 && s[t] != s[i]) {
t = pi[t - 1];
}
if (s[t] == s[i]) {
t ++;
}
pi[i] = t;
i ++;
}
return;
}
void kmp(char *s, char *t)
{
int m = strlen(s);
int pi[m];
prefix(s, pi);
int q = 0, k = 0;
int n = strlen(t);
while (k < n) {
while (q > 0 && s[q] != t[k]) {
q = pi[q - 1];
}
if (s[q] == t[k]) {
q ++;
}
if (q == m) {
printf("%d ", k - m + 1);
q = pi[q - 1];
}
k ++;
}
return;
}
int main(int argc, char **argv)
{
char *str = malloc(sizeof(char)*100);
char *s = malloc(sizeof(char)*100);
str = argv[1];
s = argv[2];
/*gets(str);
gets(s);*/
kmp(s, str);
free(str);
free(s);
return 0;
}