入门hash求救! WA #50 #53 #59 #61 #64
查看原帖
入门hash求救! WA #50 #53 #59 #61 #64
179253
无尽星空楼主2020/12/12 21:08
#include<bits/stdc++.h>
#define R register int 
using namespace std;
const int N=2e6+5,P=135625069,B=29;
char s[N];
int n,ha[N],bit[N]={1,B},nd,lct;
inline int hash(int l,int r,int x)
{
	if(x>r)  return (ha[r]-ha[l-1]+P)%P;
	if(x<l)  return (ha[r+1]-ha[l]+P)%P;
	return (1ll*(ha[x-1]-ha[l-1]+P)%P*B%P+ha[r+1]-ha[x]+P)%P;
}
int main()
{
	scanf("%d %s",&n,s+1);nd=n>>1;
	if(!(n&1)) {printf("NOT POSSIBLE");return 0;}
	for(R i=2;i<=n;i++)  bit[i]=1ll*bit[i-1]*B%P;
	for(R i=1;i<=n;i++)  ha[i]=(ha[i-1]+1ll*(s[i]-'A'+1)*bit[i-1]%P)%P;
	for(R i=1,ed1,ed2;i<=n;i++)
	{
		ed2=n-(i==n);ed1=nd+(i<=nd);
		if((1ll*hash(1,nd,i)*bit[ed2-ed1]%P)==hash(nd+1,n-1,i))
		{
			if(lct)  {printf("NOT UNIQUE");return 0;}
			lct=i;
		}
	}
	if(!lct)  {printf("NOT POSSIBLE");return 0;}
	for(R i=1;i<=nd+(lct<=nd);i++)
		if(i!=lct)  putchar(s[i]);
	return 0;
}
2020/12/12 21:08
加载中...