【模板】扩展 KMP(Z 函数)
题目描述
给定两个字符串 $a,b$,你要求出两个数组:
- $b$ 的 $z$ 函数数组 $z$,即 $b$ 与 $b$ 的每一个后缀的 LCP 长度。
- $b$ 与 $a$ 的每一个后缀的 LCP 长度数组 $p$。
对于一个长度为 $n$ 的数组 $a$,设其权值为 $\operatorname{xor}_{i=1}^n i \times (a_i + 1)$。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 20000010;
typedef long long LL;
int z[N];
int ext[N];
void getext(int n,char *str1,int m,char *str2){
int l = 0,r = 0;
for(int i = 1;i <= n;i ++){
if(l > r){
while(i + ext[i] <= n && 1 + ext[i] <= m && str1[i + ext[i]] == str2[1 + ext[i]])
ext[i] ++;
l = i,r = i + ext[i] - 1;
}
else if(z[i - l + 1] < r - i + 1)
ext[i] = z[i - l + 1];
else{
ext[i] = r - i + 1;
while(i + ext[i] <= n && 1 + ext[i] <= m && str1[i + ext[i]] == str2[1 + ext[i]])
ext[i] ++;
l = i,r = i + ext[i] - 1;
}
}
}
void getz(int n,char *str){
int l = 0,r = 0;
z[1] = n;
for(int i = 2;i <= n;i ++){
if(i > r){
while(str[i + z[i]] == str[1 + z[i]])
z[i] ++;
l = i,r = i + z[i] - 1;
}
else if(z[i - l + 1] < r - i + 1)
z[i] = z[i - l + 1];
else{
z[i] = r - i;
while(str[i + z[i]] == str[1 + z[i]])
z[i] ++;
l = i,r = i + z[i] - 1;
}
}
}
char a[N],b[N];
int main(){
scanf("%s%s",a + 1,b + 1);
a[0] = b[0] = '#';
int n = strlen(a) - 1,m = strlen(b) - 1;
getz(m,b);
LL ans = 0;
for(int i = 1;i <= m;i ++)
ans ^= 1ll * i * (z[i] + 1);
cout << ans << endl;
getext(n,a,m,b);
ans = 0;
for(int i = 1;i <= n;i ++)
ans ^= 1ll * i * (ext[i] + 1);
cout << ans << endl;
return 0;
}