求next数组（暴力版本）
Next[0] = -1
Next[1] = 0
For i = 2...P.len
Next[i] = 0;
For j = i - 1...1
If P[1...j] == P[i - j + 1...i]//P[1...j]是P[1...i]的后缀
Next[i] = j
Break不过上面这个根据定义直接求的算法时间复杂度太高了。如果不优化会成为整个KMP的瓶颈，导致还不如直接用O(P.len * S.len)的暴力算法匹配效率高。要优化求next数组的算法，就需要对next数组有深入的理解。首先要理解，next实际上描述了P的所有前缀字符串两两之间的一种关系
举个例子，P=”bababb”，则P一共有6个前缀，依次是”b”,“ba”, “bab”, “baba”, “babab”, “bababb”。在这6个字符串中，如果P[1..k]恰好是P[1..j]的后缀，我们就连一条从P[1..j]到P[1..k]的虚线，表明这种后缀关系。显然这种后缀关系是一个偏序关系，也就是说如果P[1..i]是P[1..k]的后缀，而P[1..k]是P[1..j]的后缀，那么P[1..i]一定也是P[1..j]的后缀
比如上图中P[1..1]（”b”）是P[1..3]（”bab”）的后缀，P[1..3]（”bab”）是P[1..5]（”babab”）的后缀。 所以P[1..1] （”b”）也是P[1..5] （”babab”）的后缀。特别的，如果P[1..k]是P[1..j]最长的后缀，我们就连一条从P[1..j]到P[1..k]的实线，表明这种最长后缀关系
这个实线表明的”最长后缀关系“，实际上就是next数组。比如P[1..6]指向P[1]对应next[6]=1；P[1..5]指向P[1..3]对应next[5]=3。而且如果我们想知道都有哪些前缀是P[1..j]的后缀，只需要沿着实线也就是next数组往上找即可：P[1..next[j]], P[1..next[next[j]]], P[1..next[next[next[j]]]], … Ø。此外，如果P[1..k]是P[1..j]的后缀，那么各自砍掉最后一个字母后，P[1..k-1]仍是P[1..j-1]的后缀
有了以上两条分析结果，我们就可以来求next数组了。首先令next[0]=-1, next[1]=0。然后我们用递推法依次求出每一个next[j]。假设我们已经求出来next[0], next[1], … next[j]，现在要求next[j+1]
假设next[j+1]的值是k，那么P[1..k]就必须是P[1..j+1]的后缀，所以P[1..k-1]就必须是P[1..j]的后缀（都砍掉最后一个字符）。而之前我们分析得出P[1..j]的后缀分别是P[1..next[j]]， P[1..next[next[j]]], P[1..next[next[next[j]]]], … Ø；所以如果next[j+1]不等于0的话，next[j+1]就只可能是next[j]+1或者next[next[j]]+1或者next[next[next[j]]]+1… 或者1
而我们要求next[j+1]，就要在集合{ next[j]+1，next[next[j]]+1，next[next[next[j]]]+1，…… 1}中找到一个最大的数k，满足P[k]==P[j+1]。如果这样的k存在，那么next[j+1]=k；否则next[j+1]=0
j = Next[0] = -1
For i = 1...P.len
While j >= 0 AND P[j + 1] != P[j]
j = next[j]
Next[i] = ++j下面看一下KMP求匹配的完整代码：
#include <cstring>
#include <cstdio>
using namespace std;
int next[1000001];
int ans;
char p[1000001],s[1000001];
int n,m;
int main()
{
ans = 0;
scanf("%S%S",p + 1,s + 1);
n = strlen(s + 1);
m = strlen(p + 1);
next[0] = -1;
int j = -1;
for(int i = 1;i <= m;i++)
{
while(j >= 0 && p[j + 1] != p[i])
j = next[j];
next[i] = ++j;
}
j = 0;
for(int i = 1;i <= n;i++)
{
while(j >= 0 && p[j + 1] != s[i])
j = next[j];
++j;
if(j == m)
{
ans = i - m + 1;
break;
}
}
printf("%d\n",ans);
return 0;
}首先要注意上面代码中字符串都是从P[1]和S[1]开始的，并不是从下标0开始。并且n和m分别是S的长度和P的长度。第16-21行是在求next数组。第23-33行是在进行KMP匹配。注意其中第28-32行，如果匹配已经进行到j==m，说明P的最后一个字符P[m]也匹配上了，并且匹配到的是S[i]。这里我们是要在S中找P第一次出现的位置，也就是P[1]的位置，所以是i-m+1
例1 题目链接：hihoCoder1015
这道题的大意是给你很多对模式串P和原串S。对于每一对都让你求出P在S中出现了多少次。需要注意出现的P是可以部分重叠的，比如ADA在ADADADA中出现了3次
之前KMP的代码是找到第一次出现的位置就中止了。现在我们需要让KMP在找到一次完整的匹配之后还能继续匹配下去。让匹配继续进行的方法就是，当P[m]匹配S[i]成功时，（这里m是P的长度）令j=next[m]，然后从尝试S[i+1]和P[j+1]匹配继续
以下是完整的代码：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int nxt[1000001];
int ans,t;
char p[1000001],s[1000001];
int n,m;
int main()
{
cin >> t;
while(t--)
{
ans = 0;
scanf("%s%s",p + 1,s + 1);
n = strlen(s + 1);
m = strlen(p + 1);
nxt[0] = -1;
int j = -1;
for(int i = 1;i <= m;i++)
{
while(j >= 0 && p[j + 1] != p[i])
j = nxt[j];
nxt[i] = ++j;
}
j = 0;
for(int i = 1;i <= n;i++)
{
while(j >= 0 && p[j + 1] != s[i])
j = nxt[j];
if(++j == m)
{
ans++;
j = nxt[j];
}
}
cout << ans << endl;
}
return 0;
}首先是c++11中std::next是有定义的，所以为了提交到hihoCoder上不会编译出错，我们把next[]数组的名字改成nxt[]。然后就是第31-35行，这里匹配到j==m说明完成了一个完整匹配之后，我们令j=nxt[j]，就可以让KMP继续找下一个完整匹配的位置。最后ans的值就是答案
