记录编号	122451	评测结果	AAAAAAAAAA
题目名称	[SPOJ 705] 不同的子串	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.087 s
提交时间	2014-09-23 19:27:14	内存使用	1.89 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=50010;
int sum[SIZEN]={0};//桶排序用
void basesort(int a[],int b[],int c[],int n,int m){//排序前a,排序后b,关键字c,下标0~n-1,关键字0~m
	memset(sum,0,sizeof(sum));
	for(int i=0;i<n;i++) sum[c[a[i]]]++;
	for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
	for(int i=n-1;i>=0;i--) b[--sum[c[a[i]]]]=a[i];
}
int A[SIZEN]={0},B[SIZEN]={0};
int x[SIZEN]={0},y[SIZEN]={0};
void sort_suf(char S[],int rank[],int sa[],int N){//串S,名次数组rank,顺序数组sa,下标0~N-1
	for(int i=0;i<N;i++) x[i]=S[i],A[i]=i;
	basesort(A,sa,x,N,256);
	rank[sa[0]]=1;
	for(int i=1;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=0;i<N;i++){
			x[i]=rank[i];
			y[i]=i+k<N?rank[i+k]:0;
			A[i]=i;
		}
		basesort(A,B,y,N,N);
		basesort(B,sa,x,N,N);
		rank[sa[0]]=1;
		for(int i=1;i<N;i++)
			if(x[sa[i]]==x[sa[i-1]]&&y[sa[i]]==y[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]];
			else rank[sa[i]]=rank[sa[i-1]]+1;
	}
	for(int i=0;i<N;i++) rank[sa[i]]=i;
}
void calc_height(char S[],int rank[],int sa[],int height[],int N){
	int h=0;
	for(int i=0;i<N;i++){
		if(rank[i]==0) h=0;
		else{
			int k=sa[rank[i]-1];//排在i前一位的后缀
			if(--h<0) h=0;
			while(S[i+h]==S[k+h]) h++;
		}
		height[rank[i]]=h;
	}
}
int N;
char S[SIZEN]={0};
int rank[SIZEN]={0},sa[SIZEN]={0},height[SIZEN]={0};
void work(void){
	sort_suf(S,rank,sa,N);
	calc_height(S,rank,sa,height,N);
	int ans=0;
	for(int i=0;i<N;i++) ans+=N-sa[i]-height[i];
	printf("%d\n",ans);
}
void read(void){
	memset(S,0,sizeof(S));
	scanf("%s",S);
	N=strlen(S);
}
int main(){
	freopen("subst1.in","r",stdin);
	freopen("subst1.out","w",stdout);
	read();
	work();
	/*int T;scanf("%d",&T);
	while(T--){
		read();
		work();
	}*/
	return 0;
}