题目链接：###
题目：###
Description####
有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S.
Input####
第一行一个数N,表示U的长度.
第二行一个字符串U,保证U由大写字母组成
Output####
输出一行,若S不存在,输出"NOT POSSIBLE".若S不唯一,输出"NOT UNIQUE".否则输出S.
题目分析：###
枚举断点+字符串前缀和哈希
如果一个字符串中去掉一个字母（或一段），它的哈希值等于前面串的哈希值*base^(len[后面串])+后面。
代码：###
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int cnt=0,f=1;char c;
c=getchar();
while(!isdigit(c)){
if(c=='-')f=-f;
c=getchar();
}
while(isdigit(c)){
cnt=cnt*10+c-'0';
c=getchar();
}
return cnt*f;
}
int n;
const int P=131;
char s[2000005];
unsigned long long Hash[2000005];
unsigned long long bin[2000005];
int flag=0;
unsigned long long hash_left;unsigned long long hash_right;
int pos=-1;
unsigned long long ans=0;
int main(){
n=read();scanf("%s",s+1);
if(n%2==0){
printf("NOT POSSIBLE");
return 0;
}
bin[0]=1;
for(register int i=1;i<=n;i++){
Hash[i]=Hash[i-1]*P+s[i];
bin[i]=bin[i-1]*P;
}
// for(register int i=1;i<=n;i++)printf("%d ",hash[i]);
int mid=(n+1)/2;
for(register int i=1;i<=n;i++){
hash_left=0;hash_right=0;
if(i<mid){
hash_left=Hash[i-1]*bin[mid-i]+Hash[mid]-Hash[i]*bin[mid-i];
hash_right=Hash[n]-Hash[mid]*bin[n-mid];
}
if(i==mid){
hash_left=Hash[i-1];
hash_right=Hash[n]-Hash[mid]*bin[n-mid];
}
if(i>mid){
hash_left=Hash[mid-1];
hash_right=(Hash[i-1]-Hash[mid-1]*bin[i-mid])*bin[n-i]+Hash[n]-Hash[i]*bin[n-i];
}
// cout<<hash_left<<" "<<hash_right<<endl;
if(hash_left==hash_right){
if(flag==0)flag++,pos=i,ans=hash_left;
else
if(ans!=hash_left){
flag++;
break;
}
}
}
if(flag>1)printf("NOT UNIQUE");
if(flag==0)printf("NOT POSSIBLE");
if(flag==1){
if(pos<mid)
for(register int i=mid+1;i<=n;i++)printf("%c",s[i]);
if(pos>mid)
for(register int i=1;i<mid;i++)printf("%c",s[i]);
if(pos==mid)
for(register int i=1;i<mid;i++)printf("%c",s[i]);
}
return 0;
}