比赛 |
20160414 |
评测结果 |
AAAAAAAAAA |
题目名称 |
随机数消除器 |
最终得分 |
100 |
用户昵称 |
lxtgogogo |
运行时间 |
3.754 s |
代码语言 |
C++ |
内存使用 |
803.66 MiB |
提交时间 |
2016-04-14 16:18:08 |
显示代码纯文本
/*
Language: c++
Author: lxtgogogo
Date: 2016.04.14
为了防止你们说我回文树的模板长,我特意压码!
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int r=8000005;
int n=0,suff=0,ge=1;
char ch[r]={};
struct hehe{
int nex[26];
int sufflink,len,num;
}tree[r];
void add(int pos){
int cur=suff,curlen=0;
int w=ch[pos]-'a';
while(1)
{
curlen=tree[cur].len;
if(pos-curlen-1>=0 && ch[pos-curlen-1]==ch[pos]) break;
cur=tree[cur].sufflink;
}
if(tree[cur].nex[w]!=0){suff=tree[cur].nex[w];return ;}
suff=tree[cur].nex[w]=++ge;
tree[ge].len=tree[cur].len+2;
if(tree[ge].len==1){tree[ge].sufflink=1;tree[ge].num=1;return ;}
while(1)
{
cur=tree[cur].sufflink;
curlen=tree[cur].len;
if(pos-curlen-1>=0 && ch[pos-curlen-1]==ch[pos]){tree[ge].sufflink=tree[cur].nex[w];break;}
}
tree[ge].num=tree[tree[ge].sufflink].num+1;
}
int main(){
freopen("randomb.in","r",stdin);
freopen("randomb.out","w",stdout);
while(1){ch[n]=getchar();if(ch[n]=='\n'){break;}n++;}
tree[0].len=-1;tree[0].sufflink=0;
tree[1].len=0;tree[1].sufflink=0;
for(int i=0;i<n;i++)
add(i);
printf("%d\n",ge-1);
fclose(stdin);fclose(stdout);
return 0;
}