Description

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

Input

第一行一个数N,表示U的长度.

第二行一个字符串U,保证U由大写字母组成

Output

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

Sample Input1

7
ABXCABC

Sample Output1

ABC

Sample Input2

6
ABCDEF

Sample Output2

NOT POSSIBLE

Sample Input3

9
ABABABABA

Sample Output3

NOT UNIQUE

Hint

对于100%的数据 2<=N<=2000001

题解

这题很显然是一道字符串\(Hash\)，但是有一些坑点

由于我将若S不唯一看成了若插入的位置不唯一，创造了我的首\(WA\)

接着，我却将每次可以的\(S\)记录下来，导致时间代价太大，造成了我的首\(TLE\)，\(TLE\)代码如下：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;

typedef unsigned long long ull;
const int L=2000005,E=100007;
char s[L],Out[L];
int l,Ans;
ull power[L],h[L];

void PutIn(int id)//超时的关键
{
    if(id<=l/2)
    {
        for(int i=1;i<=l/2;++i) Out[i]=s[i+l/2+1];
        return;
    }
    for(int i=1;i<=l/2;++i) Out[i]=s[i];
}

int Check(int id)//超时的关键
{
    if(id<=l/2)
    {
        for(int i=1;i<=l/2;++i)
            if(Out[i]!=s[i+l/2+1]) return 1;
        return 0;
    }
    for(int i=1;i<=l/2;++i)
        if(Out[i]!=s[i]) return 1;
    return 0;
}

int main()
{
    scanf("%d\n%s",&l,s+1);
    if(l%2==0) {puts("NOT POSSIBLE");goto end;}
    power[0]=1;
    for(int i=1;i<=l;++i) power[i]=power[i-1]*E;
    for(int i=1;i<=l;++i) h[i]=h[i-1]*E+s[i];
    for(int i=1;i<=l;++i)
    {
        if(i<=l/2)
        {
            if((h[l/2+1]-h[i]*power[l/2+1-i]+h[i-1]*power[l/2+1-i])
            ==(h[l]-h[l/2+1]*power[l/2]))
                if(!Ans) {Ans=i;PutIn(i);}
                else if(Check(i))
                        {puts("NOT UNIQUE");goto end;}
        }
        else
        {
            if(h[l/2]
            ==(h[l]-h[i]*power[l-i]+h[i-1]*power[l-i]-h[l/2]*power[l-l/2-1]))
                if(!Ans) {Ans=i;PutIn(i);}
                else if(Check(i))
                        {puts("NOT UNIQUE");goto end;}
        }
    }
    if(!Ans) puts("NOT POSSIBLE");
    else
    {
        for(int i=1;i<=l/2;++i) printf("%c",Out[i]);
        putchar('\n');
    }
    end:
    return 0;
}

---

注意到上面代码中造成\(TLE\)的罪魁祸首，如果我们能够\(O(1)\)来比较的话那么问题不就迎刃而解了吗

字符串\(Hash\)的作用是什么？

将字符转化成数，从而方便的计算与比较大小，（大雾

\(My~Code\)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;

typedef unsigned long long ull;
const int L=2000005,E=100007;
char s[L];
int l,Ans;
ull power[L],h[L],hAns;

int main()
{
    scanf("%d\n%s",&l,s+1);
    if(l%2==0) {puts("NOT POSSIBLE");goto end;}
    power[0]=1;
    for(int i=1;i<=l;++i) power[i]=power[i-1]*E;
    for(int i=1;i<=l;++i) h[i]=h[i-1]*E+s[i];
    for(int i=1;i<=l;++i)
    {
        if(i<=l/2)
        {
            if((h[l/2+1]-h[i]*power[l/2+1-i]+h[i-1]*power[l/2+1-i])
            ==(h[l]-h[l/2+1]*power[l/2]))//此处的过程需要用草稿纸或大脑子
                if(!Ans) Ans=i,hAns=h[l]-h[l/2+1]*power[l/2];
                else if(h[l]-h[l/2+1]*power[l/2]!=hAns)
                    {puts("NOT UNIQUE");goto end;}
        }
        else
        {
            if(h[l/2]
            ==(h[l]-h[i]*power[l-i]+h[i-1]*power[l-i]-h[l/2]*power[l-l/2-1]))
                if(!Ans) Ans=i,hAns=h[l/2];
                else if(h[l/2]!=hAns)
                    {puts("NOT UNIQUE");goto end;}
        }
    }
    if(!Ans) puts("NOT POSSIBLE");
    else
    {
        if(Ans<=l/2)
        {
            for(int i=l/2+2;i<=l;++i) printf("%c",s[i]);
            putchar('\n');
        }
        else
        {
            for(int i=1;i<=l/2;++i) printf("%c",s[i]);
            putchar('\n');
        }
    }
    end:
    return 0;
}