比赛 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;
}