0. 采用什么标准的KMP算法

本文采用的是闫蔚敏版《数据结构》中对 KMP 算法的描述，即模式串下标从 1 开始，而不是更符合编程习惯的从 0 开始。
为了节省篇幅，本文默认读者已经了解了 KMP 算法的基本原理，包括什么是朴素模式匹配算法，以及如何手算 next 数组，所以对这些基础不会讲解非常详细。本文主要分享笔者对如何理解求 next 数组的函数的理解，这也是 KMP 算法的核心和难点。

1. KMP 算法中求 next 数组的代码

本文采用的求 next 数组的代码如下：

int GetNext(char ch[], int length, int next[]) {
	next[1] = 0;
	int i = 1, j = 0; 
	while (i < length) {
		if (j == 0 || ch[i] == ch[j]) {
			i++; j++;
			next[i] = j;
		}
		else {
			j = next[j];
		}
	}
}

关于这段代码，笔者认为比较难理解的地方主要有三个：

1. 变量 i 和 j 的角色是什么？
2. if 语句中的条件 ch[i] == ch[j] 的含义是什么？
3. else 语句中的 j = next[j]; 的含义是什么？

1.1. 定义两个临时概念：指向时后缀和小串

为了方便后面行文的描述，我们引入了两个概念：【指向时后缀】和【小串】。

1.1.1. 指向时后缀

对于一个模式串，假设此时遍历指针指向了模式串中间的某个字符 $P_k$ ，那么【指向时后缀】就是包含了字符 $P_k$ 的后缀。
e.g. 模式串是 "aabacbXbbac" 此时遍历指针指向字符 'X' ，那么指向时后缀是 "aabacbX" ，也可以是 "acbX" ，还可以是 "bX" ，甚至可以是 "X" 。

1.1.2. 小串

假设我们此时正在计算模式串 T 中的第 k 个字符（注意：此时第 k 个字符还没有被处理），那么前 k-1 个字符所组成的模式串子串就是【小串】。
e.g. 模式串 "aabacbXbbac" 的第七个字符是 'X' ，那么我们处理到字符 'X' 的时候，小串就是 "aabacb" 。

2. 回顾手算 next 数组

手算 next 数组的详细过程就不多讲了，我们直接快进到一个具体的场景：

在这里，字符 'o' 和字符 'c' 出现了失配，于是模式串做出向右平移了4个字符的调整。
这是我们手动模拟 KMP 算法时的样子。我们做这样的操作，本质上是在做一件事情：当失配出现时，我们在找此时的指向时后缀和小串的前缀出现重叠的部分。如下图所示：

换句话说，我们其实是在找小串中发生重合的前后缀：

2.1. 手算 next 数组可以得到的两条规律

如果你有完整手算过一条模式串的 next 数组，你会发现：

1. 所谓 next[j] 的数值其实就是长度为 j-1 的小串 $T_{j-1}$ 的前后缀重叠部分的字符个数 + 1 。

之所以小串的长度是 j - 1 ，是因为我们在计算 next[j] 的时候，既然这个值没有算出来，那么第 j 个字符就没有被处理。
以上面的字符串 "aabRaabcabcaa" 为例，第一个字符 'c' 的 next 数组值就是 3 + 1 = 4 。该结果可以手算验证。

2. 模式串的最后一个字符不影响next数组的结果。

这是因为，我们本身就是比较小串 $T_{j-1}$ 的前后缀字符重合数，模式串的最后一个字符无论是什么都不会改变小串的内容。如果计算进行到了最后一个字符并成功匹配，那么算法结束；如果没有匹配，那么调用对应的 next 数组值。

3. 疑难杂症解答

3.1. 变量 i 和变量 j 的角色

直接说结论：变量 i 指向模式串中刚刚被处理完的字符，也就是小串的最后一个字符；变量 j 指向能和小串的后缀所匹配的小串前缀的最后一个字符。
仍然以字符串 "aabRaabcabcaa" 为例，当第一个字符 'c' 即将被处理时，小串的内容是 "aabRaab" ，此时变量 i 被设计为指向第二个字符 'b' ，变量 j 被设计为指向第一个字符 'b' 。

怎么记忆呢？

我们的 GetNext() 函数从一开始就作出了 next[1] = 0; 这样的赋值操作，然后才声明并初始化了 i 和 j 两个整型变量，也就是说先处理了模式串第一个字符的 next 数组值，再让变量 i 指向第一个字符。

至于如何理解变量 j 的角色，我们先来看第二个问题。

3.2. 为什么要判断 ch[i] == ch[j] ？

通过分析 GetNext() 函数的代码我们可以看出来，每一次循环，都会以必然调整指针 j 、可能调整指针 i 的方式结束。也就是说，循环的结果必然造成小串有效前缀的长度发生调整，可能造成小串整体长度 + 1 且最多 + 1（至于为什么是 i++ 和 j++ ，以及 else 分支体中的 j = next[j] 是怎么来的，后面会给出解释）。
其实算法的判断逻辑就是：

1. 如果上一次循环进入了 if 分支，即 i++ 且 j++ ，说明小串的长度 + 1 ，那么必然是小串后缀长度 + 1，同时指向小串前缀的指针 j 也 向右移了一位，即小串前缀长度 + 1。此时只需要比较小串新的前后缀是否匹配。
   打个比方，我们即将处理 "aabRaabcabcaa" 的第一个 'c' 字符，此时 i 指向第二个 'b' ， 'j' 指向第一个 'b' ，小串前缀是 "aab" ，后缀是 "aab" ；等处理完 'c' ，小串变成了 'aabRaabc' ，从CPU的视角来看，小串的后缀变成了 "aab啥" ，小串的前缀变成了 "aab嗯" ，要判断新的前后缀是否重叠，自然要执行 ch[i] == ch[j] ，即比较【哈】是否等于【嗯】。
   比较的结果无非两种。如果等于，那么模式串第九个字符（位于第一个 'c' 之后）的 next 数组值就是 4 ，即有效前缀的长度 + 1，刚好指针 j 指向有效前缀的最后一个字符，所以我们设置了 j++; next[i] = j; 这样的操作；如果不等于是另一种调整，这里先不讲。
2. 如果上一次循环进入了 else 分支，说明上一次小串的前后缀并不匹配，算法重新调整了指针 j 的指向（为什么这样调整暂不解释），用某种方式作出了新的前缀，然后看小串的新前缀能不能找到相匹配的新后缀。
   打个比方，我们已经处理完了 "aabRaabcabcaa" 的第一个字符 'c' ，现在要处理下一个字符，也就是 'a' 。此时 i 指向 'c' ， j 指向 'R' 。比对 ch[i] 和 ch[j] 之后，发现 'R' 和 'c' 并不匹配，调整 j 的位置到 next[j] 处（ j 的值是 4 ， next[4] 是 1 ），即让指针 j 指向模式串的第一个字符，再执行下一次循环。
   新一轮循环中， ch[i] 再次和 ch[j] 不相等（前者是 'c' ，后者是 'a' ），调整 j 的位置到 next[j] ，即 0 ，说明小串的有效前缀没有了，下一次循环就会触发 if 条件中的 j == 0 ，从而引发 i++ 和 j++ 。

3.3. 为什么是 i++ 和 j++

i++ 的原因想必现在很好理解了，因为小串的长度最多增加一个字符，所以指向小串结尾字符的指针自然也最多右移一个字符。
j++ 的原因其实也很好理解。小串长度 + 1 ，那么小串的后缀长度不也就 + 1 吗？和后缀相匹配的有效前缀的长度最多不也就 + 1 吗？

如果有效前缀末尾字符的指针 j 右移一位，发现新的前缀和新的后缀能够匹配，那么当前正在处理的模式串字符（即指针 i 右边的第一个字符）发生失配，模式串就需要向右移动有效前缀长度个字符，即移动 j 个字符。

3.4. 为什么 if 语句的判断中要加入 j == 0

这个问题的答案其实也很好理解了。 j == 0 意味着：实在是没有更短的前后缀可以继续尝试了。

3.5. else 分支体中的 j = next[j] 的原理是什么

这是求 next 数组最核心、最难懂的一行代码，甚至可以说这是整个 KMP 算法的精髓。
假设我们现在要求第 k 个字符的 next 数组值，也就是 next[k] 。
已知小串的最长公共前后缀长度为 j 。现在我们想尝试，当小串长度 + 1 ，如果在公共前缀的基础上往右多加进来一个字符， ch[i] 和 ch[j] 的匹配还能否生效？
匹配成功的情况我们就不多说了。如果失配，那么现状就是：
长度为 j 的公共前后缀不能继续延长。
所以我们尝试：
退回到“这个公共前后缀自身”的最长公共前后缀，再继续尝试。
注意，不是退回到 j - 1 处，也不是退回到 j - 2 处，而是退回到【仍然有希望成为答案】的最长那个长度。
一句话总结：

放弃当前最长公共前后缀，转而尝试它的【次长公共前后缀】。
退一次不够就退两次，两次不够就三次，等退到 j == 0 的时候也就退无可退了。

4. 详细解释 j = next[j] ：为什么可以直接跳到 next[j] ？为什么中间那些长度一定不用检查？

我们用几个图示来证明这一点。
假设有一个抽象模式串， next 数组值已经进行到某一个字符上。这一次小串公共前后缀匹配的情况是，配成：

这触发了 i++ 和 j++ ，计算进行到下一个字符。这一次小串公共前后缀匹配的情况是，失配：

这次的失配意味着：

1. 之前公共前后缀的长度是 j - 1 ，现在公共前后缀的长度已经确认不是 j 了。
2. 我们必须寻找新的公共前后缀 L 。

为了方便表达，我们规定：

上一次匹配成功时，小串是 $T_1$ ，它的公共前后缀的前缀是 $P_1$ ，后缀是 $Q_1$ 。
这一次匹配失败，新小串是 $T_2$ ，它的前缀是 $P_2$ ，后缀是 $Q_2$ 。

具体情况见下图：
于是我们现在要找 $T_2$ 的最长公共前后缀 $L$ 。如果 $L$ 存在，它有可能是这个样子的：

如果用肉眼去看、在草稿纸手算，我们能够轻而易举地找到新的 $L$ ，将直接找 $L$ 的操作转化为代码大致需要：指向 $Q_2$ 末尾的指针往前走，指向 $P_2$ 的指针往后走，等两个指针指向的字符不匹配， $L$ 就得到确认了。
但这不是 KMP ，这还是朴素匹配算法的思想，效率不够高。
所以，现在，看着刚刚的图示，思考：

小串加入进来了一个字符，对吧？
现在变量 i 指向了这个新的字符，对吧？
现在看右边的 $L$ （也就是 $Q_2$ 的后缀 $L$ ），它的最后一个字符就是变量 i 指向的字符，对吧？

将 $L$ 的最长前缀（即 $L$ 取掉变量 i 指向的字符之后的剩余部分）标记为 $LL$ ，你会发现， $LL$ 是 $Q_1$ 的一个后缀。如下图所示：

这样子可能还不是很清晰，我们把图中的信息补充完整，并在关键部分换上我们一开始图示中使用的颜色，看看这样能不能让你建立起联想：

即，我们让指针 j 回退到 $P_1$ 的 $LL$ 后面的第一个字符，这样就又可以利用判断条件 ch[i] == ch[j] 了，成功起到了代码复用的效果。

而 $LL$ 是 $P_1$ 的前缀、 $Q_1$ 的后缀。
且 $P_1=Q_1$ 。
所以 $LL$ 是 $P_1$ 的最长公共前后缀。
当小串是 $P_1$ 的时候，情况如下图所示：

经过计算，字符 α 的 next 数组值为 $LL$ 的长度 + 1。变量 j 的值正是字符 α 的下表，所以通过执行 else 分支体中的 j = next[j] ，我们就成功让指针 j 回溯到 $LL$ 后面一个字符的位置。
这样的回溯一定是最高效、且不会缺失环节的。