DTOJ #1166 不相同的子串的个数

题目

给定一个字符串，求不相同的子串的个数。

数据范围

1 ≤ T ≤ 10 1 \leq T \leq 10 1≤T≤10，字符串长度 ≤ 5 × 1 0 5 \leq 5 \times 10^5 ≤5×105。

题解

考虑到字串所有后缀的前缀，所以我们只要把新增的 n + 1 − s a [ i ] n+1-sa[i] n+1−sa[i]个前缀，减去 h e i g h t [ i ] height[i] height[i]个相同的前缀即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,ht[N],sa[N],r[N],fir[N],sec[N],sum[N];
char c[N];
long long ans;
void get_sa(){
	for(int i=1;i<=n;++i)++sum[fir[i]=c[i]];
	for(int i=1;i<=m;++i)sum[i]+=sum[i-1];
	for(int i=n;i;--i)sa[sum[fir[i]]--]=i;
	for(int k=1;k<=n;k<<=1){int tot=0;
		for(int i=n-k+1;i<=n;++i)sec[++tot]=i;
		for(int i=1;i<=n;++i)if(sa[i]>k)sec[++tot]=sa[i]-k;
		for(int i=1;i<=m;++i)sum[i]=0;
		for(int i=1;i<=n;++i)++sum[fir[i]];
		for(int i=1;i<=m;++i)sum[i]+=sum[i-1];
		for(int i=n;i;--i)sa[sum[fir[sec[i]]]--]=sec[i],sec[i]=0;
		swap(fir,sec);
		int cnt=1;fir[sa[1]]=1;
		for(int i=2;i<=n;++i)
			fir[sa[i]]=(sec[sa[i]]==sec[sa[i-1]]&&sec[sa[i]+k]==sec[sa[i-1]+k])? cnt : ++cnt;
		if(cnt==n)break;
		m=cnt;
	}
	for(int i=1;i<=n;++i)r[sa[i]]=i;
}
void get_h(){int k=0,j;
	for(int i=1;i<=n;++i){j=sa[r[i]-1];if(k)--k;while(c[i+k]==c[j+k])++k;ht[r[i]]=k;}
}
int main(){int T;
	scanf("%d",&T);
	while(T--){
	memset(sum,0,sizeof(sum));ans=0;
	scanf("%s",c+1);
	n=strlen(c+1);m=200;
	get_sa();get_h();
	for(int i=1;i<=n;++i)ans+=n+1-sa[i]-ht[i];
	printf("%lld\n",ans);}
	return 0;
}