比赛 20160414 评测结果 AAAAAAAAAA
题目名称 随机数消除器 最终得分 100
用户昵称 ennekings 运行时间 0.841 s
代码语言 C++ 内存使用 130.01 MiB
提交时间 2016-04-14 16:28:39
显示代码纯文本
#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;
}