数据结构复健 (一): 字符串算法
前缀函数与 KMP 算法
前缀函数
定义
对于一个长度为 \(n\) 的字符串 \(s\), 其最大相等前后缀长度为 \(k\) 当
\[s[0\cdots k-1]=s[n-k+1\cdots n]\]且 \(k\) 是满足这一条件的最大值. 对于整个字符串, 其前缀函数就是一个长度为 \(n\) 的数组 \(\pi[n]\), 其中 \(\pi[i]\) 的值为 \(s[0\cdots i]\) 的最大相等前后缀长度. 特别地, 规定 \(\pi[0]=0\)
例如, 字符串
\[abcdabcde\]就有
\[\pi=\{0,0,0,0,1,2,3,4,0\}\]前缀函数的计算
朴素算法
trivial \(O(n^3)\)
匹配优化
注意到相邻两项有 \(\Delta\pi\le 1\), 这是因为 于是可以在朴素算法的前提下进行优化, 将 \(\pi[n]\) 的枚举上界设为 \(\pi[n-1]+1\), 这样一来, 容易证明时间复杂度为 \(O(n^2)\).
失配优化
在上一个优化中, 我们处理了 \(\pi_{n+1}\) 的最优情况, 即完成匹配, 下面讨论无法完成匹配的情况, 容易发现, 下一个应该尝试的长度最大为 \(\pi_{\pi_n - 1}\), 这是因为其为满足 \(s[0\cdots i-1]=s[n-i+1\cdots n]\) 的次大 \(i\).
这样一来, 我们就可以得到一个 \(O(n)\) 的算法了.
实现
void prefix_funtion(std::string s) {
int n = s.size();
vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[j - 1];
while (j && s[j] != s[i])
j = pi[j - 1];
if (s[i] == s[j])
j++;
pi[i] = j;
}
}
应用
KMP 算法
过程
给定一个文本串 \(t\) 与模式串 \(s\), 尝试找到 \(s\) 在 \(t\) 中的所有出现.
算法
考虑问题的本质: 是否在 \(t\) 中存在一段 \(t[i\cdots i+n-1]\) 使得其与 \(s\) 完全相等, 显然, 这可以转化为一个求前缀函数的问题, 构造字符串 \(s+\#+t\) 其中 \(\#\) 代表一个无义分隔符. 接下来, 考虑在 \(n+1\) 之后的区域考虑前缀函数, 显然, 找到匹配当且仅当 \(\pi_i=n\).
求字符串的周期
若字符串内存在一个 \(l\) 的周期, 则显然其有一段长度为 \(n-l\) 的相等前后缀. 于是, 根据求前缀函数的方式可以找到 \(s\) 的最小周期, 通过失配优化可以找到其所有周期.
统计每个前缀的出现次数
寻找 \(s\) 的每一个前缀的出现次数, 朴素方法是跑 \(n\) 次 KMP, 时间复杂度在平方量级, 但是通过失配优化, 很容易变成线性.
字符串压缩
与字符串周期是类同的, 证明比较烦.
字符串哈希
定义
把字符串映射为一个整数, 注意时间复杂度与 Hash 的准确率 (避免 Hash 碰撞) .
应用
字符串匹配
求文本串每个字串的哈希值, 与模式串直接比较即可.
允许 k 次失配的字符串匹配
匹配时允许至多有 \(k\) 个位置上的字符不同 (\(k\) 较小) . 考虑哈希+二分, 可以在每一次匹配过程中用 \(O(\log n)\) 的时间找到所有失配字符, 总时间复杂度为 \(O(km\log n)\).
最长回文子串
枚举回文中心+二分, \(O(n\log n)\), 好像 \(O(n)\) 哈希也可以, 先咕.
AC 自动机
什么是自动机？
自动机的本质是一个状态转移函数
\[\delta(v, c)\]其中 \(v\) 代表一个状态, \(c\) 代表一个新输入的字符. 这个函数的输出结果是一个新的状态, 也即: 一个自动机在接受一个字符后由一种状态切换到另一种状态. 有一些熟知的例子:
- Trie 树: 接受一个字符后, 向下沿着树边走到一个子节点；
- KMP 自动机: 接受一个字符后, 若匹配, 将状态变为 \(v+1\), 若失配, 变为 \(\delta(\pi(i),c)\).
而 AC 自动机就是上面两者的结合.
用途
一个文本串, 多个模式串进行匹配
失配优化
核心是在 Trie 树上跑失配指针. 例如, 对于字符串 abcd, bce, cf 构成的 Trie 树, 若读入 abc 后在 d 处失配, 将会把指针跳到 bce 字符串的 bc 后进行匹配, 若再次失配, 将跳到 cf 的 f 后进行匹配, 依此类推.
实现
首先是建立失配指针的过程
void build() {
queue<int> q;
for (int i = 0; i < 26; i++)
if (tr[0][i])
q.push(tr[0][i]);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++) {
if (tr[u][i]) { // 子节点存在, 让 fail 指针指向父节点 (拓扑序保证父节点 fail 指针的最优性)
fail[tr[u][i]] = tr[fail[u]][i];
q.push(tr[i][i]);
} else { // 子节点不存在, 直接跳转
tr[u][i] = tr[fail[u]][i];
}
}
}
}
接下来, 进行匹配时, 只需要不断跳指针即可
int e[MAXN]; // e[i] 表示以 i 结尾的模式串个数
int query(std::string t) {
int u = 0, ans = 0;
for (auto ch: t) {
u = tr[u][ch - 'a']; // 一步到位跳到失配节点
for (int j = u; j && e[j] != -1; j = fail[j]) {
ans += e[j]; // 把每一个匹配都记录
e[j] = -1; // 已经匹配到了
}
}
return ans;
}