Dyd's Blog

He who has a strong enough why can bear almost any how.

Z函数(拓展KMP)

感觉和 KMP 关系不大啊

Z函数(拓展KMP)

定义

故名思意, Z 函数是个函数,若我们定义一个长度为 n 的字符串以第 i 个字符开头,第 j 个字符结尾(下标从 1 开始)的子串为 s[ij] ,再定义 LCP(x,y) 代表字符串 x,y最长公共前缀长度,那么,有 Z[i]=LCP(s[in],s[0n]) ,即 Z[i] 表示以 i 开头的后缀与原串的最长公共前缀

求法

直接求显然不好,类似 kmp 考虑用已有的信息,结论是,我们同时维护已与前缀匹配上的位置为 s[l,r] ,如有多个(肯定有多个)取 r 最大

当枚举到 i 时,把 Z[i] 初始化为 min(Z[il+1],ri+1) (要保证 ir ),而每次计算完后用 Z[i] 跟新 l,r ,关于正确性,对图理解很显然:Z

考虑时间复杂度,由于 l,r 单调,直接用初始化匹配的复杂度是线性的,而暴力匹配时,原串的每个字符最多被匹配一次,所以是 O(n)

注意, Z[1] 要单独处理

代码

板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define int LL
using LL = long long;
const int N = 2e7 + 100;
char a[N], b[N];
int la, lb, Z[N], p[N], ans;
void get_Z(char x[], int len)
{
Z[1] = len;
for (int i = 2, l = 0, r = 0; i <= len; ++i)
{
if (i <= r) Z[i] = std::min(Z[i - l + 1], r - i + 1);
while (Z[i] + i <= len && x[Z[i] + 1] == x[Z[i] + i]) ++Z[i];
if (i + Z[i] - 1 > r) r = i + Z[i] - 1, l = i;
}
}
void exkmp(char x[], int len, char y[]) //y已有Z数组
{
for (int i = 1, l = 0, r = 0; i <= len; ++i)
{
if (i <= r) p[i] = std::min(Z[i - l + 1], r - i + 1);
while (p[i] + i <= len && y[p[i] + 1] == x[p[i] + i]) ++p[i];
if (i + p[i] - 1 > r) r = i + p[i] - 1, l = i;
}
}
signed main()
{
scanf("%s %s", a + 1, b + 1);
la = strlen(a + 1), lb = strlen(b + 1);
get_Z(b, lb), ans = 0;
for (int i = 1; i <= lb; ++i) ans ^= (Z[i] + 1) * i;
printf("%lld\n", ans);
exkmp(a, la, b), ans = 0;
for (int i = 1; i <= la; ++i) ans ^= (p[i] + 1) * i;
printf("%lld\n", ans);
return 0;
}