记录编号	538742	评测结果	AAAAAAAAAA
题目名称	[SPOJ 705] 不同的子串	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.071 s
提交时间	2019-07-30 16:08:06	内存使用	148.13 MiB

#include<bits/stdc++.h>
#define LL long long
#define I inline
using namespace std; 
const int N=1e6+7;
struct Node
{
	int ch[26],fa,len;
} pt[N];
struct edge
{
	int nx,to;
} e[N<<1];
char s[N];
int tot=1,lst=1,head[N],cnt;
LL dp[N];
void extend(int c)
{
	int p=lst,np=lst=++tot;
	pt[np].len=pt[p].len+1;
	for (;p&&!pt[p].ch[c];p=pt[p].fa) pt[p].ch[c]=np;
	if (!p) pt[np].fa=1;
	else 
	{
		int q=pt[p].ch[c];
		if (pt[q].len==pt[p].len+1) pt[np].fa=q;
		else 
		{
			int nq=++tot;pt[nq]=pt[q];
			pt[nq].len=pt[p].len+1;
			pt[q].fa=pt[np].fa=nq;
			for (;p&&pt[p].ch[c]==q;p=pt[p].fa) pt[p].ch[c]=nq;
		}
	}
}
void add_edge(int a,int b)
{
	cnt++;e[cnt].nx=head[a];e[cnt].to=b;head[a]=cnt;
}
void solve(int x)
{
	for (int i=head[x];i;i=e[i].nx)
	{
		int y=e[i].to;
		if (!dp[y]) solve(y);
		dp[x]+=dp[y]+1;
	}
}
int main()
{
	freopen("subst1.in","r",stdin);
	freopen("subst1.out","w",stdout);
	scanf("%s",s);int len=strlen(s);
	for (int i=0;i<len;i++) extend(s[i]-'A');
	for (int i=1;i<=tot;i++) 
		for (int j=0;j<26;j++) 
			if (pt[i].ch[j])add_edge(i,pt[i].ch[j]);
	solve(1);
	printf("%lld\n",dp[1]);
	return 0;
}