Three Friends

传送门：链接（UPC）或链接（大视野）

题目描述

Three friends like to play the following game. The first friend chooses a string S. Then the second friend constructs a new string T that consists of two copies of the string S. finally, the third friend inserts one letter at the beginning, the end or somewhere inside the string T, thereby creating a string U.

You are given the string U and your task is to reconstruct the original string S.

输入

The first line of the input contains N（2 ≤ N ≤ 2000001）, the length of the final string U. The string U itself is given on the second line. It consists of N uppercase English letters (A, B, C, . . . , Z).

输出

Your program should print the original string S. However, there are two exceptions:

1.If the final string U could not have been created using the above procedure, you should print NOT POSSIBLE.

2.If the original string S is not unique, you should print NOT UNIQUE.

样例输入

7

ABXCABC

样例输出

ABC

题目大意：

有三个字符串分别为S，T，U，其中T=S+S，U为在T中插入一个字符。

现在给出字符串U，判断是否存在原始字符串S，或者是存在不止一个。

aaa 应该输出 a ，而不应该判断为不存在。

解题思路：

hash应该能想到，但我T了n遍。

1、数据量很大，最好用scanf或者加ios::sync_with_stdio(false);。

2、暴力每个点，判断这个点的字符去掉后左右两边的hash值是否相等。

3、解决aaa的问题，我开始是用map标记，但因为map要用string做key键，导致用了很多string函数导致超时，解决这个问题其实可以保存第一个符合条件的hash值，以后直接判断。

4、在遍历过程中，一旦有两个hash值不相同的点且都满足条件，立刻输出并return 0也是优化的关键。

AC代码：

我用的hash方法是进制哈希（我没取模肯定会导致爆long long，建议你们取模）：详解进制哈希

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL MAX=2e6;

LL k=27;

LL ha[MAX+5];

LL qpow(LL m,LL q)

{

    LL ans=1;

    while(q){

        if(q%2) ans*=m;

        m*=m;

        q/=2;

    }

    return ans;

}

void hasha(string a)

{

    LL la=a.size();

    la-=1;

    for(LL i=la;i>=1;i--){

        ha[i]=ha[i+1]*k+a[i];

    }

}

int main()

{

    ios::sync_with_stdio(false);

    LL la;

    string a;

    cin>>la>>a;

    a=' '+a;

    if(la%2==0){

        cout<<"NOT POSSIBLE"<<endl;

        return 0;

    }

    hasha(a);

    LL flag=-1;

    long long flag1;

    for(LL i=1;i<=la;i++){

        if(i==(la/2+1)){

            if((ha[1]-ha[i]*qpow(k,i-1)==(ha[i+1]))){

                if(flag==-1){

                    flag1=ha[i+1];

                    flag=i;

                }else{

                    if(ha[i+1]!=flag1){

                        cout<<"NOT UNIQUE"<<endl;

                        return 0;

                    }

                }

            }

        }else if(i<(la/2+1)){

            LL x=i-1;

            LL y=la/2-i+1;

            LL num1=la/2+2;

            if(((ha[i+1]-ha[num1]*qpow(k,y))*qpow(k,x)+(ha[1]-ha[i]*qpow(k,x)))==ha[num1]){

                if(flag==-1){

                    flag1=ha[num1];

                    flag=i;

                }else{

                    if(ha[num1]!=flag1){

                        cout<<"NOT UNIQUE"<<endl;

                        return 0;

                    }

                }

            }

        }else if(i>(la/2+1)){

            LL x=i-la/2-1;

            LL num1=la/2+1;

            if(ha[i+1]*qpow(k,x)+(ha[num1]-ha[i]*qpow(k,x))==(ha[1]-ha[num1]*qpow(k,la/2))){

                if(flag==-1){

                    flag1=ha[1]-ha[num1]*qpow(k,la/2);

                    flag=i;

                }else{

                    if((ha[1]-ha[num1]*qpow(k,la/2))!=flag1){

                        cout<<"NOT UNIQUE"<<endl;

                        return 0;

                    }

                }

            }

        }

    }

    if(flag==-1) cout<<"NOT POSSIBLE"<<endl;

    else{

        LL dir=flag,j=1;

        for(LL i=1;;i++){

            if(i==dir) continue;

            else{

                cout<<a[i];

                j++;

            }

            if(j==la/2+1) break;

        }

        cout<<endl;

    }

    return 0;

}

巴特西

【哈希和哈希表】Three Friends【进制哈希】

Three Friends

传送门：链接（UPC）或链接（大视野）

最新文章

热门文章

巴特西

【 哈希和哈希表】Three Friends【进制哈希】

Three Friends

传送门：链接 （UPC）或 链接（大视野）

最新文章

热门文章

【哈希和哈希表】Three Friends【进制哈希】

传送门：链接（UPC）或链接（大视野）