发布于 ,更新于 

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}\)1

好了,现在我们设 \(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;
}
}
证明

口胡一个。

每次 \(j\) 指针最多右移 \(1\),除此以外 \(j\) 指针只会左移。
容易发现右移最多 \(\Theta(n)\)次,则左移也不会超过 \(\Theta(n)\)次。
计算前缀函数的过程只涉及 \(j\)指针的左移右移,所以复杂度 \(\Theta(n)\)。

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'; // 答案要求
}

  1. border 在能不能包含原串这方面没有权威定义,实际上 border 这个概念就只是有一部分人在用,仅用于理解。↩︎