ybt 1459：friends

写下一个字符串 A，将其复制一遍得到B ，在任意位置（包括首尾）插入一个字符得到 C。现在你得到C。求出 A

题意中的  [复制]： 这个多余的字符在 [1,md] 或 [md,n]

枚举这个字符的位置，剩余的东西是2个A, 当前区间有插入的，那么另一个区间是完整的

先算一下字符串的hash

int f(int l,int r,int k)  找出 [L,R] 去掉位置k 的串的hash

#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();
 }