记录编号	213652	评测结果	AAAAAAAAAA
题目名称	[SPOJ 705] 不同的子串	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.097 s
提交时间	2015-12-12 21:14:31	内存使用	2.08 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int SIZEN=50010;
char str[SIZEN];
int rank[SIZEN],sa[SIZEN],S[SIZEN]={0};
int A[SIZEN],B[SIZEN],N;
int x[SIZEN],y[SIZEN];
int height[SIZEN]={0};;
int sum[SIZEN];
void read()
{
	scanf("%s",str);
	N=strlen(str);
	for(int i=0;i<N;i++) S[i+1]=str[i]-'A'+1;
}
void basesort(int a[],int b[],int c[],int n,int m)//排序前，排序后，关键字
{
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=n;i++) sum[c[a[i]]]++;
	for(int i=0;i<=m;i++) sum[i]+=sum[i-1];
	for(int i=n;i>=1;i--) b[sum[c[a[i]]]--]=a[i];
}
void sort_suf()
{
	for(int i=1;i<=N;i++) x[i]=S[i],A[i]=i;
	basesort(A,sa,x,N,30);
	rank[sa[1]]=1;
	for(int i=2;i<=N;i++)
	{
		if(x[sa[i]]==x[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]];
		else rank[sa[i]]=rank[sa[i-1]]+1;
	}
	for(int k=1;k<=N;k<<=1)
	{
		for(int i=1;i<=N;i++)
		{
			x[i]=rank[i];
			if(i+k<=N) y[i]=rank[i+k];
			else y[i]=0;
			A[i]=i;
		}
		basesort(A,B,y,N,N);
		basesort(B,sa,x,N,N);
		rank[sa[1]]=1;
		for(int i=2;i<=N;i++)
		{
			if(x[sa[i-1]]==x[sa[i]]&&y[sa[i-1]]==y[sa[i]]) rank[sa[i]]=rank[sa[i-1]];
			else rank[sa[i]]=rank[sa[i-1]]+1;
		}
	}
	for(int i=1;i<=N;i++) rank[sa[i]]=rank[sa[i-1]]+1;
}
void clac_height()
{
	int h=0;
	for(int i=1;i<=N;i++)
	{
		if(rank[i]==1) h=0;
		else
		{
			int k=sa[rank[i]-1];
			//cout<<k<<endl;
			h--;
			//cout<<h<<endl;
			if(h<0) h=0;
			while(S[k+h]==S[i+h]) h++;
		}
		height[rank[i]]=h;
	}
}
void prepare()
{
	sort_suf();
	clac_height();
}
void work()
{
	int ans=0;
	for(int i=1;i<=N;i++) ans+=N-sa[i]+1-height[sa[i]];
	printf("%d",ans);
}
int main()
{
	freopen("subst1.in","r",stdin);
	freopen("subst1.out","w",stdout);
	read();
	prepare();
	work();
	return 0;
}