写下一个字符串 A
#include<iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define int long long
const int N=2e6+5;
char s[N];
int flag=0;
string yy,ans1,ans2;
int n;
int h[N],pow[N];
int bas=131;
int f2(int l,int r){
return h[r]-h[l-1]*pow[r-l+1];
}
int f(int l,int r,int k){
return f2(l,k-1)*pow[r-k]+f2(k+1,r);
}
void solve(){
int i,j,t1,t2;
int md=(1+n)/2;
t2=f2(md+1,n);
for(i=md+1;i<=n;i++) yy.push_back(s[i]);
for(i=1;i<=md;i++){
t1=f(1,md,i);
if(t1==t2){
flag++; ans1=yy;break;
}
}
yy.clear();
t1=f2(1,md-1);
for(i=1;i<md;i++) yy.push_back(s[i]);
for(i=md;i<=n;i++){
t2=f(md,n,i);
if(t1==t2){
flag++; ans2=yy;break;
}
}
if(flag==0) cout<<"NOT POSSIBLE";
else if(flag==1||ans1==ans2) {if(ans1.size()) cout<<ans1; else cout<<ans2;}
else cout<<"NOT UNIQUE";
cout<<endl;
}
void init(){
h[0]=0; pow[0]=1;
for(int i=1;i<=n;i++){
pow[i]=pow[i-1]*bas;
h[i]=h[i-1]*bas+s[i]-'A'+1;
}
}
main(){
cin>>n>>s+1;
if(n%2==0) return cout<<"NOT POSSIBLE",0;
init();
solve();
}