hash WA on #23 #53 #64 求助
查看原帖
hash WA on #23 #53 #64 求助
609818
Point_LUO楼主2024/6/1 23:42
#include<bits/stdc++.h>
using namespace std;
const int N=2000002;
int n,m,ans,h1,h2;
int h[N],pre[N];
char s[N];
string a,b,c,d;

int val(int l,int r){ return h[r]-h[l-1]*pre[r-l+1]; }//求哈希值 
int del(int l,int r,int p){ return val(l,p-1)*pre[r-p]+val(p+1,r); }//删后求值 

int main()
{
	cin>>n;
	if(n%2==0)
	{
		printf("NOT POSSIBLE");
		return 0;
	}//特判偶数 
	m=(n+1)>>1;
	scanf("%s",s+1);
	pre[0]=1;
	for(int i=1;i<=n;i++)
	{
		pre[i]=pre[i-1]*31;
		h[i]=h[i-1]*31+s[i]-'A';
	}
	h1=val(m+1,n);
	for(int i=m+1;i<=n;i++) a.push_back(s[i]);
	for(int i=1;i<=m;i++)
	{
		h2=del(1,m,i);
		if(h1==h2)
		{
			ans++;
			c=a;
			break;
		}
	}
	h1=val(1,m-1);
	for(int i=1;i<m;i++) b.push_back(s[i]);
	for(int i=m+1;i<=n;i++)
	{
		h2=del(m+1,n,i);
		if(h1==h2)
		{
			ans++;
			d=b;
			break;
		}
	}
	if(!ans) printf("NOT POSSIBLE");
	else if(ans==1||c==d) cout<<(c.size()?c:d);
	else printf("NOT UNIQUE");
	return 0;
}
2024/6/1 23:42
加载中...