你所不知道的 KMP 冷知识
KMP 这个名字是由三个人名构成的，你知道吗？
KMP算法由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。
和AC自动机类似的，KMP算法也是一种字符串匹配算法。
只不过KMP适用于单模式串的匹配。而且KMP的next数组应用非常玄学。
可以发现，对于简单的字符串匹配算法，时间大规模的浪费在了重复的比较匹配上面，那么KMP算法用巧妙的预处理将重复的比较省去了。
如下图，在匹配到第六个字符，出现错误，而已经有了
个匹配字符的信息，我们可以根据这个信息，推知
的偏析是无效的，而
的偏移是会有三个字符匹配的，只要从第四个字符开始比较即可。
前缀函数
那么，我们和AC自动机类似的，我们需要知道失配以后的偏移情况。也就是这里的
。简单来说
就是，子串
最长的相等的真前缀与真后缀的长度。
用数学语言描述如下：
特别地，规定
。
举例来说，对于字符串 abcabcd，
，因为 a 没有真前缀和真后缀，根据规定为 0
，因为 ab 无相等的真前缀和真后缀
，因为 abc 无相等的真前缀和真后缀
，因为 abca 只有一对相等的真前缀和真后缀：a，长度为 1
，因为 abcab 相等的真前缀和真后缀只有 ab，长度为 2
，因为 abcabc 相等的真前缀和真后缀只有 abc，长度为 3
，因为 abcabcd 无相等的真前缀和真后缀
同理可以计算字符串 aabaaab 的前缀函数为
。
模版
下面的字符串，我们都假设主串长度为
，模式串的长度为
显然，一个偏移位置就是以
为结尾的后缀和模式串前缀的极大匹配量，我们可以
预处理出来。
需要注意的是，Next数组要比字符串多一位，最后一位表示的是全部匹配以后的偏移。
void Pre_KMP()
{
for (int i=0;i<=m;i++)
Next[i]=0;
int j=0,k=-1;
Next[0]=-1;
while(j<m)
{
if (k==-1||t[j]==t[k]) Next[++j]=++k;
else k=Next[k];
}
}
得到了偏移数组，匹配算法就比较显然了。
两个参数
和
分别是主串和模式串
int KMP(char *S,char *T)
{
int i=0,j=0;
while(i<n&&j<m)
{
if(j==-1||S[i]==T[j]) i++,j++;
else j=Next[j];
}
if(j==m) return i-m;
else return -1;
}
由此可知，KMP算法的预处理时间复杂度是
，匹配的时间复杂度是
，所以总的时间复杂度就是
。
完全的匹配已经没有什么讲的意义了。我们来看一看Next数组的应用。
例题
HDU3336 Count the string
http://acm.hdu.edu.cn/showproblem.php?pid=3336
分析
前缀匹配成功的次数，我们可以利用Next数组。
根据Next数组的性质知，当Next数组有值的时候，就证明肯定有一个匹配，所以我们需要统计出Next数组里面
的个数
但是一个
Next数组位贡献可能不止1，因为他本身后缀的前缀可能也是一个符合要求的
所以我们对于每一个
Next数组位需要向前探查有多少符合要求的前缀，就是他的贡献个数
再加上与自身的匹配
就是答案
#include<bits/stdc++.h>
#define LL long long
#define inf 0x3f3f3f3f
#define P pair<int,int>
using namespace std;
int T,n,m,ans,Next[200010];
char x[200010];
void Pre_KMP()
{
for (int i=1;i<=n;i++)
Next[i]=0;
int j=0,k=-1;
Next[0]=-1;
while(j<n)
{
if (k==-1||x[j]==x[k]) Next[++j]=++k;
else k=Next[k];
}
}
void dfs(int x)
{
if (x==0||x==-1) return ;
ans++;ans%=10007;
dfs(Next[x]);
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
scanf("%s",x);
Pre_KMP();
ans=n%10007;
for (int i=0;i<n;i++)
dfs(Next[i]);
printf("%d\n",ans);
}
return 0;
}
ZOJ1905 Power Strings
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1905
分析
Next数组的经典应用，求最短的循环节，可以得到是
。
那么存在循环节的条件自然就是，
能够整除
。
证明就略了。直观感受以下也不难。
POJ2752 Seek the Name, Seek the Fame
http://poj.org/problem?id=2752
分析
显然
和
是最长公共前后缀
显然
和
也是公共前后缀
如此反复的话，我们直接递归调用即可。
别忘了自己本身也是公共前后缀。
NOI2004 动物园
题意
对于字符串
的前
个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作
。求
。
分析
利用性质：
*
表示
为结尾的字符串的最长公共前后缀（不算本身）
可以得到，满足要求的数量就是不断的跳
，但是要保证
，
为当前位置，
为前缀的结束位置。
但是直接这样跳复杂度不对，题目要求的复杂度是
的。
我们考虑
的计算方式，利用上面的分析可以知道，如果不考虑互相重叠的话，
。
显然
数组是递增的。那么考虑重叠的时候，显然
的值是嵌套的
中，满足比
一半的最后一个位置。
我们可以用类似于kmp匹配的方法。
如果当前位置
像后移动一位，那么他所对应的答案最多也是向后移动一位。
所以，如果当前指向的位置为
，如果能匹配上则继续匹配下一位，当前的答案为
，如果匹配失败就往前跳；另一种情况是，当前的
（
是当前的位置）了，那么也是往前跳。
#include<bits/stdc++.h>
#define LL long long
#define inf 0x3f3f3f3f
using namespace std;
struct kmp
{
char t[1000010];
int Next[1000010],m;
void Pre_KMP()
{
for (int i=0;i<=m;i++)
Next[i]=0;
int j=0,k=-1;
Next[0]=-1;
while(j<m)
{
if (k==-1||t[j]==t[k]) Next[++j]=++k;
else k=Next[k];
}
}
}K;
int T,n;
LL num[1000010];
char s[1000010];
const LL mo=1000000007LL;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%s",K.t);
K.m=strlen(K.t);
K.Pre_KMP();
LL ans=1;
num[0]=0LL;
for (int i=1;i<=K.m;i++)
num[i]=num[K.Next[i]]+1LL;
int k=0;
for (int i=1;i<=K.m;i++)
{
while(k&&K.t[k]!=K.t[i-1]) k=K.Next[k];
if (K.t[k]==K.t[i-1]) k++;
while(k>i/2) k=K.Next[k];
ans=ans*(num[k]+1LL)%mo;
}
printf("%lld\n",ans);
}
return 0;
}
总结常见（奇怪）的应用
以下均指开始下标为
的字符串
- 长度为
字符串的最短循环节长度为
表示
为结尾的字符串的最长公共前后缀（不算本身）
- 前缀
的最长循环节长度为
(不算本身)
for (int i=1;i<=K.m;i++)
if (K.Next[i]==0) f[i]=i;
else f[i]=f[K.Next[i]];