KMP算法经典应用（超详细！！！）

如果想了解更多内容，欢迎关注我的微信公众号：信息学竞赛从入门到巅峰。

上期我们讲了关于KMP算法的基本原理和实现，今天我们来证明KMP算法的时间复杂度和一些经典应用（敲黑板，划重点啦~）

 

首先来证明一下时间复杂度是O(N)的（先贴上模板）。

cin >>s;
int m=s.size();
s=" "+s; j=0;
for (int i=2;i<=m+1;++i) {
    while (j>0 && s[j+1]!=s[i])j=p[j];
    if (s[j+1]==s[i])j++;
    p[i]=j;
}

考虑算法中产生计算的地方，第4行的 for 是O(N)的，这点毋庸置疑，主要的问题出在第5行的 while 上，那么我们需要证明的就是这个循环累计是O(N)的。

我们的目标已经明确了，接下来考虑最坏情况。要使 while 进行尽量多次的循环，那么这个字符串的构成一定是一段重复的字符，在加上一个不同的字符，并如此反复，具体见下图：

在每一段中A的个数显然是要相同的。如果不同就不能使 while 进行最多次的循环。

这样我们就证明了 while 的总循环次数在最坏的情况下是O(N)的，那么KMP算法的总复杂度显然是O(N)的。

 

接下来我们来讲一下KMP算法的具体应用（题目来源洛谷，侵删）。

洛谷P4391

这道题是KMP的经典应用：求循环节。

根据next数组的性质，我们可以知道一个字符串前缀等于后缀的最大长度l，这字符串全长为 L ，那么这个字符串的循环节长度就是 （L - l）。

为什么是这样呢？看下面这张图就很容易理解了。

很显然，这个字符串的循环节长度为2。

洛谷P3375

这道题是KMP算法的另一个经典用法：匹配字符串。

求next数组就不说了，我们来说说求一个字符串在另一个字符串里出现的位置，我们从头开始匹配，若匹配不上，就尝试不断跳next数组进行匹配。若匹配得上，就匹配；否则，继续在next数组里往前跳。

next数组其实是一个fail指针，可类比AC自动机（不知道也没关系，很快会推出AC自动机算法的讲解）。最大前缀等于最大后缀，说明我们可以减少几个字符继续匹配，而不是从头开始匹配，这样提高了程序的运行效率。这样的尝试总复杂度是O(N)的，证明类似于KMP算法时间复杂度的证明。