KMP算法

本文参考资料：https://www.zhihu.com/question/21923021

KMP算法是一种字符串匹配算法，可以在 \(O(n+m)\) 的时间复杂度内实现两个字符串的匹配。

字符串匹配问题

首先我们需要了解一下什么是字符串匹配问题。

比如给你两个串 \(s1\)，\(s2\)，问你 \(s1\) 是否为 \(s2\) 的子串，以及每次出现在 \(s2\) 中的位置，其中称 \(s1\) 为模式串，\(s2\) 为主串。看看下面这张阮行止老师的图：

我们可以发现，对于字符串 no 的匹配结果是在主串中出现了 1 次，位置为 6，对于字符串 ob 的匹配结果就是在主串中出现过 2 次，出现的位置分别为 1 和 10。

生活中有很多类似的问题，比如当你在成绩单里找自己的名字或者说在小说的章节里面查找你所想看的带有某个关键字的部分，都是和这个是差不多的。

Brute-Force

直译过来就是暴力破解的意思，所以这个算法也是非常的暴力，首先，我们应该如何实现两个字符串 \(s1\)，\(s2\) 的比较？所谓字符串比较，就是问“两个字符串是否相等”。最朴素的思想，就是从前往后逐字符比较，一旦遇到不相同的字符，就返回 False；如果两个字符串都结束了，仍然没有出现不对应的字符，则返回 True。

那么我们理解了如何判断两个字符串相等的话，我们就可以想到，假设要查询 \(s1\) 是否为 \(s2\) 的子串，我们可以枚举 \(s2\) 的每一个点为起点，然后截取与 \(s1\) 长度相等的一段串，来判断是否相等，就可以暴力判断出 \(s1\) 在 \(s2\) 中的出现位置了。

当然这个算法的复杂度是很大的，在一般情况下是会 T 飞的，所以我们需要对其进行改进。

Brute-Force的改进

上图为 Brute-Force 的最坏情况，可以看到复杂度并不乐观，所以有了这一部分。
我们很难降低字符串比较的复杂度（因为比较两个字符串，真的只能逐个比较字符）。因此，我们考虑降低比较的趟数。如果比较的趟数能降到足够低，那么总的复杂度也将会下降很多。要优化一个算法，首先要回答的问题是“我手上有什么信息？”　我们手上的信息是否足够、是否有效，决定了我们能把算法优化到何种程度。请记住：尽可能利用残余的信息，是 KMP 算法的思想所在。

在 Brute-Force 中，如果从 \(s2[i]\) 开始的那一趟比较失败了，算法会直接开始尝试从 \(s2[i+1]\) 开始比较。这种行为，属于典型的“没有从之前的错误中学到东西”。我们应当注意到，一次失败的匹配，会给我们提供宝贵的信息——如果 \(s2[i]\) 到 \(s2[i+len[s1]]\) 与 \(s1\) 的匹配是在第 \(r\) 个位置失败的，那么从 \(s2[i]\) 开始的 \(r-1\) 个连续字符，一定与 \(s1\) 的前 \(r-1\) 个字符一模一样！

所以我们可以发现，以从 \(i\) 到 \(r-1\) 为开头的那一段区间是不可能是 \(s2\) 中 \(s1\) 的起点的，也就是说，中间的那一块 \(i\) 到 \(r-1\) 的位置，是不用再去比较的！

这时候我们需要一个新的东西——next 数组。

\(next\) 数组是对于模式串而言的。\(s1\) 的 \(next\) 数组定义为：\(next[i]\) 表示 \(P[0]\) ~ \(P[i]\) 这一个子串，使得 前k个字符恰等于后 \(k\) 个字符的最大的 \(k\). 特别地，\(k\) 不能取 \(i+1\)（因为这个子串一共才 \(i+1\) 个字符，自己肯定与自己相等，就没有意义了）。
上图给出了一个例子。\(s1=\)"\(abcabd\)"时，\(next[4]=2\)，这是因为 \(P[0]\) ~ \(P[4]\) 这个子串是 "\(abcab\)"，前两个字符与后两个字符相等，因此 \(next[4]\) 取 \(2\). 而 \(next[5]=0\)，是因为"\(abcabd\)"找不到前缀与后缀相同，因此只能取 \(0\).如果把模式串视为一把标尺，在主串上移动，那么 Brute-Force 就是每次失配之后只右移一位；改进算法则是每次失配之后，移很多位，跳过那些不可能匹配成功的位置。但是该如何确定要移多少位呢？

在 \(S[0]\) 尝试匹配，失配于 \(S[3] <=> P[3]\) 之后，我们直接把模式串往右移了两位，让 \(S[3]\) 对准 \(P[1]\). 接着继续匹配，失配于 \(S[8] <=> P[6]\), 接下来我们把 \(P\) 往右平移了三位，把 \(S[8]\) 对准 \(P[3]\). 此后继续匹配直到成功。　　我们应该如何移动这把标尺？很明显，如图中蓝色箭头所示，旧的后缀要与新的前缀一致（如果不一致，那就肯定没法匹配上了）！

回忆 \(next\) 数组的性质：\(P[0]\) 到 \(P[i]\) 这一段子串中，前 \(next[i]\) 个字符与后 \(next[i]\) 个字符一模一样。既然如此，如果失配在 \(P[r]\), 那么 \(P[0]\)~\(P[r-1]\)这一段里面，前 \(next[r-1]\) 个字符恰好和后 \(next[r-1]\) 个字符相等——也就是说，我们可以拿长度为 \(next[r-1]\) 的那一段前缀，来顶替当前后缀的位置，让匹配继续下去！　　您可以验证一下上面的匹配例子：\(P[3]\) 失配后，把 \(P[next[3-1]]\) 也就是 \(P[1]\) 对准了主串刚刚失配的那一位；\(P[6]\) 失配后，把 \(P[next[6-1]]\) 也就是 \(P[3]\) 对准了主串刚刚失配的那一位。