KMP算法主要用于高效解决单模式串的匹配问题，即：
给定主串s和模式串p，问p是否是s的子串（len(s)<=N, len(p)<=M）。
先考虑最朴素的算法，即枚举s中的起点i，检查s[i..i+M-1]是否等于p，这样的时间复杂度为O(NM)。
分析一下为什么这样的算法效率低：设指针i和j分别指向s和p中的字符，不妨假定s[0..k-1]和p[0..k-1]已经匹配上了，而s[k]!=p[k]（k<M），这说明s[0..M-1]已经不能匹配上p了，根据朴素算法，指针i将移动到s[1]，指针j将移动到p[0]重新开始匹配，之后每次失配时主串中的指针i都要回到前面，这就产生了不必要的麻烦。但是如果指针i不回溯而是停在s[k]处，就会漏掉s[l..l+M-1]和p[0..M-1]（0<l<k）匹配上的情形。那么为了提高效率实现指针i不回溯，我们来重点考察如何弥补这些被漏掉的情形（见下图）：
假定存在这样的l（0<l<k）使得s[l..l+M-1]和p[0..M-1]匹配上了，那么有s[l..k-1]=p[0..k-l-1]，由于之前已经匹配上的部分说明了s[l..k-1]=p[l..k-1]，于是推出p[0..k-l-1]=p[l..k-1]，也就是说这样的l会使得p[0..k-1]的长度为k-l的前缀和后缀完全相同！如果令next[k]=k-l的话，那么一旦在p[k]处失配，指针i不需要回溯，而指针j只需要指向模式串的next[k]处继续与主串比较就可以了！这就是KMP算法思想的出发点。
那么接下来我们要解决的，就是如何计算next数组。设next[k]=r，根据上一段的分析我们知道r是使得p[0..k-1]的前缀和后缀完全相同的最大长度（之所以选择最大长度是因为，当再次失配的时候可以继续把指针j向前移，就会移到较小的使前后缀完全相同的长度上）。考虑利用递推的方式来求next数组，假定我们已知next[i]=j，现在求next[i+1]：
（图片改自http://blog.csdn.net/yutianzuijin/article/details/11954939）
如果p[i]=p[j]，那么自然有next[i+1]=j+1；如果p[i]!=p[j]，那么从定义出发，next[i+1]是最大长度r（r<=j）使得p[0..r-1]=p[i-r+1..i]，由next[i]的性质可以推出p[i-r+1..i]=p[i-r+1..i-1]+p[i]=p[j-r+1..j-1]+p[i]，所以如果p[i]=p[r-1]，那么r就满足p[0..r-2]=p[j-r+1..j-1]，这表明next[j]=r-1，即next[i+1]=next[j]+1，此时相当于p[i]=p[next[j]]；如果仍然有p[i]!=p[next[j]]，那么仿照上面的推导过程，只需要比较p[i]和p[next[next[j]]]，形成这样一个递归过程：不断令j=next[j]，直到最后p[i]等于p[j]或者j=-1为止（如果令next[0]=-1的话），然后令next[++i]=++j就可以了。下面是对模式串p计算next数组的代码：
void CountNext(char p[])
{
int i = 0, j = -1;
next[0] = -1;
while (i < lenp)
if (j == -1 || p[i] == p[j])
next[++i] = ++j;
else j = next[j];
}
有了next数组以后就可以实现第一段中陈述的匹配过程了，用指针i指向主串s，指针j指向模式串p，如果s[i]=p[j]或者j=-1（指针j回溯过头），那么两个指针各向后移动一位，如果s[i]!=p[j]，那么就将j向前移动到next[j]处，即令j=next[j]。当j=len(p)的时候，匹配就成功了，而当i=len(s)的时候，匹配就失败了。下面是利用next数组进行单模式串匹配的代码：
void KMP(char s[], char p[])
{
int i = 0, j = 0;
while (i < lens)
{
if (j == -1 || s[i] == p[j])
++i, ++j;
else j = next[j];
if (j == lenp)
printf("One matched!\n"), j = next[j];
}
}
可以看出两段代码具有很高的相似度。上面这段代码中，将完成一次匹配看作是在p[len(p)]处失配，这样就可以继续查找主串后面的部分与模式串的匹配情况了。
整个KMP算法的时间复杂度为O(N+M)，效率非常高。
KMP算法的执行过程比较容易掌握，但next数组性质的应用却非常灵活。
Problems
题意：求模式串p在主串s中出现的次数（len(p)<=10,000, len(s)<=1,000,000）。
KMP模板题，每次匹配成功计数器自增1即可。提醒：strlen()函数的复杂度是O(L)不是O(1)。
1 // Problem: poj3461 - Oulipo
2 // Category: KMP Algorithm
3 // Author: Niwatori
4 // Date: 2016/07/23
5
6 #include <stdio.h>
7 #include <string.h>
8
9 int next[10010];
10 int lens, lenp;
11
12 void CountNext(char p[])
13 {
14 int i = 0, j = -1;
15 next[0] = -1;
16 while (i < lenp)
17 if (j == -1 || p[i] == p[j])
18 next[++i] = ++j;
19 else j = next[j];
20 }
21
22 int KMP(char s[], char p[])
23 {
24 int i = 0, j = 0, cnt = 0;
25 while (i < lens)
26 {
27 if (j == -1 || s[i] == p[j])
28 ++i, ++j;
29 else j = next[j];
30
31 if (j == lenp)
32 ++cnt, j = next[j];
33 }
34 return cnt;
35 }
36
37 int main()
38 {
39 int t; scanf("%d", &t);
40 while (t--)
41 {
42 char p[10010], s[1000010];
43 scanf("%s%s", p, s);
44 lenp = strlen(p);
45 lens = strlen(s);
46 CountNext(p);
47 printf("%d\n", KMP(s, p));
48 }
49 return 0;
50 }
POJ2752 - Seek the Name, Seek the Fame
题意：给定字符串s（len(s)<=400,000），求使得s的前缀与后缀完全相同的所有长度。
如果理解了上面next数组的求法，那么很容易知道这题只需从len(s)处开始，不断调用next数组，最后把所有结果逆序输出即可。
1 // Problem: poj2752 - Seek the Name, Seek the Fame
2 // Category: KMP Algorithm
3 // Author: Niwatori
4 // Date: 2016/07/23
5
6 #include <stdio.h>
7 #include <string.h>
8 #define MAXL 400010
9
10 int len, next[MAXL];
11
12 void CountNext(char p[])
13 {
14 int i = 0, j = -1;
15 next[0] = -1;
16 while (i < len)
17 if (j == -1 || p[i] == p[j])
18 next[++i] = ++j;
19 else j = next[j];
20 }
21
22 int main()
23 {
24 char s[MAXL];
25 while (scanf("%s", s) == 1)
26 {
27 len = strlen(s);
28 CountNext(s);
29
30 int i = len, cnt = 0, ans[MAXL];
31 while (i > 0)
32 {
33 ans[cnt++] = i;
34 i = next[i];
35 }
36 for (int i = cnt - 1; i >= 0; --i)
37 printf("%d ", ans[i]);
38 printf("\n");
39 }
40 return 0;
41 }
题意：给定字符串s（len(s)<=1,000,000），求其最小循环节的循环次数。
字符串s存在非平凡最小循环节的充要条件是len % (len - next[len]) == 0，且最小循环节的长度就等于len - next[len]，否则最小循环节就是整个串s。理由见下图（摘自网络）：
类似地可以解决另一个问题：给定字符串s，求其满足（多次复制后能包含原串）的子串的最小长度。例如对于abcabcab，答案为3，取abc即可。实际上这个问题就是求len-next[len]，原理与上图类似。
1 // Problem: poj2406 - Power Strings
2 // Category: KMP Algorithm
3 // Author: Niwatori
4 // Date: 2016/07/23
5
6 #include <stdio.h>
7 #include <string.h>
8 #define MAXL 1000010
9
10 int len, next[MAXL];
11
12 void CountNext(char p[])
13 {
14 int i = 0, j = -1;
15 next[0] = -1;
16 while (i < len)
17 if (j == -1 || p[i] == p[j])
18 next[++i] = ++j;
19 else j = next[j];
20 }
21
22 int main()
23 {
24 char s[MAXL];
25 while (scanf("%s", s) == 1)
26 {
27 if (!strcmp(s, ".")) break;
28 len = strlen(s);
29 CountNext(s);
30
31 if (len % (len - next[len]) == 0)
32 printf("%d\n", len / (len - next[len]));
33 else printf("1\n");
34 }
35 return 0;
36 }
题意：给定一个字符矩阵，求其满足（多次复制后能包含原矩阵）的子矩阵的最小面积（矩阵高R<=10,000，宽C<=75）。
可以看出这道题就是上面那个问题的二维版本。为了叙述方便，以下称多次复制后能包含原串的子串为好串，多次复制后能包含原矩阵的子矩阵为好矩阵。
显然好矩阵可以取为原矩阵左上角的一块，我们只要求出其高度与宽度即可。这里有一个技巧，把矩阵的每一行都看成一个字符，那么整个矩阵就可以看成长度为R的模式串，好矩阵的高度就等于这个串的最小好串长度，问题化为了一维的情形。然后对列进行同样的处理，求出好矩阵的宽度，再把宽与高一乘就得到了答案。由于在计算next数组的过程中每次比较矩阵的两行或两列都会用到strcmp函数，所以上面做法的时间复杂度为O(RC)。
1 // Problem: poj2185 - Milking Grid
2 // Category: KMP Algorithm
3 // Author: Niwatori
4 // Date: 2016/07/23
5
6 #include <stdio.h>
7 #include <string.h>
8 #define MAXR 10010
9 #define MAXC 80
10
11 template <class T>
12 void CountNext(T s, int next[], int len)
13 {
14 int i = 0, j = -1;
15 next[0] = -1;
16 while (i < len)
17 if (j == -1 || !strcmp(s[i], s[j]))
18 next[++i] = ++j;
19 else j = next[j];
20 }
21
22 int main()
23 {
24 char s1[MAXR][MAXC] = {0}, s2[MAXC][MAXR] = {0};
25 int r, c, next1[MAXR], next2[MAXC];
26 scanf("%d%d", &r, &c);
27 for (int i = 0; i < r; ++i)
28 scanf("%s", s1[i]);
29 for (int i = 0; i < c; ++i) // Transpose
30 for (int j = 0; j < r; ++j)
31 s2[i][j] = s1[j][i];
32
33 CountNext(s1, next1, r); // Compute for rows
34 CountNext(s2, next2, c); // Compute for columns
35 printf("%d", (r - next1[r]) * (c - next2[c]));
36 return 0;
37 }