KMP——字符串匹配的利器

默认所有字符串的下标从 \(1\) 开始。

\(\text{KMP(Knuth-Morris-Pratt)}\) 算法，能够在 \(O(|s| + |p|)\) 的时间复杂度内求出模式串 \(p\) 在文本串 \(s\) 中的出现次数、位置等信息。

众所周知，暴力地进行匹配（也就是对 \(s\) 的每一位都进行与 \(p\) 的比对）的最坏时间复杂度是 \(O(|s| \times |p|)\)，那么 \(\text{KMP}\) 算法是如何将时间复杂度优化这么多的呢？

从暴力的过程入手：不难发现，在匹配的过程中，有很多重复的比对。举个例子，令 $s = $ abab，$p = $ ab，当我们匹配到 \(s[2]\) 时，明明已经知道它和 \(p[2]\) 相等，而 \(p[2] \ne p[1]\)，却还是要在匹配一次。这样的例子数不胜数，放到较长的 \(s\) 和 \(p\) 中，浪费的资源会更多。而 \(\text{KMP}\) 算法就解决了这个问题。

先引入一个 \(nxt[]\) 数组，令 \(suf(i)\) 表示 \(p[1 \dots i]\)，即 \(p\) 以第 \(i\) 个字符为结尾的前缀，\(nxt[i]\) 表示 \(suf(i)\) 的每个前缀和后缀的最长公共元素长度，特别地，\(nxt[1] = 0\)。

真前缀：不等于原字符串的前缀。

真后缀：不等于原字符串的后缀。

再举例：对于 $p = $ abcabcd，

\(nxt[1] = 0\)

\(nxt[2] = 0\)

\(nxt[3] = 0\)

\(nxt[4] = 1,(p[1] = p[4])\)

\(nxt[5] = 1,(p[1 \dots 2] = p[4 \dots 5])\)

\(nxt[6] = 3,(p[1 \dots 3] = p[4 \dots 6])\)

有了 \(nxt[]\)，在失配之后就可以整些高大上的操作了。

再再举例： $s = $ abcabcacd，$p = $ abcabcd 时（配对成功往后跳即可，这里只列举失配的情况）

当 \(i = 7, k = 6\) 时，\(s[i] \ne p[k + 1]\)，让 \(k = nxt[k] = 3\)，此时 \(s[i] = s[k + 1]\)，继续匹配。

可以发现，\(nxt[]\) 帮助我们跳过了 \(s[3 \dots 5]\) 的再次匹配的过程，进而将匹配的时间复杂度优化到了 \(O(|s|)\)。

清楚了这个逻辑，不难写出匹配的代码：

int KMP(char *s, char *p) { //求解出现次数
    int res = 0, k = 0, slen = strlen(s + 1), plen = strlen(p + 1);
    for (int i = 1; i <= slen; i++) {
        while (k && s[i] != p[k + 1]) k = nxt[k]; // k==0时就不必再跳了，不然会死循环
        if (s[i] == p[k + 1]) k++;
        if (k == plen) res++;
    }
    return res;
}

接下来，难点来到了如何求解 \(nxt[]\)。

这里给出递推求 \(nxt[]\) 的方法；

还是就着上面的例子来解释：\(p =\) abcabcd 时

\(nxt[1] = 0\)

\(i = 2, k = 0, p[i] \ne p[k + 1] \Rightarrow nxt[2] = k = 0\)

\(i = 3, k = 0, p[i] \ne p[k + 1] \Rightarrow nxt[3] = k = 0\)

\(i = 4, k = 0, p[i] = p[k + 1] \Rightarrow nxt[4] = k = 1\)

\(i = 5, k = 1, p[i] = p[k + 1] \Rightarrow nxt[5] = k = 2\)

\(i = 6, k = 2, p[i] = p[k + 1] \Rightarrow nxt[6] = k = 3\)

\(i = 7, k = 3, p[i] \ne p[k + 1] \Rightarrow k = nxt[k] = 0, p[i] \ne p[k + 1] \Rightarrow nxt[7] = k = 0\)

不难发现，\(nxt[]\) 的求解过程，其实就是 \(p\) 和 \(p\) 的 \(\text{KMP}\)。

求解代码如下：

void getnxt(char *p) [ //求解nxt[]
    nxt[1] = 0;
    int plen = strlen(p + 1), k = 0;
    for (int i = 2; i <= plen; i++) {
        while (k && p[i] != p[k + 1]) k = nxt[k];
        if (p[i] == p[k + 1]) k++;
        nxt[i] = k;
    }
]

至此，我们便可以在 \(O(|s| + |p|)\) 的时间复杂度内进行字符串匹配了～