记录编号	219743	评测结果	AAAAAAAAAA
题目名称	[SPOJ 705] 不同的子串	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	0.058 s
提交时间	2016-01-15 20:46:48	内存使用	0.36 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct u
{
	u *pre,*e[26];
	int d;
}*rt,*ls;
int n;
char s[50010];
inline void gj(int a)
{
	u *p=new u(),*k=ls;
	p->d=ls->d+1;
	while(k&&(!k->e[a]))
	{
		k->e[a]=p;
		k=k->pre;
	}
	if(!k)
	{
		p->pre=rt;
	}
	else
	{
		u *q=k->e[a];
		if(k->e[a]->d==k->d+1)
			p->pre=q;
		else
		{
			u *nq=new u();
			nq->d=k->d+1;
			nq->pre=q->pre;
			memcpy(nq->e,q->e,sizeof (nq->e));
			q->pre=p->pre=nq;
			while(k&&k->e[a]==q) 
			{
				k->e[a]=nq;
				k=k->pre;
			}
		}
	}
	n+=p->d-p->pre->d;
	ls=p;
}
int main()
{
	freopen("subst1.in","r",stdin);
	freopen("subst1.out","w",stdout);
	rt=new u();
	rt->d=0;
	ls=rt;
	scanf("%s",s);
	int m=strlen(s);
	for(int i=0;i<m;i++)
		gj(s[i]-'A');	
	printf("%d",n);
}