50ptsWA球条
查看原帖
50ptsWA球条
1491240
abnegate楼主2025/7/22 22:14
#include<bits/stdc++.h>
#define int long long
using namespace std;
string a,b;
int la,lb; 
int z[20000005];
int p[20000005];
int ansz;
int ansp;
void z_function(){
	//first
	z[0]=0,z[1]=lb;
	int l=0,r=0;
	for(int i=2;i<=lb;i++){
		if(i<=r&&z[i-l+1]<=r-i+1) z[i]=z[i-l+1];
		else{
			z[i]=max(0ll,r-i+1);
			while(b[i+z[i]]==b[z[i]+1]&&i+z[i]<=lb) z[i]++;
		}
		if((i+z[i])>r){
			l=i;
			r=i+z[i]-1;
		}
	}
	//second
	p[0]=0;
	l=r=0;
	for(int i=1;i<=la;i++){
		if(i<=r&&z[i-l+1]<r-i+1) p[i]=z[i-l+1];
		else{
			p[i]=max(0ll,r-i+1);
			while(a[i+p[i]]==b[p[i]+1]&&i+p[i]<=la) p[i]++;
		}
		if(i+p[i]>r){
			l=i;
			r=i+p[i]-1;
		}
	}
}
void calc_ans(){
	ansz=z[1]+1;
	for(int i=2;i<=lb;i++){
		ansz^=i*(z[i]+1);
	}
	ansp=p[1]+1;
	for(int i=2;i<=la;i++){
		ansp^=i*(p[i]+1);
	}
}
signed main()
{
	cin>>a>>b;
	la=a.length();
	lb=b.length();
	a='0'+a,b='0'+b;
	z_function();
	//for(int i=1;i<=lb;i++) cout<<z[i]<<' ';
	//for(int i=1;i<=la;i++) cout<<p[i]<<' ';
	calc_ans();
	cout<<ansz<<'\n'<<ansp;
	return 0;
}



2025/7/22 22:14
加载中...