BZOJ_3916_[Baltic2014]friends_hash

BZOJ_3916_[Baltic2014]friends_hash

题意：

有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S.

分析：

字符串哈希

首先n%2==0一定没有答案

枚举插入的字符，拿出来，判断一下前后两半串的哈希值是否相等

具体做法：一个串被一个字符隔开了，它的哈希值等于前面串的哈希值*base^(len[后面串])+后面。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 2000050

#define LL unsigned long long

char s[N];

LL p=13131,mi[N],h[N],ans;

int n,pos;

int main()

{

    ans=-1;

    scanf("%d%s",&n,s+1);

    int l=(n-1)/2;

    if(n%2==0)

    {

        puts("NOT POSSIBLE");return 0;

    }

    int i;

    mi[0]=1;

    for(i=1;i<=n;i++)

    {

        h[i]=h[i-1]*p+s[i];

        mi[i]=mi[i-1]*p;

    }

    for(i=1;i<=n+1;i++)

    {

        if(i-1<l)

        {

            LL h1=h[i-1]*mi[l-i+1]+(h[l+1]-h[i]*mi[l-i+1]);

            LL h2=h[n]-h[l+1]*mi[l];

            if(h1==h2)

            {

                pos=i;

                if(ans==-1)ans=h1;

                else if(ans!=h1)

                {

                    puts("NOT UNIQUE");return 0;

                }

            }

        }

        else

        {

            LL h1=h[l];

            LL h2=(h[i-1]-h[l]*mi[i-l-1])*mi[n-i]+h[n]-h[i]*mi[n-i];

            if(h1==h2)

            {

                pos=i;

                if(ans==-1)ans=h1;

                else if(ans!=h1)

                {

                    puts("NOT UNIQUE");return 0;

                }

            }

        }

    }

    if(ans==-1)

    {

        puts("NOT POSSIBLE");return 0;

    }

    if(pos-1<l)

    {

        for(i=l+2;i<=n;i++)printf("%c",s[i]);

    }

    else

    {

        for(i=1;i<=l;i++)printf("%c",s[i]);

    }

}