hash求助!WA#50#53#59#61#64
查看原帖
hash求助!WA#50#53#59#61#64
178992
Hanghang楼主2021/2/20 23:34

若谁能帮我解决,我将大小号一起关注他

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
char t[2000003];
int n,base=131;
ull s[2000003],Q[2000003],S,X,Y;
int main()
{
	Q[0]=1;
	for(int i=1;i<=2000001;i++)Q[i]=Q[i-1]*base; 
	cin>>n;
	for(int i=1;i<=n;i++)cin>>t[i];
	for(int i=1;i<=n;i++)s[i]=s[i-1]*base+ull(t[i]-'a');
	if(n%2==0)
	{
		cout<<"NOT POSSIBLE";return 0;
	}
	if(s[n/2+1]-s[1]*Q[n/2]==s[n]-s[n/2+1]*Q[n-n/2-1])S++,X=2,Y=n/2+1;
	if(s[n/2]==s[n]-s[n/2+1]*Q[n-n/2-1])S++,X=1,Y=n/2;
	if(s[n/2]==s[n-1]-s[n/2]*Q[n-n/2-1])S++,X=1,Y=n/2;
	for(int i=2;i<=n/2;i++)
	{
		ull x=s[i-1]*Q[n/2+1-i]+s[n/2+1]-s[i]*Q[n/2+1-i];
		ull y=s[n]-s[n/2+1]*Q[n-n/2-1];
		if(x==y)S++,X=n/2+2,Y=n;
	}
	for(int i=n/2+2;i<n;i++)
	{
		ull x=s[n/2];
		ull y=(s[i-1]-s[n/2]*Q[i-n/2-1])*Q[n-i]+s[n]-s[i]*Q[n-i];
		if(x==y)S++,X=1,Y=n/2;
	}
	if(S==0)
	{
		cout<<"NOT POSSIBLE";return 0;
	}
	if(S>1)cout<<"NOT UNIQUE";
	else for(int i=X;i<=Y;i++)cout<<t[i];
	return 0;
}
2021/2/20 23:34
加载中...