BZOJ 3916 Baltic 2014 friends Hash

题目大意

给出一个字符串，这个字符串是由两个相同的字符串连接之后再加一个字母的到的，求原串。

思路

枚举加的字母是哪一个，之后分情况讨论，根据hash值来判定是否符合题目要求。注意判重。

CODE

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 2000010
#define BASE 23333
using namespace std;

int length, mid;
char s[MAX];

unsigned long long _hash[MAX];
unsigned long long power[MAX];

int cnt;
char ans[MAX], now[MAX];
unsigned long long h_ans, h_now;

inline unsigned long long GetHash(int l, int r)
{
    return _hash[r] - _hash[l - 1] * power[r - l + 1];
}

inline bool Judge(int dismiss)
{
    static unsigned long long front, tail;
    if(dismiss < mid) {
        front = GetHash(1, dismiss - 1) * power[mid - dismiss] + GetHash(dismiss + 1, mid);
        tail = GetHash(mid + 1, length);
    }
    else if(dismiss == mid) {
        front = GetHash(1, mid - 1);
        tail = GetHash(mid + 1, length);
    }
    else {
        front = GetHash(1, mid - 1);
        tail = GetHash(mid, dismiss - 1) * power[length - dismiss] + GetHash(dismiss + 1, length);
    }
    if(front == tail) {
        if(h_ans == front)  return false;
        h_ans = front;
        int top = 0;
        if(dismiss <= mid)
            for(int i = mid + 1; i <= length; ++i)
                ans[++top] = s[i];
        else
            for(int i = 1; i < mid; ++i)
                ans[i] = s[i];
        return true;
    }
    return false;
}

int main()
{
    cin >> length;
    if(!(length&1)) {
        puts("NOT POSSIBLE");
        return 0;
    }
    mid = (length >> 1) + 1;
    scanf("%s", s + 1);
    power[0] = 1;
    for(int i = 1; i <= length; ++i)
        power[i] = power[i - 1] * BASE;
    for(int i = 1; i <= length; ++i)
        _hash[i] = _hash[i - 1] * BASE + s[i];
    for(int i = 1; i <= length; ++i) {
        cnt += Judge(i);
        if(cnt > 1) break;
    }
    if(!cnt)
        puts("NOT POSSIBLE");
    if(cnt == 1)
        puts(ans + 1);
    if(cnt > 1)
        puts("NOT UNIQUE");
    return 0;
}