51nod 2619 三个好朋友 字符按Hash

2619 三个好朋友

1. 1.0 秒
2.  
3. 131,072.0 KB
4.  
5. 20 分
6.  
7. ​​3级题​​

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

比如得到U串为ABABA。

那么S串有可能是AB，T串为ABAB，之后在最后一个位置插入A，得到ABABA。

S串还有可能是BA，T串为BABA，之后在第一个位置插入A，得到ABABA。

 收起

输入

第1行：一个数n,表示U的长度。(1<=n<=200000) 第2行：一个字符串U,保证U由大写字母组成。

输出

输出一行,若S不存在,输出"NOT POSSIBLE".若S不唯一,输出"NOT UNIQUE".否则输出S。

输入样例

7 ABXCABC

输出样例

ABC

 

不错的Hash题目被我成功的AC，这题对理解字符串Hash有帮助。

对ABXCABC，我们可以暴力枚举每一个位置，关键如何拼接ABXC，我们可以求出AB和C的Hash值，如何拼接成ABC，

AB的Hash：1*P^1+2*P^0,C为3*P^0,AB要拼接在C的前面，需要向高位移一位，给C留出位置来，即

                                                 前半部分的Hash值*P^(后半部分字符数量）+后半部分的Hash值

 

 

#include<bits/stdc++.h>
const int N = 500000+5;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int P=131;
ULL hashv[N],power[N];
char str[N];
int n;
void calHash()
{
    power[0]=1;
    for(int i=1; i<=n; i++)
    {
        hashv[i]=hashv[i-1]*P+(str[i]-'A'+1);
        power[i]=power[i-1]*P;
    }
}
ULL getHash(int l,int r)
{
    if(r>=l)
        return hashv[r]-hashv[l-1]*power[r-l+1];
    else
        return 0;
}
set<ULL> s;
int main()
{


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

    calHash();

    if(n%2==0)
    {
        printf(("NOT POSSIBLE\n"));
        return 0;
    }
    int len=(n-1)/2;
    int pos;

    for(int i=1; i<=len+1; i++)
    {
        //cout<<getHash(len+2,n)<<" "<<getHash(1,i-1)*power[len-(i-1)]<<" "<<getHash(i+1,1+len)<<endl;
        if(getHash(len+2,n)==getHash(1,i-1)*power[len-(i-1)]+getHash(i+1,len+1))
        {
            pos=i;
            s.insert(getHash(len+2,n));
        }
        if(s.size()>=2)
            break;
    }

    if(s.size()>=2)
    {
        printf("NOT UNIQUE\n");
        return 0;
    }


      for(int i=len+2; i<=n; i++)
    {
        //cout<<getHash(len+2,n)<<" "<<getHash(1,i-1)*power[len-(i-1)]<<" "<<getHash(i+1,1+len)<<endl;
        if(getHash(1,len)==getHash(len+1,i-1)*power[len-(i-(len+1))]+getHash(i+1,n))
        {
            pos=i;
            s.insert(getHash(1,len));
        }
        if(s.size()>=2)
            break;
    }


    if(s.size()==1)
    {
        int t=0;
        for(int i=1;i<=len+1;i++)
        {
            if(pos!=i)
            {
                t++;
                printf("%c",str[i]);
                if(t==len)
                    break;
            }
        }
        return 0;
    }
    else if(s.size()==0)
    {
        printf(("NOT POSSIBLE\n"));
        return 0;
    }
    else
    {
        printf("NOT UNIQUE\n");
        return 0;
    }




    return 0;
}