Z函数求卡常29pts
查看原帖
Z函数求卡常29pts
490694
Compound_Interest楼主2024/8/1 16:47
#include<bits/stdc++.h>
using namespace std;
string A,B; 
const int maxn=4e7+10;
int Z[maxn];
void sol(string S){
	string str="#"+S;
	int n=(int)str.length()-1;
	int mid=0;
	for(int i=1;i<=n;i++){
		if(mid+Z[mid]-1>=i){
			int ii=i-mid+1;
			Z[i]=min(Z[ii],mid+Z[mid]-i);
			while(Z[i]+i<=n&&str[i+Z[i]]==str[Z[i]+1]) Z[i]++;
			if(i+Z[i]>mid+Z[mid]) mid=i;
		}
		else{
			while(Z[i]+i<=n&&str[i+Z[i]]==str[Z[i]+1]) Z[i]++;
			if(i+Z[i]>mid+Z[mid]) mid=i;			
		}
	}
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	cin>>A>>B;
	sol(B+A);
	long long val1=0,val2=0;
	for(int i=1;i<=(int)(A.length()+B.length());i++){
		if(i>=(int)B.length()+1){
			Z[i]=min(Z[i],(int)B.length());
			val2^=1ll*(i-(int)B.length())*(Z[i]+1);	
		}
		else{
			Z[i]=min(Z[i],(int)B.length()-i+1);
			val1^=1ll*i*(Z[i]+1);
		}
	}
	cout<<val1<<'\n'<<val2;
	return 0;
}
2024/8/1 16:47
加载中...