跳到主要内容

Z 函数（扩展 KMP）

参考资料​

例题​

洛谷 P5410 【模板】扩展 KMP/exKMP（Z 函数）​

洛谷 P5410 【模板】扩展 KMP/exKMP（Z 函数）

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

  • bb 的 zz 函数数组 zz，即 bb 与 bb 的每一个后缀的 LCP 长度。
  • bb 与 aa 的每一个后缀的 LCP 长度数组 pp。

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

代码（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^=(ll)(z[i]+1)*i;
	for(int i=1;i<=n;i++)ans2^=(ll)(z[m+i+1]+1)*i;
	cout<<ans1<<'\n'<<ans2<<'\n';
	return 0;
}