KMP算法是一种用于字符串匹配的算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。
入门字符串问题，最难懂的应该就要数KMP算法了吧。
今天，让我们来深入理解一下KMP算法的基本原理和实现方法。
算法解析
KMP算法能够在O(N)的时间内完成字符串自身的匹配，其精髓主要在于next数组。next[i]的意义是在字符串的前 i 个字符中，前缀等于后缀的最长的长度是多少。这么说可能有点抽象，我们来看一下下面这个例子。
对于 ABAABB 这个字符串，他的next数组的值如下所示（为了方便说明，字符串的第一个字符的位置记为1）：
Example
以next[5]举一个更详细的例子：
Example
相信大家对next数组的含义有了清楚的认知，接下来讲一讲怎么求next数组。
利用动态规划（DP）的思想，假设我们现在要求next[i + 1]的值，而next[1] ~ next[i] 全部都已经求出来了，那么我们知道了前i个字符组成的字符串的最长能匹配的前缀和后缀，那么可以直接判断下一个是否相等（记字符串数组为 s[]）：
- 如果二者相等（即 s[next[i]] + 1 == s[i + 1]），那么很显然直接 +1 就可以了。
- 如果二者不相等，那么不断往前跳一个next 来尝试是否能匹配，直到能够匹配时跳出循环，进行转移。
核心代码
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 进行尽量多次的循环，那么这个字符串的构成一定是一段重复的字符，在加上一个不同的字符，并如此反复，具体见下图：
Example
在每一段中A的个数显然是要相同的。如果不同就不能使 while 进行最多次的循环。
证明过程
这样我们就证明了 while 的总循环次数在最坏的情况下是O(N)的，那么KMP算法的总复杂度显然是O(N)的。
网友评论