Robbie Mosaic's Web Log

• 

声名在先：我站在巨人的肩膀上，才认识了 KMP 算法。

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 < t，且 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）中字符串最长的一对的字符串长度。

KMP 算法的实现：
为了完成上述的 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] = -1。接下来如果 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 了怎么办？此时 next[j – 1] 是无效的，因为 j – 1 == -1，已经超出 next 数组下标的下界了。要做的事情就是置此 next[i] 为 0，同时让 i 加一。

前面这段只是粗略地说了一说生成 next 数组的过程。现在我来证明一下。

首先，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 数组将被赋以正确的值。

前提：next[0] 到 next[i – 1] 是正确的。t[0] .. t[j – 1] 与 t[i – j] .. t[i – 1] 相等。t[0] .. t[j] 与 t[i – j] .. t[i] 若相等，则是最长真前后缀匹配。

退出条件：与前提一样。

第一个分支条件（t[i] == t[j]）成立的情况：
如果 t[i] 等于 t[j]，则 t[0] .. t[j] 等于 t[i – j] .. t[i]。这说明 next[i] 至少为 j + 1。

现在证明为什么 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] 的匹配的前后缀。这与条件 next 数组原有的数据正确相矛盾。

因此，让 next[i] 等于 j + 1 是正确的。

退出时，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）成立的情况：
如果 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] 是有效的。

退出时，因为 next 数组没有变化，而 i 也没有变化，所以是 next[0] .. next[i – 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[匹配。其次，证明这是最长的。（反证法）假设存在 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。因为上面的论断中，k 小于等于 j1（这是上面的 j1）。而之所以会 next[i – 1] 不等于 j0 是因为这已经不是给 next 数组赋值后第一次到第二个分支条件的处理过程了。也就是说，最近已经多次经过第二个分支条件的处理过程，所以这次的 j0 可以看作上次的 j1。上次的 j0 可以看作再上次的 j1，直到 next[i – 1] 等于某次的 j0 为止。因为 t[i] 不等于 t[j0]，因此 k 小于 j1，然后下一次的 j0 即是这次的 j1，可以用上面的证明过程来证明 k 小于等于下次的 j1。这样，一直下去，直到本次为止（严格的证明必须用数学归纳法）。

因此，如果 t[i] 等于 t[j1]，则 t[0] .. t[j1] 与 t[i – j1] .. t[i] 必是最长的前后缀匹配。

再看退出时 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 数组已赋值。

到此为止，next 数组的生成过程已经说过了。而匹配时则是通过 next 数组的特性做到的，前面简略地说过。

请大家看看我是不是有什么写得不完整或不正确的，并指正。谢谢。

附记：这是我在某个周末，出于兴趣而写的。经过一个多星期才写完。呵呵。