LeetCode 周赛已经连续考了两次 KMP 啦，我 KMP 的坑终于填完了……
P.S.如果在阅读的过程中发现哪里不清楚或者某些地方不易懂，欢迎在评论中指出。我会想办法进行改进，让本文变得更好。

KMP 是一种模式匹配算法，要解决的问题可以形式化为：给定模式串 T 与目标串 S，我们要在目标串 S 中寻找 T 的所有出现。

为何暴力算法可以加速

提前剧透一下，KMP 算法使用模式串自己与自己进行匹配，得到了每一个前缀 $T[1\cdots x]$ 的最长相等前后缀（除自身外）的长度，从而在同目标串 S 比较的过程中，省去了暴力算法中无意义的比较。

先来看暴力匹配的过程，比如用 $T=aaaaa$ 去匹配 $S=aaaaaaaaaaaaaaa$。因为每一个可能的出现位置都会完全匹配，所以比较的次数非常多，有 $5\times 11=55$ 次。
可以看一下这个匹配的动图，你可以发现做了很多无意义的比较。

这里的无意义可以理解为能够避免的比较。如果我们知道 $T[0\cdots 3]=T[1\cdots 4]$，假设此时我们完成了一次匹配 $S[0\cdots 4]=T$，那么由等号的传递性，我们就可以知道 $S[1\cdots 4]=T[1\cdots 4]=T[0\cdots 3]$。由此，检查 $S[1\cdots 5]$ 与 $T$ 是否相等，只需要看一看 $S[5]$ 与 $T[4]$ 是否相等即可，后面也是类似，最终只需要比较 $15$ 次就可以得到暴力匹配相同的结果。

这是完全匹配的情况。在失配的时候，$T$ 前缀的最长相等前后缀信息也是可以利用的。

假设在暴力匹配的到了红色部分失配了，我们下一步应该将模式串 T 向后移动一个位置，再从头进行比较。

这个位置肯定是不可以成功匹配的，因为 $T[0\cdots 2]=aba$ 已经与 $S[0\cdots 2]$ 成功匹配了，而 $T[1\cdots 2]=ba\ne ab=T[0\cdots 1]$，我们很容易就可以知道 $T[0\cdots 1]\ne S[1\cdots 2]$。因此，尝试比较 $T$ 与 $S[1\cdots 4]$ 是肯定不可能成功的，是一次无意义的比较。

那么，什么是此时有意义的比较呢？假设我们得知 $T[0\cdots 2]$ 的最长相等前后缀是 $T[0]=T[2]$，那么我们就可以直接将模式串 $T$ 向后滑动，使得现在的 $T[0]$ 对准原本的 $T[2]$ 位置，然后继续向后的匹配。
这样做不仅跳过了一些肯定不能匹配的情况，还保存了之前的部分匹配进度。这种保存部分匹配进度体为在匹配的全过程中，目标串 $S$ 上的匹配指针不需要往回跳。

KMP 算法

PM数组

这一小节我们要按顺序讲清楚四个问题：

• 如何定义模式串内部相等信息
• 为什么是串的每个前缀的相等前后缀
• 为什么要求最长的相等前后缀
• 使用 PM 数组匹配

先看第一个问题，从暴力分析，我们可以了解到利用模式串内部的某种相等信息，我们可以加速匹配。

究竟如何刻画这种相似信息呢？我们定义一个叫做 Partial Matching Table 的东西，翻译过来就是部分匹配数组。它的定义为 $pm[i]$ 表示模式串 $T[0\cdots i]$ 的最长相等前后缀（除自身外）的长度是多少。

举一个简单的例子，$T=abcabcd$，那么 $pm[\cdots ]$ 数组的值如下：

下标	0	1	2	3	4	5	6
字符串	a	b	c	a	b	c	d
pm 数组	0	0	0	1	2	3	0
解释				a=a	ab=ab	abc=abc

给定一个模式串 $T$，这个数组的值你通过肉眼应该很容易就能看出来，可以挡住上面表格的第三行，自行计算一下，看看自己是否理解到位了。

再来看第二个问题，为什么是前后缀？

橘黄色框是我们当前比对的位置，第一行是目标串，第二行和第三行是模式串 T 同目标串进行比较的两个情况：$T[0\cdots 5],S[0\cdots 5]$完成匹配 与 $T[0\cdots 2],S[3\cdots 5]$完成匹配。
我们发现当两种情况对比到目标串的同一个位置的时候，其实我们无形之中借助了目标串对模式串自身进行了比较，比如这种情况 $T[0\cdots 3]=T[3\cdots 5]=S[3\cdots 5]$，而这种比较一定较长的部分模式串（模式串的一个前缀）的后缀（这里是 $T[0\cdots 5]$）同较短的前缀进行比较。又因为是同一个模式串，所以我们就可以看作是模式串的一个前缀的前后缀进行比较。

所以一旦某一个模式串的前缀 $T[0\cdots i]$ 同目标串匹配成功了，那么这个模式串前缀的所有与其后缀相等的前缀也一定能和目标串完成这部分的匹配。在上图中也就是如果第一行目标串和第二行模式串完成了 $T[0\cdots 5]$ 的匹配，那么我们立刻知道 $T[0\cdots 3]=S[3\cdots 5]$，$T[0]=S[5]$。

回答第三个问题，问什么是模式串前缀的最长前后缀。
答案还是看上面的那张图，从第二行和目标串比较，到第三行和目标串比较，再到第四行和目标串比较，这是我们暴力比较的顺序。我们一定会先比较到较长的相等前缀，再去比较较短的相等前缀。
所以为了不重不漏，我们要求模式串前缀的最长相等前后缀。

第四个问题，其实在读懂了前三个问题之后，应该自己就可以得到答案。
我们还是按照暴力匹配的过程将模式串与目标串进行匹配，当失配的时候，我们比较 $S[p]\ne T[q]$ 的时候失配，分两种情况：

• q = 0，那么我们没有啥选择，下一步目标串下一位和模式串从头比较，也就是 $S[p+1]$ 与 $T[0]$ 进行比较。
• q > 0，那么我们找到 $pm[q-1]$，然后将模式串向后移动，使 $T[pm[q-1]]$ 对齐 $S[p]$，下一步比较这两位。

Next 数组

这一节，我们回答两个问题：

• Next 数组是什么
• 如何计算 Next 数组

看完上面的 PM 数组，你可以理解使用它的合理性。但是实际使用起来未免有一些麻烦，因为使用和写代码的过程中总有很多 +1 / -1 需要考虑。

为了提升 KMP 算法的易用性，我们定义 Next 数组为 -1 接上删去最后一位的PM数组，这样有一个好处就是在 $T[x]$ 处失配，我们可以直接通过 $Next[x]$ 跳转，而不是复杂地还要去找 $pm[x-1]$ 然后再移动字符串再从下一位开始继续匹配。

这里在赘述以下 Next 数组的使用方法：我们先暴力匹配的过程将模式串与目标串进行匹配，当失配的时候，我们比较 $S[p]\ne T[q]$ 的时候失配，分两种情况：

• q = 0，下一步目标串下一位和模式串从头比较，也就是 $S[p+1]$ 与 $T[0]$ 进行比较。
• q > 0，我们将模式串向后移动，使 $T[Next[q]]$ 对齐 $S[p]$，下一步比较这两位。

我们可以通过证明使用 Next 数组与使用 PM 数组等价，证明 Next 数组的正确性。

紧接着看如何计算 Next 数组，其实从意义上理解我们是在计算 PM 数组。Next[i] 就是算 $T[0\cdots i-1]$ 的最长前后缀长度是多少，这有两种情况：

• 如果 $T[i-1]=T[Next[i-1]]$，那么 $Next[i]=Next[i-1]+1$。因为 $Next[i-1]$ 存储的是 $T[0\cdots i-2]$ 的最长前后缀，如果能在这个基础上增加 1 个得到 $Next[i]$，那一定是最长的。
• 如果 $T[i-1]\ne T[Next[i-1]]$，那么我们可以把它看作是 $T$ 的前缀和 $T[0\cdots i-1]$ 的匹配问题且在这一步失配了，那么我们可以使用上述的 KMP 算法跳 Next 数组比较 $T[i-1]$ 与 $T[Next[Next[i-1]]]$，再分成现在说的这两种情况考虑。（或者确认模式串此前缀的最长前后缀长度为 0 为止）

KMP 的复杂度分析

这是我很想讲的一个东西，因为我在写文章之前也不会……（我之前可能会，但是现在显然忘光了……

这里我参考了这篇文章 算法导论17：摊还分析学习笔记(KMP复杂度证明) 进行学习，里面介绍了三种算法复杂度分析的高级方法，如果你想了解更多，可以进入原文查看。

目标串为 $S$， 模式串为 $T$，且 $|S|=n,|T|=m$。
这里我就直白地解释一下子，匹配与失配一定伴随着匹配指针移动，所以我们关注会造成匹配指针移动地操作（这里将匹配指针在模式串与目标串分开看）：A.模式串的匹配指针在目标串上向前移动、B.模式串的匹配指针在模式串上向前移动、C.模式串的匹配指针在模式串上跳 Next 数组。
A操作：因为匹配指针在目标串上不会回退，所以 A 操作的次数为 $n$。
B操作：匹配指针在模式串上向前移动一定伴随着 A 操作同时发生，所以 B 操作的次数为 $n$。
C操作：C 操作很难直接想清楚，但是我们可以发现 B 操作可以让模式串上的匹配指针向前移动 1 个，而 C 操作 至少 让模式串上的匹配指针回退 1 个，所以 C 操作一定不比 B 操作多，那么 $C$ 操作的次数至多 $n$ 次。
综上，匹配指针移动的次数是 $O(n)$ 的，所以 KMP 算法匹配的复杂度为 $O(n)$。同理，计算 Next 数组的复杂度为 $O(m)$，那么整个 KMP 的算法复杂度为 $O(n+m)$。

其他链接

原文链接
配套代码
原理 B 站视频讲解
算法ABC目录