KMP 详解

今天是 8 月 4 日喵，距离退役还有 3 个月左右喵。
写字符串的时候感觉突然悟了，于是来写笔记。

前缀函数

实际上看了 OI Wiki 才知道有这个名词……但是也应该有，因为 KMP 只是一个匹配算法。

定义

约定：为了方便表示，此处字符串下标从 \(1\) 开始；对于串 \(X\)，\(X(i,j)\) 表示截取 \(X\) 的 \([i,j]\) 段。

对于串 \(S\)，其前缀函数 \(P\) 为一个数组，\(P_i\) 表示 \(S(1,i)\) 这段前缀字符串的最长 border（不包含 \(S(1,i)\) 本身）。

呃，什么是 border？简单来说，串 \(X\) 的一个 border 就是 \(X\) 的一对相等的前缀后缀。

举个例子，设 \(X = \texttt{abcssfabc}\)，则 \(\texttt{abc}\) 是 \(X\) 的一个 border。同样的，对于 \(\texttt{abbabba}\) 来说，存在三个 border，即 \(\texttt{a},\texttt{abba},\texttt{abbabba}\)¹。

好了，现在我们设 \(S=\texttt{abcabc}\)，尝试一下求 \(S\) 的前缀函数？如果上面的概念你还没有理解，可以直接参考下图。

于是，\(S\) 的前缀函数则为 \(\left[0,0,0,1,2,3\right]\)

性质

遇到 border 相关要对“跳 border”敏感一些。啥叫跳 border 呢？

拿 \(\texttt{abbabba}\) 来举例子，假设其前缀函数为 \(P\)，容易求得 \(P=[0,0,0,1,2,3,4]\)。
末尾的 \(P_7 = 4\)，代表的是 \(\texttt{abba}\) 这个 border。然后就出现了一个神奇的事情：如果把该串所有合法的 border 按照长度排序，则 \(\texttt{abba}\) 的上一个 border 就是 \(\text a\)。

那这个 \(\texttt a\) 是什么呢？就是 \(P_{P_7}\) 代表的 border 喵。

换句话说，如果 \(X\) 的前缀函数 \(P\) 已知，则：令 \(m\gets X.length\)，反复让 \(m \gets P_m\)，则能够按长度从大到小遍历完原串所有的合法 border。这就是所谓“跳 border”。

线性递推求前缀函数

实际上如果前面的东西你都明白了，这个部分是可以轻松想出来的。

以防万一，我还是写一份思考过程。

假设目前位置是 \(i\)，\(i-1\) 以及之前的 \(P\) 都已知，再令 \(j\gets P_{i-1}\)，想办法递推求出 \(P_i\)。

如果红色部分是 \(S(1,i)\) 的合法 border 且长度不为 \(1\)，则蓝色部分必然是 \(S(1,i-1)\) 的合法 border。

因此，我们可以枚举 \(S(1,i-1)\) 的所有合法 border，看看能不能接上 \(S_i\) 这个字母形成 \(S(1,i)\) 的 border。遍历 border 可以采用上面说过的跳 border 实现。由于这个过程是从长到短遍历，因此找到的合法 border 必然是最长的合法 border。

于是可以反复使 \(j \gets P_j\) 直到 \(S(1,j+1)\) 成为 \(S(1,i)\) 的合法 border。

细节见代码实现。代码实现中认为下标从 \(0\) 开始，nxt 数组即为 \(P\)。

1
2
3
4
5
6
7
8
9
10
11
12
13

void get_nxt(string& str) {
    for (int i = 1, j = 0; i < str.size(); ++i) {
        while (j && str[i - 1] != str[j])
            j = nxt[j];  // 如果 border 不合法就跳，直到没 border 为止
        if (str[i - 1] == str[j])
            ++j;  /* 实际上上面循环完之后的 j 可能是合法 border
                   的结尾也有可能是无解（0），同时如果 border 合
                   法，需要 +1（因为跳 border 的时候跳的是之前的
                   border）*/

        nxt[i] = j;
    }
}

KMP 字符串匹配算法

总的来说：借助前缀函数实现时空复杂度均为 \(\operatorname{O}(n+m)\) 的字符串匹配。

过程和上面递推前缀函数差不多。

具体来讲，为什么要借助前缀函数呢？

假设我们有一个文本串 \(S\)，一个模式串 \(T\)，接下来需要找出 \(S\) 中 \(T\) 出现的所有位置。一旦到 \(T\) 的 \(i\) 这个位置匹配失败，我们难道一定就要返回 \(T_1\) 从头匹配吗？

并不是，我们可以利用 \(T(1,i)\) 的 border 来减少匹配次数。border 的定义是“相等的前缀和后缀”，那 \(T(1,i)\) 的这个后缀匹配成功，其对应的前缀也一定能匹配成功，只需要从这个前缀结束的位置继续匹配即可。

做了个动画：

代码：

1
2
3
4
5
6
7

for (int i = 0, j = 0; i < s.size(); ++i) {
    while (j && s[i] != t[j])
        j = nxt[j];
    if (s[i] == t[j]) ++j;
    if (j == t.size()) // 匹配成功
        cout << i - (int)t.size() + 2 << '\n'; // 答案要求
}