记录编号	250581	评测结果	AAAAAAAAAA
题目名称	随机数消除器	最终得分	100
用户昵称	asddddd	是否通过	通过
代码语言	C++	运行时间	0.774 s
提交时间	2016-04-15 12:40:50	内存使用	130.01 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define sigma 2
#define maxn 8000005
using namespace std;
typedef long long LL;
char ch[maxn];
LL ans=0;
struct PRT{
    int cnt,fa[maxn],prt[maxn][sigma],l[maxn],last;
    PRT(){
        cnt=1,last=0,fa[0]=fa[1]=1,l[0]=0,l[1]=-1;
    }
    void extend(int c,int n){
        int p=last;
        while(ch[n-l[p]-1]!=ch[n]) p=fa[p];
        if(!prt[p][c]){
            int now=++cnt,k=fa[p];
            l[now]=l[p]+2;
            while(ch[n-l[k]-1]!=ch[n]) k=fa[k];
            fa[now]=prt[k][c],prt[p][c]=now;
        }
        last=prt[p][c];
    }
}P;
int main(){
    freopen("randomb.in", "r", stdin);
    freopen("randomb.out", "w", stdout);
    scanf("%s",ch+1);
    int n=strlen(ch+1);
    for (int i=1; i<=n; i++) {
        P.extend(ch[i]-'a', i);
    }
    cout<<P.cnt-1;
}