文件详细信息

下载本文件

本文件的大小为 1033 字节。

#include<algorithm>
#include<cstdio>
#include<cstring>
const int maxn=500005;
char s[maxn];
int n,k,w,sa[maxn],rk[maxn],oldrk[maxn],height[maxn];
int top,stack[maxn],l[maxn];
long long answer;
bool cmp(int x,int y){
	return rk[x]==rk[y]?rk[x+w]<rk[y+w]:rk[x]<rk[y];
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	answer=((long long)n*(n-1)*(n+1))>>1;
	register int i;
	for(i=1;i<=n;i++)sa[i]=i,rk[i]=s[i];
	for(w=1;w<n;w<<=1){
		std::sort(sa+1,sa+n+1,cmp);
		memcpy(oldrk,rk,sizeof(rk));
		for(int p=0,i=1;i<=n;i++){
			if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])rk[sa[i]]=p;
			else rk[sa[i]]=++p;
		}
	}
	for(i=1,k=0;i<=n;i++){
		if(k)k--;
		while(s[i+k]==s[sa[rk[i]-1]+k])k++;
		height[rk[i]]=k;
	}
	for(i=1;i<=n;i++){
		while(height[stack[top]]>height[i])top--;
		l[i]=i-stack[top];
		stack[++top]=i;
	}
	stack[++top]=n+1;
	height[n+1]=-1;
	for(i=n;i;i--){
		while(height[stack[top]]>=height[i])top--;
		answer-=2ll*height[i]*l[i]*(stack[top]-i);
		stack[++top]=i;
	}
	printf("%lld",answer);
	return 0;
}