约定：
- 本文中所有字符串下标均从 $0$ 开始。
- 记 $\vert s\vert$ 表示字符串 $s$ 的长度。
- 记 $s[l,r]$ 表示字符串 $s_ls_{l+1}s_{l+2}\cdots s_r$。
- $s=t$ 表示字符串 $s,t$ 相同。
Z 函数
定义
对于一个长为 $n$ 的字符串 $s$，定义函数 $z_i$ 表示 $s$ 和 $s[i,n-1]$（即以 $s_i$ 开头的后缀）的最长公共前缀（LCP）的长度，则 $z$ 被称为 $s$ 的 Z 函数。特别地，$z_0=0$。
国外一般将计算该数组的算法称为 Z Algorithm，而国内则称其为 扩展 KMP。
过程
其实有点类似于 Manacher 的过程，和 KMP 关系反而不那么深刻（这也是为什么我喜欢叫它 Z 函数，它和 KMP 可能仅仅是求出的东西有点类似之处）。
记字符串为 $s$，$s$ 的 Z 函数为 $z$。
对于计算完成后的 $z$，有 $s[0,z_i]=s[i,i+z_i-1]$。
称 $[i,i+z_i-1]$ 为 $i$ 的匹配段，那么维护最靠右的匹配段 $[l,r]$。
在计算 $z_i$ 过程中，有 $l\leq i$。
在计算 $z_i$ 过程中，如果 $i\leq r$，则有：
\[z_i\geq\min(z_{i-l},r-i+1)\]因为 $s[l,r]=s[0,r-l],s[l,i]=s[0,i-l]$，所以 $s[i,r]=s[i-l,r-l]$。（如图）
所以，$z_i\geq\min(z_{i-l},r-i+1)$。
随后，暴力扩展 $z_i$ 即可。
扩展完之后，记 $k=i+z_i-1$，若 $k>r$，则 $l\leftarrow i,r\leftarrow k$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Z(char a[],int z[]){
int n=strlen(a);
for(int i=1,l=0,r=0;i<n;i++){
if(i<=r){
z[i]=min(z[i-l],r-i+1);
}
while(i+z[i]<n&&a[z[i]]==a[i+z[i]]){
z[i]++;
}
if(i+z[i]-1>r){
l=i,r=l+z[l]-1;
}
}
}
时间复杂度
外层循环显然是 $\mathcal O(n)$ 的。
而对于内层循环，考虑不会更新 $r$ 的情况下，$i+z_i\leq r$，又考虑到 $r$ 单调不降，则内层 while 的时间复杂度为 $\mathcal O(n)$。
总时间复杂度：$\mathcal O(n)$。
例题：扩展 KMP
题中的 $z$ 数组显然就是 Z 函数（特别地，$z_0=\vert b\vert$，而不是 Z 函数定义的 $0$），但是 $p$ 数组似乎有点不一样。
但是仔细思考一下就能发现，将 $a$ 接到 $b$ 的后面求字符串 $ba$ 的 Z 函数 $z’$ 即可求出答案，有 $p_i=\min(\vert b\vert,{z’}_{i+\vert b\vert})$。
记得开 long long。
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=2e7;
typedef long long ll;
char a[N+1],b[N<<1|1];
int z[N+1],p[N<<1|1];
void Z(char a[],int z[]){
int n=strlen(a);
for(int i=1,l=0,r=0;i<n;i++){
if(i<=r){
z[i]=min(z[i-l],r-i+1);
}
while(i+z[i]<n&&a[z[i]]==a[i+z[i]]){
z[i]++;
}
if(i+z[i]-1>r){
l=i,r=l+z[l]-1;
}
}//题目特殊要求
z[0]=n;
}
void P(char a[],char b[]){
for(int i=0;b[i];i++){
if(!b[i+1]){
for(int j=0;a[j];j++){
b[i+1+j]=a[j];
}
break;
}
}
Z(b,p);
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>a>>b;
int sizeB=strlen(b);
Z(b,z);
P(a,b);
ll ansZ=0;
for(int i=0;i<sizeB;i++){
ansZ^=1ll*(i+1)*(z[i]+1);
}
ll ansP=0;
for(int i=0;a[i];i++){
ansP^=1ll*(i+1)*(min(sizeB,p[i+sizeB])+1);
}
cout<<ansZ<<'\n'<<ansP<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
