Z函数22分求调
查看原帖
Z函数22分求调
1270559
zkhehe楼主2024/8/29 21:54
#include <bits/stdc++.h>
using namespace std;
string a="",b="";
int z[40000010];
int f(string x,string y){
	string s=x+'#'+y;
	int len=s.size();
	int lenx=x.size();
	
	int l=0,r=0;
	for(int i=1;i<len;i++){
		int k=(i>=r)?0:min(r-i+1,z[i-l]);
		while(s[i+k]==s[k]){
			k++;
		}
		z[i]=k;
		if(i+k-1>r){
			r=i+k-1;
			l=i;
		}
	}
	int ans=0;
	for(int i=lenx+1;i<len;i++){
		ans=ans^((i-lenx)*(z[i]+1));
	}
	return ans;
}
void read(string &x){
	char ch=getchar();
	while(ch<'a'||ch>'z')ch=getchar();
	while(ch>='a'&&ch<='z')x+=ch,ch=getchar();
}
int main(){
	read(a);
	read(b);
	cout<<f(b,b)<<endl<<f(b,a);
	return 0;
} 
2024/8/29 21:54
加载中...