结果

Code:

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N=2000005,mod=999991,base=128;
string u;
int n,mid,ans,poss,lt,rt,hashh[N],power[N];
int get_hash(int l,int r){
	return hashh[r]-hashh[l-1]*power[r-l+1];
}
int re_hash(int l,int r,int pos){
	return get_hash(l,pos-1)+get_hash(pos+1,r);
}
map<string,int> mp;
bool Hash(int pos){
	if(pos>mid){
		lt=get_hash(1,mid-1);
		rt=re_hash(mid,n,pos);
		return lt==rt;
	}
	if(pos==mid){
		lt=get_hash(1,mid-1);
		rt=get_hash(mid+1,n);
		return lt==rt;
	}
	if(pos<mid){
		lt=re_hash(1,mid,pos);
		rt=get_hash(mid+1,n);
		return lt==rt;
	}
}
signed main(){
	cin>>n>>u;
	u='0'+u;
	mid=(n+1)/2;
	if(n%2==0){
		printf("NOT POSSIBLE");
		return 0;
	}
	power[0]=1;
	for(int i=1;i<=n;i++){
		power[i]=power[i-1]*base;
		hashh[i]=hashh[i-1]*base+u[i];
	}
	for(int i=1;i<=n;i++)
		if(Hash(i)){
			poss=i;
			string s;
			if(i>mid) s=u.substr(1,mid);
			else s=u.substr(mid+1);
			if(mp[s]!=1) ans++;
			mp[s]=1;
		}
	if(ans==1){
		if(poss>mid) cout<<u.substr(1,mid-1);
		else cout<<u.substr(mid+1);
		return 0;
	}
	if(ans==0) cout<<"NOT POSSIBLE";
	else printf("NOT UNIQUE");
	return 0;
}