前置
- \(KMP\)：\(O(n)\) 求解字符串匹配的算法。维护前缀数组 \(p_i\) 表示字符串 \(s\) 以 \(i\) 结尾的最长公共前后缀的长度；
- \(border\): 对于字符串 \(s\)，如果存在一个子串 \(t\) 满足 \(t\) 既是 \(s\) 的一个前缀又是 \(s\) 的后缀，则称 \(t\) 是 \(s\) 的一个 border;
Z函数
定义：\(z_i\) 表示字符串 \(s\) 下标从 \(i\) 开始的后缀与 \(s\) 的最长公共前缀 (\(LCP\)) 的长度。这里我们规定字符串下标从 \(0\) 开始。
e.g.
\(\ s: a\ a\ a\ a\ b\ a\ a\ b\)
\(\ i:\ 0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\)
\(z_i: 8\ 3\ 2\ 1\ 0\ 2\ 1\ 0\)
注意，在处理不同的问题时 \(z_0\) 通常为 \(\vert s\vert\) 或 \(0\)。
对于字符串 \(s\) 的下标 \(i\)，如果有 \(Z_i\neq 0\)，那么称区间 \([i,i+z_i-1]\) 为一个 \(Z-box\)（匹配段）。
考虑如何实现求解Z函数。假定区间 \([l, r]\) 为找到的 \(Z-box\) 中 \(r\) 最靠右的哪一个匹配段，当前在考虑第 \(i\) 个位置。
- 若 \(i>r\)，则从下标 \(0\) 开始暴力匹配；
- 若 \(i\le r\)，
- 若 \(i-z_{i-l} - 1 < r\)，那么有 \(z_i=z_{i-l}\)；
- 若 \(i-z_{i-l}-1 \ge r\)，暴力匹配
在每找到一个一个 \(Z-box\)，更新 \(l=i,r=i+z_i-1\)。
单次暴力扩展至少使右端点 \(+1\)，故暴力匹配的总时间是 \(O(n)\) 的。
对于 \(i-z_{i-l}-1 < r\) 的情况。由于 \([l,r]\) 是一个 \(Z-box\)，所以 \(s[0,r-l]=s[l,r]\)，同时因为 \(l\le i\le r\)，有 \(s[i - l, r - l+1]=s[i,r]\)。这时候 \(z_i\) 就相当于是 \(z_{i-l}\)，直接转移即可。
总时间复杂度 \(O(n)\)。
void Solve(string s) {
z[0] = n = s.size();
for(int i = 1, l = 0, r = 0; i < n; i++) {
if(z[i - l] < r - i + 1) {
z[i] = z[i - l];
} else {
for(z[i]= max(0, r - i + 1); i + z[i] < n && s[z[i]] == s[i + z[i]]; z[i]++) { // 暴力扩展
}
l = i, r = i + z[i] - 1;
}
}
}
应用
-
给定字符串 \(s,t\)，求出 \(s\) 的每一个后缀与 \(t\) 的最长公共前缀。
sol: 构造字符串 \(t+特殊字符+s\)，然后求z函数即可。
-
求字符串 \(s\) 的所有 \(border\)。
sol: 对于每一个位置 \(i\)，如果有 \(i+z_i=\vert s\vert\)，则当前以 \(i\) 开头的 \(Z-box\) 是一个 \(border\)。
-
求字符串 \(s\) 的每一个前缀的出现次数。
sol: 对 \(z_i\) 的长度维护后缀和。因为对于位置 \(i\)，若 \(z_i \ne 0\)，则长度在 \([1,z_i]\) 内的前缀均出现了一次。
练习：
完结撒花 \ /\ / \ / \ /
标签：box,前缀,后缀,扩展,KMP,字符串,vert,函数 From： https://www.cnblogs.com/ereoth/p/17757014.html