KMP算法

看本文前请先通读算法竞赛进阶指南，本文仅为少许补充。

书中引理解释

我们先来定义“候选项”：以i为结尾的后缀$j_0$个和前缀$j_0$个数相同，则next[i]的值可能是$j_0$，也就称$j_0$是next[i]的候选项。

引理内容

若$j_0$是next[i]的“候选项”不存在“候选项”在next[$j_0$]到$j_0$之间。推论：若next[i]=$j_0$，也就是以i为结尾的后缀$j_0$个和前缀$j_0$个数相同，那么得出只有j = $j_0$或next[$j_0$]或next[next[$j_0$]]或……时，以i为结尾的后缀j个和前缀j个数相同。

证明：

我们沿用书中的反证法，假设在$j_0$和next[$j_0$]中存在$j_1$，其中$j_1$也为“候选项”。

配图解释：

假设next[i] = $j_0$

(1)为1~i的完整字符串。(2)为以i为结尾的$j_0$个字符。(3)为以i为结尾的next[$j_0$]个字符。(4)为以i为结尾的$j_1$个字符。

(5)为以1为首的$j_0$个字符。(6)为以$j_0$为结尾的next[$j_0$]个字符。(7)为以1为首的next[$j_0$]个字符。(8)为以1为首的$j_1$个字符。

已知：(2)和(5)相同，(3)和(7)相同，(6)和(7)相同。

所以(3)和(6)相同。

假设(4)和(8)相同，那么(8)在(5)上肯定有对应后缀串，又由于$j_1$ > next[$j_0$]，所以next[$j_0$]应该为$j_1$，矛盾。所以不存在$j_1 \in (j_0, next[j_0])$，使$j_1$为候选项。

这个引理有什么用？

如果next[i] = j，则next[i - 1] = j - 1，也就是说如果以i为结尾的j个字符和以1为首的j个字符相等时，必有以i - 1为结尾的j - 1个字符和以1为首的j个字符相等。contrapositive后，只有next[i - 1] = j - 1，才可能next[i] = j。

也就是next[i] = $\underset{x}{\operatorname{argmax}}next[i - 1] = j - 1且A[i] = A[j]$。

这样我们对于next[i]求取可以做到很好的剪枝，只需要查询少量可能的j。且我们只需要找到第一个符合的即可，所以A自匹配算法复杂度为O(N)。

知道了next后如何在B中查找A？

A中附加了很多退回信息，这种信息相当于钩子一样。一般而言，一旦不匹配就相当于滑倒底端，从1开始再一个一个匹配。加入了next之后，相当于在半当中被挂住，可以从中间开始继续匹配。