[BalticOI2014]Friends/[BZOJ4287]新三个和尚

题目大意：

一个字符串\(A\)，将\(A\)复制一遍并在任意位置插入一个新字符得到\(B\)。给出\(B(|B|\le2\times10^6,|\Sigma|\le26)\)，求\(A\)是否存在、是否唯一。若唯一，则求出\(A\)。

思路：

字符串哈希。

源代码：

#include<cstdio>

#include<cctype>

inline int getint() {

    register char ch;

    while(!isdigit(ch=getchar()));

    register int x=ch^'0';

    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

    return x;

}

inline char getalpha() {

    register char ch;

    while(!isalpha(ch=getchar()));

    return ch;

}

typedef unsigned long long uint64;

const int N=2e6+1;

const uint64 base=31;

int s[N];

uint64 pwr[N],hash[N];

inline uint64 calc(const int &i,const int &j) {

    return hash[j]-hash[i-1]*pwr[j-i+1];

}

int main() {

    const int n=getint();

    if(n%2==0) {

        puts("NOT POSSIBLE");

        return 0;

    }

    for(register int i=pwr[0]=1;i<=n;i++) {

        s[i]=getalpha();

        pwr[i]=pwr[i-1]*base;

        hash[i]=hash[i-1]*base+s[i]-'A'+1;

    }

    uint64 last=0;

    int pos;

    for(register int i=1;i<=n/2;i++) {

        if(calc(1,i-1)*pwr[n/2-i+1]+calc(i+1,n/2+1)==calc(n/2+2,n)) {

            if(last!=0&&calc(n/2+2,n)!=last) {

                puts("NOT UNIQUE");

                return 0;

            }

            last=calc(n/2+2,n);

            pos=i;

        }

    }

    if(calc(1,n/2)==calc(n/2+2,n)) {

        if(last!=0&&calc(1,n/2)!=last) {

            puts("NOT UNIQUE");

            return 0;

        }

        last=calc(1,n/2);

        pos=n/2+1;

    }

    for(register int i=n/2+2;i<=n;i++) {

        if(calc(1,n/2)==calc(n/2+1,i-1)*pwr[n-i]+calc(i+1,n)) {

            if(last!=0&&calc(1,n/2)!=last) {

                puts("NOT UNIQUE");

                return 0;

            }

            last=calc(1,n/2);

            pos=i;

        }

    }

    if(!last) {

        puts("NOT POSSIBLE");

        return 0;

    }

    if(pos<=n/2) {

        for(register int i=n/2+2;i<=n;i++) putchar(s[i]);

    } else {

        for(register int i=1;i<=n/2;i++) putchar(s[i]);

    }

    putchar('\n');

    return 0;

}