提交时间:2025-09-25 13:24:39
运行 ID: 38260
#include<bits/stdc++.h> using namespace std; long long n; unsigned long long ha[2000006],bz[2000006],sum,tp1,tp2; inline unsigned long long zc(long long l,long long r){ if(l>r)return 0; return ha[r]-ha[l-1]*bz[r-l+1]; } string s; int main(){ //freopen("string.in","r",stdin); //freopen("string.out","w",stdout); scanf("%lld",&n); if(n%2==0){ printf("NOT POSSIBLE"); return 0; } cin>>s; s=" "+s; bz[0]=1; for(int i=1;i<=n;i++){ ha[i]=(ha[i-1]*131+s[i]); bz[i]=bz[i-1]*131; } long long mid=(n)/2; for(int i=1;i<=n;i++){ if(i<=mid){ unsigned long long bs=zc(i+1,mid+1); bs=ha[i-1]*bz[(mid-(i-1))]+bs; //cout<<bs<<" "<<zc(mid+2,n)<<"\n"; if(bs==zc(mid+2,n)){ sum++; tp2=1; } } if(i==mid+1){ if(zc(1,mid)==zc(mid+2,n)){ sum++; tp2=tp2=1; } } else{ unsigned long long bs=zc(i+1,n); bs=zc(mid+1,i-1)*bz[(mid-(i-1-(mid+1)))-1]+bs; if(i==n){ //printf("%lld ",(mid-(i-1-(mid+1)))-1); } //cout<<bs<<" "<<zc(mid+2,n)<<"\n"; if(bs==ha[mid]){ sum++; tp1=1; } } } if(sum>1){ printf("NOT UNIQUE"); return 0; } else if(tp1==1){ for(int j=1;j<=mid;j++){ printf("%c",s[j]); } return 0; } else if(tp2==1){ for(int j=mid+2;j<=n;j++){ printf("%c",s[j]); } return 0; } else{ printf("NOT POSSIBLE"); } } //1158368 1124178