KMP模板

 1 ///KMP模板
 2 ///生成next数组
 3 void get_next()
 4 {
 5     int i=0,j=-1;
 6     next[0]=-1;
 7     while (s1[i])
 8     {
 9         if (j==-1||s1[i]==s1[j])
10         {
11             i++;
12             j++;
13             next[i]=j;
14         }
15         else j=next[j];
16     }
17 }
18 
19 ///计算该子串在字符串中出现的次数
20 int kmp()
21 {
22     int i=0,j=0,k=0,len;
23     len=strlen(s1);
24     while (s2[i])
25     {
26         if (j==-1||s1[j]==s2[i])
27         {
28             j++;
29             i++;
30         }
31         else j=next[j];
32         if (j==len)
33         {
34             k++;
35             j=next[j];
36         }
37     }
38     return k;
39 }
40 
41 /// 计算每个子串在该字符串中的位置
42 for (i=strlen(s);i!=0;)
43 {
44     a[j++]=next[i];
45     i=next[i];
46 }
47 for (i=j-2;i>=0;i--)
48    printf("%d ",a[i]);
49    
50 ///计算循环节
51 if(len%(len-next[len])==0)
52     printf("%d\n",len/(len-next[len]));
53 else
54     printf("1\n");