KMP算法

 1 //复杂版
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 
 6 void prefix_table(char pattern[],int prefix[],int n){
 7     prefix[0] = 0;
 8     int len   = 0;
 9     int i = 1;
10     while (i < n){
11         if (pattern[i] == pattern[len]){
12             len++;
13             prefix[i] = len;
14             i++;
15         }
16         else{
17             if (len > 0){
18                 len = prefix[len - 1];
19             }
20             else{
21                 prefix[i] = len;
22                 i++;
23             }
24         }
25     }
26 }
27 
28 int move_prefix_table(int prefix[],int n){
29     int i;
30     for(i=n-1;i>0;i--){
31         prefix[i] = prefix[i-1];
32     }
33     prefix[0] = -1;
34 }
35 
36 void kmp_search(char text[],char pattern[]){
37     int  n = strlen(pattern);
38     int  m = strlen(text);
39     int *prefix = (int*)malloc(sizeof(int)*n);
40     prefix_table(pattern,prefix,n);
41     move_prefix_table(prefix,n);
42 
43     // text[i]     , len(text)    = m
44     // pattern[j], len(pattern) = n
45     int i = 0;
46     int j = 0;
47     while (i < m){
48         if (j == n - 1 &&text[i] == pattern[j]){
49             printf("Found patern at %d\n", i - j );
50             j = prefix[j];
51             for (int x=0;x<n;x++){
52                 printf("%c",pattern[x]);
53             }
54         }
55         if (text[i] == pattern[j]){
56             i++; j++;
57         }
58         else{
59             j = prefix[j];
60             if (j == -1){
61                 i++; j++;
62             }
63         }
64     }
65 }
66 
67 int main(){
68     
69     char pattern[] = "ABABCABAA";
70     char text[]    = "ABABABCABAABABABAB";
71     
72     kmp_search(text,pattern);
73     /*
74     int prefix[9];
75     int n = 9;
76     
77     prefix_table(pattern,prefix,n);
78     move_prefix_table(prefix,n);
79     int i;
80     for (i = 0;i < n;i++){
81         printf("%d\n",prefix[i]);
82     }
83     */
84     return 0;
85 }

 1 //精简版
 2 #include<stdio.h>
 3 #include<string.h>
 4 #define maxn (int)1e5+8
 5 
 6 char pattern[maxn]= {0},text[maxn]= {0};
 7 int next[maxn]= {0};
 8 void Next(char *s,int *fail) {
 9     fail[0]=-1,fail[1]=0;
10     int len=strlen(s);
11     for(int i=1,j=0;i<len;) {
12         if(j==-1||s[i]==s[j])fail[++i]=++j;
13         else j=fail[j];
14     }
15 }
16 
17 int KmpSearch(char* s, char* p) {
18     int i = 0,j = 0,sLen = strlen(s),pLen = strlen(p);
19     while (i < sLen && j < pLen) {
20         if (j == -1 || s[i] == p[j]) 
21             i++,j++;
22         else j = next[j];
23     }
24     return j == pLen?i - j:-1;
25 }
26 
27 int main() {
28     scanf("%s%s",pattern,text);
29     Next(pattern,next);
30     printf("%d\n",KmpSearch(text,pattern));
31 }