首先先讲一下KMP算法作用：
KMP就是来求在给出的一串字符（我们把它放在str字符数组里面）中求另外一个比str数组短的字符数组（我们叫它为ptr）在str中的出现位置或者是次数
这个出现的次数是可以重叠的
例如：在数组 ababa 中 aba的出现次数-----------它的答案是2——————分别是从[0---2] [2---4] 他们是可以重叠的，但是不可以完全重叠（废话T_T）
KMP算法主要有两个模板
1、https://blog.csdn.net/starstar1992/article/details/54913261/ 这个有详解（贼好）
2、https://blog.csdn.net/guhaiteng/article/details/52108690 这个链接中的第一题就是
第一个模板：
假设我们要求str数组的next数组，我们假设str数组长度为len
那么在next数组里面
next[0]、next[1]、next[2]、next[3]........next[len-1]
当数组下标为x的时候，那他对应在数组str中的长度就是[0---x]全闭区间
next数组里面全部存的是数组从0----x这个长度的最长相同前后缀 --------------------前缀长度就是从0到某个点长度，后缀就是从某个点到数组末尾的长度
在这个next数组里面-1代表里面最长相同前后缀为0，next里面的值为0的时候相当于相同前后缀为1，数组里面的值都加1就是他们最大相同的长度
这样做的目的就是为了和next[0]=-1这一句话达成一样
这一句话在循环中起着跳出循环的作用，因此这个-1不能改
这一句话的意义就是：当数组长度为1的时候，他的最长前后缀为-1，而我们又把-1当作0来看，所以（没有所以）
注意：这个next数组的长度开大会出现问题的，要刚好开到str数组的长度，即next[len]
第二个模板：
在第二个模板中next[0]=-1只当作一个跳出循环的条件，并没有实际意义
next[0]、next[1]、next[2]、next[3]............next[len]
可见这个next数组长度比上一个长1，他的next[0]的实际意义在next[1]中，相当于这个模板就是把上一个模板的next值所有向后移动一位
而且这个next里面的值除了第一个其他都大于等于0，我们不需要加1之后再判断
题目：http://poj.org/problem?id=3461
Description
The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter 'e'. He was a member of the Oulipo group. A quote from the book:
Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais…
Perec would probably have scored high (or rather, low) in the following contest. People are asked to write a perhaps even meaningful text on some subject with as few occurrences of a given “word” as possible. Our task is to provide the jury with a program that counts these occurrences, in order to obtain a ranking of the competitors. These competitors often write very long texts with nonsense meaning; a sequence of 500,000 consecutive 'T's is not unusual. And they never use spaces.
So we want to quickly find out how often a word, i.e., a given string, occurs in a text. More formally: given the alphabet {'A', 'B', 'C', …, 'Z'} and two finite strings over that alphabet, a word W and a text T, count the number of occurrences of W in T. All the consecutive characters of W must exactly match consecutive characters of T. Occurrences may overlap.
Input
The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:
- One line with the word W, a string over {'A', 'B', 'C', …, 'Z'}, with 1 ≤ |W| ≤ 10,000 (here |W| denotes the length of the string W).
- One line with the text T, a string over {'A', 'B', 'C', …, 'Z'}, with |W| ≤ |T| ≤ 1,000,000.
Output
For every test case in the input file, the output should contain a single number, on a single line: the number of occurrences of the word W in the text T.
Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
Sample Output
1
3
0
这一道题就是模板题，直接上代码
第一个模板：
1 #include<stdio.h>
2 #include<string.h>
3 const int maxn=1e6+10;
4 int sum;
5 char t[maxn],p[maxn];
6 void call_next(char *ptr,int *next,int len)
7 {
8 next[0]=-1;
9 int k=-1;
10 for(int i=1;i<len;++i)
11 {
12 while(k>-1 && ptr[i]!=ptr[k+1])
13 {
14 k=next[k];
15 }
16 if(ptr[i]==ptr[k+1])
17 {
18 k++;
19 }
20 next[i]=k;
21 }
22 }
23 void kmp(char *str,int slen,char *ptr,int plen)
24 {
25 int next[plen];
26 call_next(ptr,next,plen);
27 int k=-1;
28 for(int i=0;i<slen;++i)
29 {
30 while(k>-1 && str[i]!=ptr[k+1])
31 {
32 k=next[k];
33 }
34 if(ptr[k+1]==str[i])
35 {
36 k++;
37 }
38 if(k==plen-1)
39 {
40 sum++;
41 k=next[k];
42 }
43 }
44 }
45 int main()
46 {
47 int n;
48 scanf("%d",&n);
49 while(n--)
50 {
51 //memset(next,0,sizeof(next));
52 sum=0;
53 scanf("%s%s",p,t);
54 kmp(t,strlen(t),p,strlen(p));
55 printf("%d\n",sum);
56 }
57 return 0;
58 }
第二个模板：
1 #include<stdio.h>
2 #include<string.h>
3 const int maxn=1e6+10;
4 int next[maxn],sum; //着一种方法就不用考虑next数组开的大小
5 char t[maxn],p[maxn];
6 void getnext(const char ptr[],int plen)
7 {
8 int i=0,j;
9 j=next[0]=-1;
10 while(i<plen)
11 {
12 while(j!=-1 && p[i]!=p[j]) j=next[j];
13 next[++i]=++j;
14 }
15 }
16 void kmp(const char str[],int slen,const char ptr[],int plen)
17 {
18 int i,j;
19 getnext(ptr,plen);
20 i=j=0;
21 while(i<slen)
22 {
23 while(j!=-1 && str[i]!=ptr[j]) j=next[j];
24 i++;
25 j++;
26 if(j>=plen) //上一种方法是与plen-1作比较
27 {
28 sum++;
29 j=next[j];
30 }
31 }
32 }
33 int main()
34 {
35 int n;
36 scanf("%d",&n);
37 while(n--)
38 {
39 memset(next,0,sizeof(next));
40 sum=0;
41 scanf("%s%s",p,t);
42 kmp(t,strlen(t),p,strlen(p));
43 printf("%d\n",sum);
44 }
45 }
Description
Step1. Connect the father's name and the mother's name, to a new string S.
Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S).
Example: Father='ala', Mother='la', we have S = 'ala'+'la' = 'alala'. Potential prefix-suffix strings of S are {'a', 'ala', 'alala'}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings of S? (He might thank you by giving your baby a name:)
Input
Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.
Output
Sample Input
ababcababababcabab
aaaaa
Sample Output
2 4 9 18
1 2 3 4 5
题意：给出一个字符串str，求出str中存在多少子串，使得这些子串既是str的前缀，又是str的后缀。并把所有前缀从小到大输出，所后再输出一个数组的长度（不要忘了）
这个时候就是使用next数组来解决问题
我们知道next数组里面的每一个值是从0---x这个长度的最长相同前后缀
在这个长度里面前缀和后缀是一样的，那么我们求这个数组的的前后缀子数组就可以在前缀里面找最长前后缀
就相当于递归一样。。先求出来这个完整数组长度最长相同前后缀（假设这个长度为y），在求出来这个从0-----y这个里面的最长前后缀，因为[0---y]与[len-y----len]是一样的
在[0---y]中找到的后缀肯定能在[len-y---len]中找到相同的后缀，而我们又求出来在这个前缀里面的最长前后缀（设长度为p），这个样子在[0---y]中，[0--p]与[y-p---y]又有了公共部分
此时这个[y-p---y]既可以与前缀有相同部分，又与（整个数组）后缀有相同部分，这就满足题意了
我们要注意当这个next值为0的时候（按第二种模板写的），就要跳出循环，不要继续找了，因为不会再有了
上代码（第二种模板）：
1 #include<stdio.h>
2 #include<string.h>
3 const int maxn=400005;
4 char str[maxn];
5 int next[maxn],ans[maxn];
6 void getnext(int len)
7 {
8 int i=0,j;
9 j=next[0]=-1;
10 while(i<len)
11 {
12 while(j!=-1 && str[j]!=str[i]) j=next[j];
13 next[++i]=++j;
14 }
15 }
16 int main()
17 {
18 while(~scanf("%s",str))
19 {
20 memset(next,0,sizeof(next));
21 int len=strlen(str);
22 getnext(len);
23 int k=next[len];
24 int cnt=0;
25 while(k>0)
26 {
27 ans[++cnt]=k;
28 k=next[k];
29 }
30 for(int i=cnt;i>0;--i)
31 printf("%d ",ans[i]);
32 printf("%d\n",len);
33 }
34 return 0;
35 }
Input
Output
Sample Input
abcd
aaaa
ababab
.
Sample Output
1
4
3
Hint
定理：假设S的长度为len，则S存在循环子串，当且仅当，len可以被len - next[len]整除，最短循环子串为S[len - next[len]]
例子证明：
设S=q1q2q3q4q5q6q7q8，并设next[8] = 6，此时str = S[len - next[len]] = q1q2，由字符串特征向量next的定义可知，q1q2q3q4q5q6 = q3q4q5q6q7q8，即有q1q2＝q3q4，q3q4＝q5q6，q5q6＝q7q8，即q1q2为循环子串，且易知为最短循环子串。由以上过程可知，若len可以被len - next[len]整除，则S存在循环子串，否则不存在。
解法：利用KMP算法，求字符串的特征向量next，若len可以被len - next[len]整除，则最大循环次数n为len/(len - next[len])，否则为1。
1 #include<stdio.h>
2 #include<string.h>
3 const int maxn=1000005;
4 int next[maxn];
5 char str[maxn];
6 void getnext(int len)
7 {
8 int i=0,j;
9 j=next[0]=-1;
10 while(i<len)
11 {
12 while(j!=-1 && str[i]!=str[j]) j=next[j];
13 next[++i]=++j;
14 }
15 }
16 int main()
17 {
18 while(~scanf("%s",str))
19 {
20 if(str[0]=='.') break;
21 int len=strlen(str);
22 getnext(len);
23 if(len%(len-next[len])==0) printf("%d\n",len/(len-next[len]));
24 else printf("1\n");
25 }
26 return 0;
27 }
Description
Input
number zero on it.
Output
Sample Input
3
aaa
12
aabaabaabaab
0
Sample Output
Test case #1
2 2
3 3 Test case #2
2 2
6 2
9 3
12 4
题意：给出一个字符数组str，求这个字符数组里面的子字符数组的最小循环长度，和上一个题差不多，就是这个是求它本身和他的子串的循环长度
，只需要在判断那里多加一个for循环就可以了(网易翻译有毒)
上代码：
1 #include<stdio.h>
2 #include<string.h>
3 const int maxn=1000005;
4 int next[maxn];
5 char str[maxn];
6 void getnext(int len)
7 {
8 int i=0,j;
9 j=next[0]=-1;
10 while(i<len)
11 {
12 while(j!=-1 && str[i]!=str[j]) j=next[j];
13 next[++i]=++j;
14 }
15 }
16 int main()
17 {
18 int k=0,len;
19 while(~scanf("%d",&len))
20 {
21 if(len==0) break;
22 scanf("%s",str);
23 k++;
24 getnext(len);
25 printf("Test case #%d\n",k);
26 for(int i=2;i<=len;++i)
27 {
28 if(i%(i-next[i])==0 && next[i]>0) printf("%d %d\n",i,i/(i-next[i]));
29 }
30 printf("\n");
31 }
32 return 0;
33 }