KMP 算法的相关证明

对于一个模式字符串（pattern string），名为 t，要在文本 s 中搜索它的第一个匹配位置。先一个一个字母比较，即 t[0] 和 s[0] 比较，t[1] 和 s[1] 比较，以此类推。当比较结果相等时则进行下一次比较，当比较结果不相等时就要使用特殊方法了：为了提高效率，不让 s[i] 后退。此时，设比较到 t[j] 时不相等，而 t[0] .. t[j - 1] 都已经经过了比较，并且都是相等的。现在就要把 j 向前移动到这样的一个位置 k，这个位置之前的字符，t[0] .. t[k - 1] 与 t[j - k] .. t[j - 1] 是相等的，并且 k 要尽量大，然后再继续比较 t[k] 与 s[i] 是否相等。如果不存在这样一个有效的位置 k，那么让 j = 0 并且 i 增加 1。

这里要注意两个条件：一，k 要尽量大；二，继续从 t[k] 与 s[i] 比较。这是为什么呢？k 如果不是尽量大，比如现在有且仅有 k1 与 k2，k1 满足 0 <= k1 < j，且 t[0] .. t[k1 - 1] 等于 t[j - k1] .. t[j - 1]，k2 也同样满足这样的条件，并且 k2 > k1。如果要满足尽量大的条件，应该用 k2。但是如果不用满足这样的条件，我们用 k1 的话，会出现什么情况？设 t 的长度为 m，若 s[i] .. s[i + m - k2 - 1] 等于 t[k2] .. t[m - 1]，则从 t[k2] 开始与 s[i] 匹配整个搜索将成功。现在不从 k2 开始而从 k1 开始，就跳过了这样的位置，就算匹配成功也不是在 s 中第一个匹配了。因此 k 要尽量大。如果取的数不满足 t[0] .. t[k - 1] 等于 t[j - k] .. t[j - 1] 怎么办？那么前面 s[i - k] .. s[i - 1] 就与 t[0] .. t[k - 1] 不相等了。这就不符合搜索的意义了。

然后，认清了这个条件，就可以把这条件简单地说了：当 t[j] 与 s[i] 不相等时，让 j = k，此 k 是 t[0] .. t[j - 1] 所有真前缀（不等于整个字符串的前 r 个字符组成的字符串）与真后缀（类似真前缀的定义）相等的对（pair）中字符串最长的一对的字符串长度。

为了完成上述的 j 到 k 的跳转，先要生成一张列表，我们称它为 next，采用数组的格式，即为 next 数组。next[j] 等于 t[0] .. t[j] 中所有真前缀（不等于整个字符串的前 r 个字符组成的字符串）与真后缀（类似真前缀的定义）相等的对（pair）中字符串最长的一对的字符串长度（我们简称这个长度为前后缀最大匹配长度）。那么怎样高效地生成这样的表呢？我们来看代码：

void kmpMakeTable(int *next, char *str2)

{

int i, j;

next[0] = 0;

i = 1; j = 0;

while (str2[i]) {

if (str2[i] == str2[j]) {

next[i] = j + 1;

i++; j++;

* there is no problem about whether str2[j] is valid,

* because j is always not more than i

} else if (j > 0) {

/* Note 1 */

j = next[j - 1];

} else {

/* Note 2 */

next[i] = 0;

i++;

}

以上代码是 KMP 算法中生成 next 数组的一段代码。其中的 str2 对应上面讨论中的 t，即模式字符串（pattern string）。我们可以看到：初始时设 i = 1 和 j = 0，并设 next[0] = 0。接下来如果 str2[i] 与 str2[j] 相等，next[i] 就一路等于 j + 1。由我们的定义，next[i] 应等于 next[0] .. next[i] 的前后缀最大匹配长度。那么是不是这样计算就保证这一点了呢？我们可以看见，如果从一开始 str2[i] 就等于 str2[j]，然后一直下去，易见这种情况下 str2[0] .. str2[i] 都是同一个字符，显然 j + 1 就是前后缀最大匹配长度。如果某个时候 str2[i] 不等于 str2[j] 了，程序就会执行到下面两个分支条件中的一个。

发生 str2[i] 不等于 str2[j] 的情况，可以称之为“失配”，此时先经过的是第一个分支（Note 1）。第一个分支的条件是 j > 0，做的事情是让 j 变为 next[j - 1]，这个其实就是前面说的从 t[j] 转到 t[k] 的过程。（提示：next 数组中记录的是前后缀最大匹配长度，此长度即为 k，匹配的字符串是 t[0] .. t[k - 1] 与 t[j - k] .. t[j - 1]）。之后再会进行下一轮循环，试图验证 str2[i] 与 str2[j] 的匹配。如果 j == 0 了怎么办（Note 2）？此时 next[j - 1] 是无效的，因为 j - 1 == -1，已经超出 next 数组下标的下界了。要做的事情就是置此 next[i] 为 0，同时让 i 加一。

首先，next 数组初始的状态是符合条件的。i 初始值为 1，j 初始值为 0，满足 t[0] .. t[j - 1] 等于 t[i - j] .. t[i - 1] 或者 0 > j - 1 并且 i - j > i - 1（即作为字符串是空串），长度 0 也是最大的（因为 t[0] .. t[i] 只包含一个字符，它唯一的真前缀是空串，唯一的真后缀也是空串）。

现在证明为什么 next[i] 不能超过 j + 1。（反证法）假设 next[i] = k 是正确的，k > j + 1。那么 t[0] .. t[k - 1] 等于 t[i - k + 1] .. t[i]，并且它们分别是 t[0] .. t[i] 的真前缀与真后缀。于是 t[0] .. t[k - 2] 等于 t[i - k + 1] .. t[i - 1]，这说明 t[0] .. t[j - 1] 与 t[i - j] .. t[i - 1] 不是最长的 t[0] .. t[i - 1] 的匹配的前后缀。这与条件 next 数组原有的数据正确相矛盾。

退出时，已经递增了 i 和 j。next[0] 到 next[i - 1] 是正确的。t[0] .. t[j] 与 t[i - j] .. t[i] 若相等，则必是最长真前后缀匹配（理由同上）。t[0] .. t[j - 1] 与 t[i - j] .. t[i - 1] 相等。

如果 j > 0，此时 t[i] != t[j]，从而 t[0] .. t[j] 与 t[i - j] .. t[i] 不匹配。为了寻找下一个匹配，将 j 设为 next[j - 1]。 next[j - 1] 中保存的是 t[0] .. t[j - 1] 这个字符串的最长前后缀匹配的长度，这就让 j 指向这个匹配的前缀的后面一个字符。同时可以看到，因为 j < i，所以 next[j - 1] 是有效的。

现在来证明 t[0] .. t[j] 若等于 t[i - j] .. t[i]，则这是最长的匹配。首先，证明当 t[j] 等于 t[i] 的情况下这是匹配。让我们称进入时的 j 为 j0，退出时的 j 为 j1。因为 t[0] .. t[j0 - 1] 与 t[i - j0] .. t[i - 1] 是匹配，并且 t[0] .. t[j1 - 1] 等于 t[j0 - j1] .. t[j0 - 1]，所以 t[0] .. t[j1 - 1] 等于 t[i - j1] .. t[i - 1]，因此这是匹配。其次，证明这是最长的。（反证法）假设存在 t[0] .. t[k]，i > k > j，使 t[0] .. t[k] 等于 t[i - k] .. t[i] 成立。显然 t[0] .. t[k - 1] 等于 t[i - k] .. t[i - 1]。从而 next[i - 1] 至少应是 k。

如果 next[i - 1] 等于 j0。此时 t[i] != t[j0]，而 next[i - 1] 等于 j0，因此 k 不可能大于等于 j0。那么 k 有没有可能大于 j1 呢？若 k 大于 j1，则表示 k > next[j0]。如前述，t[0] .. t[j1 - 1] 等于 t[i - j1] .. t[i - 1]。因为 t[0] .. t[k - 1] 等于 t[i - k] .. t[i - 1]，并且 k < j0，并且 t[0] .. t[j0 - 1] 等于 t[i - j0] .. t[i - 1]，所以 t[0] .. t[k - 1] 等于 t[j0 - k] .. t[j0 - 1]，这与 j1 是 t[0] .. t[j0 - 1] 之间的最长匹配前后缀的长度相矛盾。因此 k 必然小于等于 j1。

如果 next[i - 1] 不等于 j0。之所以会 next[i - 1] 不等于 j0 是因为这已经不是给 next 数组赋值后第一次到第二个分支条件的处理过程了（如果前一次经过的是第一个分支，或者是从初始状态进入第二个分支的，那么 next[i - 1] 将会等于 j0）。也就是说，最近已经连续多次经过第二个分支条件的处理过程，所以这次的 j0 可以看作上次的 j1。上次的 j0 可以看作再上次的 j1，直到 next[i - 1] 等于某次的 j0 为止。因为 t[i] 不等于 t[j0]，因此 k 小于 j1，然后下一次的 j0 即是这次的 j1，可以用上面的证明过程来证明 k 小于等于下次的 j1。这样，一直下去，直到本次为止（严格的证明必须用数学归纳法）。

再看退出时 t[0] .. t[j1 - 1] 是不是等于 t[i - j1] .. t[i - 1]。应该说上面的证明过程用到了这个事实。不过分开说的话可能看起来清楚些。当 next[i - 1] 等于 j0 时，因为 j1 是 next[j0]，从而 t[0] .. t[j1 - 1] 等于 t[j0 - j1] .. t[j0 - 1]，而 t[0] .. t[j0 - 1] 等于 t[i - j0] .. t[i - 1]，又 j0 > j1，因此 t[0] .. t[j1 - 1] 等于 t[i - j1] .. t[i - 1]。

这只有当 j 等于 0 时才可能。此时 j - 1 小于 0，next[j - 1] 无意义。而在上面讨论的过程中说到过，k 小于等于 j1，而上面的 j1 到了此处就是 j，它的值是 0，所以 next[i] 应该等于 0。同时 i++ 表示 next 的当前元素已赋值。