今天是 8 月 4 日喵，距离退役还有 3 个月左右喵。
写字符串的时候感觉突然悟了，于是来写笔记。
前缀函数
实际上看了 OI Wiki 才知道有这个名词……但是也应该有，因为 KMP
只是一个匹配算法。
定义
约定：为了方便表示，此处字符串下标从 开始；对于串 ， 表示截取 的 段。
对于串 ，其前缀函数 为一个数组， 表示 这段前缀字符串的最长
border（不包含 本身）。
呃，什么是 border？简单来说，串 的一个 border 就是 的一对相等的前缀后缀。
举个例子，设 ，则 是 的一个 border。同样的，对于 来说，存在三个
border，即 。
好了，现在我们设 ，尝试一下求
的前缀函数？如果上面的概念你还没有理解，可以直接参考下图。
于是， 的前缀函数则为
性质
遇到 border 相关要对“跳 border”敏感一些。啥叫跳 border 呢？
拿
来举例子，假设其前缀函数为 ，容易求得 。
末尾的 ，代表的是 这个
border。然后就出现了一个神奇的事情：如果把该串所有合法的 border
按照长度排序，则
的上一个 border 就是 。
那这个 是什么呢？就是
代表的 border 喵。
换句话说，如果 的前缀函数
已知，则：令 ，反复让 ，则能够按长度从大到小遍历完原串所有的合法
border。这就是所谓“跳 border”。
线性递推求前缀函数
实际上如果前面的东西你都明白了，这个部分是可以轻松想出来的。
以防万一，我还是写一份思考过程。
假设目前位置是 ， 以及之前的 都已知，再令 ，想办法递推求出 。
如果红色部分是 的合法
border 且长度不为 ，则蓝色部分必然是 的合法 border。
因此，我们可以枚举
的所有合法 border，看看能不能接上 这个字母形成 的 border。遍历 border
可以采用上面说过的跳 border
实现。由于这个过程是从长到短遍历，因此找到的合法 border 必然是最长的合法
border。
于是可以反复使 直到
成为 的合法 border。
细节见代码实现。代码实现中认为下标从 开始，nxt 数组即为 。
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];
if (str[i - 1] == str[j])
++j;
nxt[i] = j;
}
}
复制 |
证明
口胡一个。
每次 指针最多右移 ，除此以外 指针只会左移。
容易发现右移最多 次，则左移也不会超过 次。
计算前缀函数的过程只涉及 指针的左移右移，所以复杂度 。
KMP 字符串匹配算法
总的来说：借助前缀函数实现时空复杂度均为 的字符串匹配。
过程和上面递推前缀函数差不多。
具体来讲，为什么要借助前缀函数呢？
假设我们有一个文本串 ，一个模式串 ，接下来需要找出 中 出现的所有位置。一旦到 的 这个位置匹配失败，我们难道一定就要返回
从头匹配吗？
并不是，我们可以利用 的
border 来减少匹配次数。border 的定义是“相等的前缀和后缀”，那
的这个后缀匹配成功，其对应的前缀也一定能匹配成功，只需要从这个前缀结束的位置继续匹配即可。
做了个动画：
代码：
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';
}
复制 |
