比赛 20160414 评测结果 AAAAAAEEEE
题目名称 随机数消除器 最终得分 60
用户昵称 /k 运行时间 0.812 s
代码语言 C++ 内存使用 153.19 MiB
提交时间 2016-04-14 16:33:45
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct uhwtree
{
	int n,p;
	int e[8000010][2];
	int fail[8000010];
	int S[8000010];
	int len[8000010];
	int ls;
	inline int getnewpoint(int a)
	{
		len[p]=a;
		++p;
		return p-1;
	}
	inline void gycl()
	{
		n=0;
		getnewpoint(0);
		getnewpoint(-1);
		p=2;
		ls=0;
		S[0]=-1;
		fail[0]=1;
	}
	inline int getfail(int a)
	{
		while(S[n-len[a]-1]!=S[n])
		    a=fail[a];
		return a;
	}
	inline void gj(int a)
	{
		S[++n]=a;
		while(S[n-len[ls]-1]!=S[n])
		{
		    ls=fail[ls];
		}
		int cur=ls;
		if(e[cur][a]==0)
		{
			int now=getnewpoint(2+len[cur]);
			fail[now]=e[getfail(fail[cur])][a];
			e[cur][a]=now;
		}
		ls=e[cur][a];
	}
}c;
char s[300010];
int m;
int main()
{
	freopen("randomb.in","r",stdin);
	freopen("randomb.out","w",stdout);
	scanf("%s",s);
	m=strlen(s);
	c.gycl();
	for(int i=0;i<m;i++)
	    c.gj(s[i]-'a');
	printf("%d\n",c.p-2);
}