问题 E: 【 哈希和哈希表】Three Friends

时间限制: 1 Sec 内存限制: 128 MB

题面 提交 状态

题目描述

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

#pragma GCC optimize(2)
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e6+10;
const int p = 131;
ull num[maxn],Hash[maxn];
ull pos=-1,S,L,R;
char str[maxn],ans[maxn];
int n,mid;
ull get_hash(int l,int r){
    return (ull)Hash[r] - (ull)Hash[l-1] * num[r-l+1];
}
int main()
{
    scanf("%d",&n);
    scanf("%s",str+1);
    num[0]=1;
    for(int i=1;i<=n;i++){
        num[i]=num[i-1]*p;
        Hash[i]=Hash[i-1]*p+str[i]-'A'+1;
    }
    mid = n>>1;
    if(n %2 ==0){
        printf("NOT POSSIBLE\n");
        return 0;
    }
    for(int i=1;i<=mid;i++){
        L=get_hash(1,i-1)*num[mid-i+1]+get_hash(i+1,mid+1);
        R=get_hash(mid+2,n);
        if(L==R){
            if(pos==-1||S==R){
                pos = i;
                S = R;
            }
            else{
                printf("NOT UNIQUE\n");
                return 0;
            }
        }
    }
    L=Hash[mid];
    R=Hash[n]-Hash[mid+1]*num[mid];
    if(L==R){
        if(pos==-1||S==L){
            pos=mid+1;
            S=L;
        } else{
            printf("NOT UNIQUE\n");
            return 0;
        }
    }
    for( int i=mid+2;i<=n;i++){
        L=Hash[mid];
        R=get_hash(mid+1,i-1)*num[n-i]+get_hash(i+1,n);
        if(L==R){
            if(pos==-1||S==R){
                pos = i;
                S = R;
            }
            else{
                printf("NOT UNIQUE\n");
                return 0;
            }
        }
    }
    if(pos==-1){
        printf("NOT POSSIBLE\n");
        return 0;
    }
    int len = n>>1,cnt=0;
    for(int i=1;i<=n&&len;i++){
        if(i==pos)
            continue;
        ans[cnt++]=str[i];
        len--;
    }
    ans[cnt]='\0';
    printf("%s\n",ans);
    return 0;
}