KMP算法详解

http://www.matrix67.com/blog/archives/115

上面的文章虽然讲的很详细不过还是没看太懂

看了下面的公式和讲解思想明了

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 char w[10001],p[1000001];
 4 int next[10001];
 5 long num;
 6 void fnext(char *c1)
 7 {
 8     int i,j,k1;
 9     k1 = strlen(c1);
10     j = -1;
11     next[0] = -1;
12     for(i = 1 ; i < k1 ; i++)
13     {        
14         while(j>-1&&c1[i]!=c1[j+1])
15             j = next[j];
16         if(c1[i]==c1[j+1])
17             j++;
18         next[i] = j;
19     }
20 }
21 void kmp(char *c1,char *c2)
22 {
23     int k1,k2,i,j = -1;
24     k1 = strlen(c1);
25     k2 = strlen(c2);
26     next[0] = -1;
27     for(i = 0 ; i < k2 ; i++)
28     {
29         while(j>-1&&c2[i]!=c1[j+1])
30         j = next[j];
31         if(c2[i]==c1[j+1])
32             j++;
33         if(j==k1-1)
34         {
35             j = next[j];
36             num++;
37         }
38     }
39 }
40 int main()
41 {
42     int i,j,t,k;
43     scanf("%d%*c", &t);
44     while(t--)
45     {
46         num = 0;
47         gets(w);
48         gets(p);
49         fnext(w);
50         kmp(w,p);
51         printf("%ld\n",num);
52     }
53     return 0;
54 }

http://poj.org/problem?id=3080

KMP+暴力

感觉写复杂了。

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 char w[61];
  4 int next[10001];
  5 long num[101];
  6 typedef struct node
  7 {
  8     char c[61];
  9     int k;
 10 }st;
 11 st m[1001];
 12 char p[11][61];
 13 void fnext(char *c1)
 14 {
 15     int i,j,k1;
 16     k1 = strlen(c1);
 17     j = -1;
 18     next[0] = -1;
 19     for(i = 1 ; i < k1 ; i++)
 20     {        
 21         while(j>-1&&c1[i]!=c1[j+1])
 22             j = next[j];
 23         if(c1[i]==c1[j+1])
 24             j++;
 25         next[i] = j;
 26     }
 27 }
 28 int kmp(char *c1,char *c2)
 29 {
 30     int k1,k2,i,j = -1,flag = 0;
 31     k1 = strlen(c1);
 32     k2 = strlen(c2);
 33     next[0] = -1;
 34     for(i = 0 ; i < k2 ; i++)
 35     {
 36         while(j>-1&&c2[i]!=c1[j+1])
 37         j = next[j];
 38         if(c2[i]==c1[j+1])
 39             j++;
 40         if(j==k1-1)
 41         {
 42             flag = 1;
 43             break;
 44         }
 45     }
 46     return flag;
 47 }
 48 int pa(char *x,int n)
 49 {
 50     int y,f = 1;
 51     fnext(x);
 52     for(y = 1; y < n ; y++)
 53         if(!kmp(x,p[y]))
 54         {
 55             f = 0;
 56             break;
 57         }
 58     return f;
 59 }
 60 int main()
 61 {
 62     int i,j,t,k,o,max,n,y,f,pf;
 63     char x[61],str[61];
 64     scanf("%d%*c", &t);
 65     while(t--)
 66     {
 67         o = 0;
 68         int g = 0;
 69         for(i = 0 ; i <= 60 ; i++)
 70             m[i].k = 0;
 71         scanf("%d%*c",&n);
 72         gets(w);
 73         for(i = 1 ; i < n ; i++)        
 74         gets(p[i]);        
 75         for(i = 0 ;i <strlen(w) ; i++)
 76         {
 77             g = 0;
 78             x[g] = w[i];
 79             x[g+1]='\0';        
 80             f = 1;
 81             pf = 0;
 82             if(pa(x,n))
 83             {
 84                 j = i;
 85                 while(pa(x,n)&&j<strlen(w))
 86                 {
 87                     pf = 1;
 88                     j++;
 89                     g++;
 90                     x[g] = w[j];
 91                     x[g+1] = '\0';                    
 92                 }
 93                 if(pf)
 94                     x[g]='\0';
 95                 o++;
 96                 strcpy(m[o].c,x);
 97                 m[o].k = strlen(x);
 98             }
 99         }
100         max = 0;    
101         for(i = 1 ; i <= o ; i++)
102             if(m[i].k>max)
103                 max = m[i].k;
104         for(i = 1; i <= o ; i++)
105             if(m[i].k == max)
106             {
107                 strcpy(str,m[i].c);
108                 break;
109             }
110         for(i = 1; i <= o ; i++)
111             if(m[i].k == max)
112             {
113                 if(strcmp(str,m[i].c)>0)
114                 strcpy(str,m[i].c);
115             }
116         if(max<3)
117             printf("no significant commonalities\n");
118         else
119             puts(str);
120     }
121     return 0;
122 }

补一篇写next函数的写的很好

http://blog.csdn.net/justlovetao/article/details/6737174