BZOJ-3916: [Baltic2014]friends

Description

有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S.若S不存在,输出"NOT POSSIBLE".若S不唯一,输出"NOT UNIQUE".否则输出S. 2<=N<=2000001

枚举插入位置暴力hash即可。
注意不同的s才算不同的情况，不同的位置不算。
好像搞一个hash前缀和能过简单很多啊。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ull;
int len,fna,ans;
char s[2001000];
ull hs1[2001000],hs2[2001000],ha1[2001000],ha2[2001000];
ull has1,has2;
int main()
{
    scanf("%d%s",&len,s+1);
    if(~len&1) {puts("NOT POSSIBLE"); return 0;}
    int mid=len/2+1; ull po1,po2; int i;
    for(po1=po2=1,i=mid;i>=1;--i,po1*=233,po2*=2333)
    {
        hs1[i]=hs1[i+1]+s[i]*po1;
        hs2[i]=hs2[i+1]+s[i]*po2;
    }
    for(po1=po2=1,i=len;i>mid;--i,po1*=233,po2*=2333)
    {
        hs1[i]=hs1[i+1]+s[i]*po1;
        hs2[i]=hs2[i+1]+s[i]*po2;
    }
    for(i=1;i<mid;++i)
    {
        ha1[i]=ha1[i-1]*233+s[i];
        ha2[i]=ha2[i-1]*2333+s[i];
    }
    for(ha1[mid]=ha2[mid]=s[mid],i=mid+1;i<=len;++i)
    {
        ha1[i]=ha1[i-1]*233+s[i];
        ha2[i]=ha2[i-1]*2333+s[i];
    }
    ull tar1=hs1[mid+1],tar2=hs2[mid+1];
    for(po1=233,po2=2333,i=mid-1;i>=1;--i,po1*=233,po2*=2333)
        if(hs1[i+1]+ha1[i-1]*po1==tar1&&hs2[i+1]+ha2[i-1]*po2==tar2)
        {
            if(!ans) has1=tar1,has2=tar2,ans++,fna=i;
            break;
        }
    if(ha1[mid-1]==hs1[mid+1]&&ha2[mid-1]==hs2[mid+1])
        if(!ans) has1=tar1,has2=tar2,ans++,fna=mid;
    tar1=ha1[mid-1]; tar2=ha2[mid-1];
    for(po1=po2=1,i=len;i>mid;--i,po1*=233,po2*=2333)
        if(hs1[i+1]+ha1[i-1]*po1==tar1&&hs2[i+1]+ha2[i-1]*po2==tar2)
        {
            if(!ans) has1=tar1,has2=tar2,ans++,fna=i;
            else if(tar1!=has1||tar2!=has2) ans++;
            break;
        }
    if(ans==0) puts("NOT POSSIBLE");
    else if(ans==1)
    {
        if(fna>=mid) s[mid]='\0',printf("%s\n",s+1);
        else printf("%s\n",s+mid+1);
    }
    else puts("NOT UNIQUE");
    return 0;
}