Z-algorithm
Algorithm
Task
给定一个文本串 (S) 和一个模式串 (T)，求 (T) 对于 (S) 的每个后缀子串的公共前缀子串。
Limitations
要求时空复杂度均为线性
Solution
设 (X) 是一个字符串，则以下表述中，(X_u) 代表 (X) 的第 (u) 个字符，(X_{u sim v}) 代表 (X) 的从 (u) 起到 (v) 结束的字串。
设 (n = |S|,~m = |T|)。
考虑按照长度由大到小扫描 (S) 的后缀字串，设当前要求 (S_{i sim n}) 与 (T) 的公共前缀子串，则 (forall k in [1, ~i),~S_{k sim n}) 的答案都已计算完成。
设先前的计算中，匹配到 (S) 最远的一次为第 (p) 次，即 (p + ans_p) 在所有 (k + ans_k) 中最大，设 (q = p + ans_p)。显然有 (p < i)。
首先不妨设 (q geq i)。(q < i) 的情况将在下方说明。
设 (j = i - p + 1)，不难发现 (T_j = S_i)，即 (j) 是 (S_i) 的对应匹配位置。
由于所求是公共前缀字串，因此有
引入一组辅助变量，设 (next_j) 为 (T_{j sim m}) 与 (T) 的最长公共前缀子串长度。
根据定义，有
分两种情况讨论。
第一种情况，(j + next_j < q)，即 (T_{j sim j + next_j}) 是 (S_{p sim q}) 的字串，因此有
又因为 (T_{j sim j + next_j} = T_{1 sim next_j})（已证），等量代换得到
对于 (S_i + next_j + 1)，则可以用反证法证明其不等于 (T_{next_j + 1})，否则由于 (T_{j + next_j + 1}) 依然是 (S_{p sim q}) 的字串，所以 (T_{j + next_j + 1} = T_{next_j + 1})，这与 (next_j) 是最长前缀公共子串矛盾。
因此，对于这种情况，答案即为 (next_j)。
第二种情况，(j + next_j geq q)，即 (T_{j sim j + next_j}) 不全是是 (S_{p sim q}) 的字串，因此有
首先可以用与第一种情况相同的证明方式证明 (S_{i sim q} = T_{1 sim q - i + 1})，即 (q) 及以前的字符可以与 (T) 完美匹配，而对于 (q) 后面的字符，我们暴力将其与 (T) 匹配，同时更新 (p) 和 (q) 的位置即可。
对于 (q < i) 的情况，显然 (q = i - 1)，直接继续暴力进行匹配即可。
考虑时间复杂度：
除掉暴力匹配的环节，剩下的部分显然都是单次 (O(1)) 完成，因此这一部分的复杂度是线性的。
考虑每次暴力匹配都会让 (q) 右移，所以暴力匹配的次数是线性的，而单次暴力匹配是 (O(1)) 的，因此算法的时间复杂度是线性的。
考虑 (next) 数组的计算：我们发现这相当于令文本串 (S = T)，只需要预处理 (next_1) 与 (next_2)，可以发现从 (next_3) 起，计算所需要的 (next) 值都已经在之前被计算过。
Sample
【P5410】 【模板】扩展 KMP
Description
给定一个文本串 (S) 和一个模式串 (T)，求 (T) 对于 (S) 的每个后缀子串的公共前缀子串。并输出 (T) 的每个后缀字串与 (T) 的公共前缀子串长度。
Limitations
字符串长度不超过 (10^5)
Solution
板板题。算法在实现上比较吃细节，注意比较大于小于的时候是否应该加等于号。记得对拍
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
const int maxn = 100005;
int nxt[maxn];
char S[maxn], T[maxn];
void Z_algorithm(const char *const A, const char *const B, const int x, const int y, const bool pt);
int main() {
freopen("1.in", "r", stdin);
scanf("%s
%s", S + 1, T + 1);
int x = strlen(S + 1), y = strlen(T + 1);
nxt[1] = y;
Z_algorithm(T, T, y, y, false);
for (int i = 1; i <= y; ++i) {
qw(nxt[i], i == y ? '
' : ' ', true);
}
Z_algorithm(S, T, x, y, true);
putchar('
');
return 0;
}
void Z_algorithm(const char *const A, const char *const B, const int x, const int y, const bool pt) {
int p = 0, q = 1;
if (!pt) {
while ((q < x) && (A[q] == A[q + 1])) ++q;
nxt[p = 2] = q - 1;
q = std::max(q, 2);
} else {
while ((q <= x) && (q <= y) && (A[q] == B[q])) ++q;
p = 1;
qw(--q, ' ', true);
}
for (int i = pt ? 2 : 3, _ans; i <= x; ++i) {
int a = i - p + 1;
int len = nxt[a];
if ((i + len - 1) >= q) {
_ans = std::max(0, q - i + 1);
while ((q < x) && (_ans < y) && (A[q+1] == B[_ans+1])) {
++_ans; ++q;
}
q = std::max(p = i, q);
} else {
_ans = len;
}
if (pt) {
qw(_ans, ' ', true);
} else {
nxt[i] = _ans;
}
}
}