exKMP TLE pts29
查看原帖
exKMP TLE pts29
945364
LiJoQiao楼主2023/12/22 09:43
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace sol{
	const int MAXLEN=2e7+10;
	char a[MAXLEN],b[MAXLEN];
	int z[MAXLEN],p[MAXLEN];
	void solve(){
		scanf("%s%s",a+1,b+1);
		int lena=strlen(a+1),lenb=strlen(b+1);
		//z函数部分 
		z[1]=lenb;
		int p0=1;
		ll valz=z[1]+1;
		for(int i=2;i<=lenb;++i){
			z[i]=max(min(z[p0]+p0-i-1,z[i-p0+1]),0);
			while(b[i+z[i]]==b[z[i]+1])++z[i];
			if(p0+z[p0]<i+z[i])p0=i;
			valz^=1ll*(z[i]+1)*i;
		}
		printf("%lld\n",valz);
		//p数组部分 
		p0=1;
		ll valp=0;
		for(int i=1;i<=lena;++i){
			p[i]=max(min(z[i-p0+1],p[p0]-(i-p0)),0);
			while(a[i+p[i]]==b[p[i]+1])++p[i];
			if(i+p[i]>p0+p[p0])p0=i;
//			cerr<<"p["<<i<<"]="<<p[i]<<' ';
			valp^=1ll*(p[i]+1)*i;
		}
		printf("%lld\n",valp);
	}
}
int main(){
	sol::solve();
	return 0;
}
2023/12/22 09:43
加载中...