Hash求助,wa#50#53#59#61#64
查看原帖
Hash求助,wa#50#53#59#61#64
437795
wanggiaoxing楼主2021/8/16 08:23
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
inline int read()
{
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();
	return s*w;
}
string ans;
char s[2000005];
int n=read(),Hash[2000005],mi[2000005],ans1;
int gethash(int l,int r)
{
	if(l>r)return 0;
	return ((Hash[r]-Hash[l-1]*mi[r-l+1])%mod+mod)%mod;
}
int check(int l,int r,int l1,int r1)
{
	return ((gethash(l,r)*mi[r1-l1+1])%mod+gethash(l1,r1))%mod;
}
signed main()
{
	if(n%2==0)
		printf("NOT POSSIBLE"),exit(0);
	mi[0]=1;
	for(int i=1;i<=n;i++)mi[i]=(mi[i-1]*29)%mod;
	cin>>s+1;
	for(int i=1;i<=n;i++)
		Hash[i]=(Hash[i-1]*29+s[i])%mod;
	for(int i=1;i<n/2+1;i++)
		if(check(1,i-1,i+1,n/2+1)==gethash(n/2+2,n))
		{
			ans="";
			ans1++;
			if(ans1>=2)
				printf("NOT UNIQUE"),exit(0);
			for(int j=1;j<i;j++)ans+=s[j];
			for(int j=i+1;j<=n/2+1;j++)ans+=s[j];
		}
	for(int i=n/2+1;i<=n;i++)
		if(gethash(1,n/2)==check(n/2+1,i-1,i+1,n))
		{
			ans="";
			ans1++;
			if(ans1>=2)
				printf("NOT UNIQUE"),exit(0);
			for(int j=n/2+1;j<i;j++)ans+=s[j];
			for(int j=i+1;j<=n;j++)ans+=s[j];
		}
	if(ans1)cout<<ans;
	else printf("NOT POSSIBLE");
	return 0;
}
2021/8/16 08:23
加载中...