WA on 1
查看原帖
WA on 1
282624
Alexia_Cosecant楼主2021/10/4 11:20
#include<bits/stdc++.h>
using namespace std;
const int N=20000005;
char s[N],t[N]; 
int z[N],p[N],ls,lt;
void getz()
{
	z[0]=lt;
	for(int i=1,l=0,r=0;i<lt;++i)
	{
		if(i<=r&&z[i-l]<r-i+1) z[i]=z[i-l];
		else
		{
			z[i]=max(0,r-i+1);
			while(i+z[i]<lt&&t[i+z[i]]==t[z[i]]) ++z[i];
		}
        if(i+z[i]-1>r) l=i,r=i+z[i]-1; 
	}
}
void exkmp()
{
	getz();
	for(int i=0,l=0,r=0;i<ls;++i)
	{
		if(i<=r&&z[i-l]<r-i+1) p[i]=z[i-l];
		else
		{
			p[i]=max(0,r-i+1);
			while(i+p[i]<ls&&s[i+p[i]]==t[p[i]]) ++p[i];
		} 
        if(i+p[i]-1>r) l=i,r=i+p[i]-1;
	}
}
int main()
{
	scanf("%s%s",s,t);
	ls=strlen(s);
	lt=strlen(t);
	exkmp();
	long long ansa=0,ansb=0;
	for(int i=0;i<lt;i++) ansa^=1ll*(z[i]+1)*(i+1);
	for(int i=0;i<ls;i++) ansb^=1ll*(p[i]+1)*(i+1);
	printf("%lld\n%lld",ansa,ansb);
	return 0;
}

第二行的答案跟标准答案差了2?求调(自认为还是比较简洁的)

2021/10/4 11:20
加载中...