题解 P5410 【【模板】扩展 KMP(Z 函数)】

xht

2020-02-21 20:56:10

Solution

> Z 函数,又称**扩展 KMP (exkmp)**,可以 $\mathcal O(n)$ 求出一个字符串的所有后缀与这个字符串的 LCP 长度。 **定义 $z$ 函数** 对于字符串 $s$,$z_i$ 定义为 $|\operatorname{LCP}(s, s[i:])|$,即从 $i$ 开始的后缀与 $s$ 的最长公共子串的长度。 暴力求显然是 $\mathcal O(n^2)$ 的,通常这个时间复杂度都无法被接受。 **$\mathcal O(n)$ 求 $z$ 函数。** 维护 $r$ 最大的匹配子串 $s[l:r]$。 当 $i \le r$ 时,我们充分利用已经算出来的 $z$,直接把 $z_i$ 初始化为 $\min(z_{i-l+1}, r - i + 1)$;否则初始化为 $0$。 然后暴力往后匹配得到 $z_i$ 的最终值,若 $i+z_i-1 > r$,还要更新 $l,r$。 这样做时间复杂度是 $\mathcal O(n)$ 的,因为每个字符最多被暴力匹配一次。 注意 $z_1$ 必须单独处理。 ```cpp inline void Z(char *s, int n) { for (int i = 1; i <= n; i++) z[i] = 0; z[1] = n; for (int i = 2, l = 0, r = 0; i <= n; i++) { if (i <= r) z[i] = min(z[i-l+1], r - i + 1); while (i + z[i] <= n && s[i+z[i]] == s[z[i]+1]) ++z[i]; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } } ``` 对于两串的匹配,过程类似。 代码: ```cpp const int N = 2e7 + 7; int n, m, z[N], p[N]; char a[N], b[N]; inline void Z(char *s, int n) { for (int i = 1; i <= n; i++) z[i] = 0; z[1] = n; for (int i = 2, l = 0, r = 0; i <= n; i++) { if (i <= r) z[i] = min(z[i-l+1], r - i + 1); while (i + z[i] <= n && s[i+z[i]] == s[z[i]+1]) ++z[i]; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } } inline void exkmp(char *s, int n, char *t, int m) { Z(t, m); for (int i = 1; i <= n; i++) p[i] = 0; for (int i = 1, l = 0, r = 0; i <= n; i++) { if (i <= r) p[i] = min(z[i-l+1], r - i + 1); while (i + p[i] <= n && s[i+p[i]] == t[p[i]+1]) ++p[i]; if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1; } } int main() { rds(a, n), rds(b, m); exkmp(a, n, b, m); ll ans = 0; for (int i = 1; i <= m; i++) ans ^= 1ll * i * (z[i] + 1); print(ans); ans = 0; for (int i = 1; i <= n; i++) ans ^= 1ll * i * (p[i] + 1); print(ans); return 0; } ```