#include <bits/stdc++.h>
using namespace std;
int const MOD=1e9+7;
int const BASE=31;
int const MAX=2000005;
int n;
char sir[MAX];
int hashes[MAX];
int bpow[MAX];
int ans_hash,ans_id;
void read(){
cin>>n;
int i;
for(i=1;i<=n;++i)
cin>>sir[i];
}
void precalc(){
int i;
bpow[0]=1;
for(i=1;i<MAX;++i)
bpow[i]=1LL*BASE*bpow[i-1]%MOD;
for(i=1;i<=n;++i)
hashes[i]=(1LL*BASE*hashes[i-1]%MOD+sir[i]-'A'+1)%MOD;
}
int hash_intv(int l,int r){
return (hashes[r]-1LL*hashes[l-1]*bpow[r-l+1]%MOD+MOD)%MOD;
}
int hash_2intv(int l1,int r1,int l2,int r2){
return (1LL*hash_intv(l1,r1)*bpow[r2-l2+1]%MOD+hash_intv(l2,r2))%MOD;
}
void solve(){
if(n%2==0)
return;
int i;
for(i=1;i<=n;++i){
int hsh1,hsh2;
if(i<=n/2+1){
hsh1=hash_2intv(1,i-1,i+1,n/2+1);
hsh2=hash_intv(n/2+2,n);
}
else{
hsh1=hash_intv(1,n/2);
hsh2=hash_2intv(n/2+1,i-1,i+1,n);
}
if(hsh1==hsh2){
if(!ans_hash){
ans_hash=hsh1;
ans_id=i;
}
else
if(ans_hash!=hsh1)
ans_id=0;
}
}
}
void answer(){
if(ans_id){
int i;
for(i=1;i<=n/2+(ans_id<=n/2);++i)
if(i!=ans_id)
cout<<sir[i];
}
else{
if(ans_hash)
cout<<"NOT UNIQUE";
else
cout<<"NOT POSSIBLE";
}
}
int main()
{
read();
precalc();
solve();
answer();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |