【算法】KMP 算法详解

请注意,本文编写于 256 天前,最后修改于 256 天前,其中某些信息可能已经过时。

直接进入正题

定义 $nxt[i]$ 为 $t[0] -- t[i - 1]$ 中前后缀匹配最长长度,即,有最大长度为 $nxt[i]$ 的相同前缀后缀, $t[0] -- t[nxt[i] - 1]$ 分别和 $t[i - nxt[i]] -- t[i - 1]$ 一一匹配

算法流程:

  • 假设现在文本串 $S$ 匹配到 $i$ 位置,模式串 $T$ 匹配到 $j$ 位置

    • 如果当前字符匹配成功(即 $s[i] = t[j]$) , $i , j$ 自增,匹配下一个字符
    • 如果当前字符匹配失败(即 $s[i] \neq t[j]$ ),显然 $i$ 不变,而 $j = nxt[j]$

      • 为什么这么跳是合法的?因为已经匹配了 $j - 1$ 个
      • 也就是说 $s[i - j] -- s[i - 1]$ 已经和 $t[0] -- t[j - 1]$ 一一匹配
      • 而且 $t[0] -- t[nxt[j] - 1]$ 又与 $t[i - nxt[j]] -- t[j - 1]$ 一一匹配
      • 所以显然 $s[i - nxt[j]] -- s[i - 1]$ 和 $t[0] -- t[nxt[j] - 1]$ 一一匹配
      • 所以原来的 $j -> nxt[j]$ 下次直接匹配 $i$ 和 $nxt[j]$

观察仔细的人可能已经发现,如果一直不匹配到 $j = 0$ 时,仍然不匹配,就会陷入死循环。所以我们将 $nxt[0]$ 拿出来设为 $ -1$

所以当我们求出 $nxt$ 数组之后,它提供的 跳跃 功能能够大大减少时间复杂度

如何求 $nxt$ 数组?

$nxt$ 数组考虑的是除当前字符外的最长相同前后缀,其实就是求出以每个点为结尾的最长相同前后缀向后移动一位,并将第零个位置设为 $-1$

根据上面匹配的方法,发现可以用来求 $nxt$ 数组

  • 假设我们已经求出了前 $i$ 位的 $nxt$ ,当前处理第 $i$ 个字符,求第 $i + 1$ 位的 $nxt$ (想想为什么),且$j = nxt[i]$

    • 如果当前字符匹配成功(即 $t[j] = t[i]$ ),当前匹配长度为 $j + 1$ ,即 $nxt[++ i] = ++ j$
    • 如果当前字符匹配失败(即 $t[j] \neq t[i]$ ),那么 $j$ 向前跳,即 $j = nxt[j]$

      • 请通过上面匹配的原理证明这样求得 $nxt$ 方法的正确性

具体代码如下:

//s为模板串,t为匹配串
int ls = strlen(s) , lt = strlen(t);
i = 0 , j = -1;
nxt[0] = -1;
while(i < lt) {
    if(j == -1 || t[i] == t[j]) nxt[++ i] = ++ j;
    else j = nxt[j];
}
i = j = 0;
while(i < ls) {
    if(j == -1 || s[i] == t[j]) {++ i; ++ j;}
    else j = nxt[j];
    if(j == lt) {printf("%d\n" , i - lt + 1) , j = nxt[j];}
}

小优化
观察发现假如在匹配时,当 $s[i] \neq t[j]$ 时,下一次匹配必然是 $s[i]$ 和 $t[nxt[j]]$ 。假设 $t[j] = t[nxt[j]]$ ,显然匹配会再次失败,所以需要使得 $t[j] \neq t[nxt[j]]$

代码如下:

nxt[0] = -1;
while(i < lt) {
    if(j == -1 || t[i] == t[j]) {
        ++ i; ++ j;
        if(t[i] != t[j]) nxt[i] = j;
        else nxt[i] = nxt[j];
    }
    else j = nxt[j];
}
Comments

添加新评论