KMP 算法的相关证明

声名在先:我站在巨人的肩膀上,才认识了 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 数组的特性做到的,前面简略地说过。
 
请大家看看我是不是有什么写得不完整或不正确的,并指正。谢谢。我的e-mail地址在主页的首页(通常是/personal/index.html)上能找到。

返回“编程天地”