Z 函数（扩展 KMP）

参考资料

Z 函数（扩展 KMP） - OI Wiki

例题

给定两个字符串 $a,b$ ，你要求出两个数组：

$b$ 的 $z$ 函数数组 $z$ ，即 $b$ 与 $b$ 的每一个后缀的 LCP 长度。
$b$ 与 $a$ 的每一个后缀的 LCP 长度数组 $p$ 。

对于一个长度为 $n$ 的数组 $a$ ，设其权值为 $\operatorname{xor}_{i=1}^n i \times (a_i + 1)$ 。

Code (1)

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=40000005;
int z[N];
void get_z(string s,int n)
{
	z[1]=n;
	for(int i=2,l=1,r=1;i<=n;i++)
	{
		z[i]=i<=r?min(z[i-l+1],r-i+1):0;
		while(i+z[i]<=n&&s[i+z[i]]==s[1+z[i]])z[i]++;
		if(i+z[i]-1>r)r=i+z[i]-1,l=i;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string a,b;
	cin>>a>>b;
	int n=a.size(),m=b.size();
	b=' '+b+'$'+a;
	get_z(b,n+m+1);
	ll ans1=0,ans2=0;
	z[1]=m;
	for(int i=1;i<=m;i++)ans1^=(z[i]+1ll)*i;
	for(int i=1;i<=n;i++)ans2^=(z[m+i+1]+1ll)*i;
	cout<<ans1<<'\n'<<ans2<<'\n';
	return 0;
}

参考资料​

例题​

参考资料

例题