【题意】
求不相同的子串的个数
【分析】
考虑每一个后缀的前缀表示了所有的子串,有n*(n+1)/2个
减去重复的即可,也就是所有的height之和
【代码】
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int maxn=2e3+5; int n,T; char a[maxn]; int h[maxn],maxi,id[maxn]; int sa[maxn],rk[maxn],oldrk[maxn],cnt[maxn],fz[maxn]; bool cmp(int x,int y,int w) { return oldrk[x]==oldrk[y] && oldrk[x+w]==oldrk[y+w]; } void calcsa() { int m=233; for(int i=0;i<=m;i++) cnt[i]=0; for(int i=1;i<=n;i++) cnt[rk[i]=a[i]]++; for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1]; for(int i=n;i>=1;i--) sa[cnt[rk[i]]--]=i; int i,p; for(int w=1;;w<<=1,m=p) { for(p=0,i=n;i>n-w;i--) id[++p]=i; for(i=1;i<=n;i++) if(sa[i]>w) id[++p]=sa[i]-w; for(i=0;i<=m;i++) cnt[i]=0; for(i=1;i<=n;i++) cnt[fz[i]=rk[id[i]]]++; for(i=1;i<=m;i++) cnt[i]+=cnt[i-1]; for(i=n;i>=1;i--) sa[cnt[fz[i]]--]=id[i]; for(i=1;i<=n;i++) oldrk[i]=rk[i]; for(p=0,i=1;i<=n;i++) rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p; if(p==n) { for(i=1;i<=n;i++) sa[rk[i]]=i; break; } } } long long sumh=0; void calch() { int i,k=0; sumh=0; for(i=1;i<=n;i++) { if(k) k--; while(a[i+k]==a[sa[rk[i]-1]+k]) k++; h[rk[i]]=k; sumh+=k; } } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d",&T); for(int i=1;i<=T;i++) { scanf("%s",a+1); n=strlen(a+1); calcsa(); calch(); long long ans=1LL*(n+1)*n/2; printf("%lld\n",ans-sumh); } return 0; }