题意：让你求这个字符串能组合出来多少个不重复的子串
思路：利用后缀数组height【i】的性质就可以求出每个位置开始能组成的字符串个数为n-sa[i]-height[i] ， n为字符串的长度
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int mx = 50005; int wa[mx],wb[mx],wv[mx],c[mx]; int sa[mx],rk[mx],r[mx],height[mx]; char s[mx]; bool cmp(int *r,int a,int b,int i){ return r[a] == r[b]&&r[a+i] == r[b+i]; } void da(int *r,int *sa,int n,int m){ int *x = wa,*y = wb; for(int i = 0; i < m; i++) c[i] = 0; for(int i = 0; i < n; i++) c[x[i]=r[i]]++; for(int i = 1; i < m; i++) c[i] += c[i-1]; for(int i = n-1; i >= 0; i--) sa[--c[x[i]]] = i; for(int j = 1,p = 1; p < n;j<<=1,m = p){ p = 0; for(int i = n-j; i < n; i++) y[p++] = i; for(int i = 0; i < n; i++) if(sa[i]>=j) y[p++] = sa[i]-j; for(int i = 0; i < n; i++) wv[i] = x[y[i]]; for(int i = 0; i < m; i++) c[i] = 0; for(int i = 0; i < n; i++) c[wv[i]]++; for(int i = 1; i < m; i++) c[i] += c[i-1]; for(int i = n-1; i >= 0; i--) sa[--c[wv[i]]] = y[i]; swap(x,y),p = 1,x[sa[0]] = 0; for(int i = 1; i < n; i++) x[sa[i]] = cmp(y,sa[i],sa[i-1],j)?p-1:p++; } } void getheight(int *r,int n){ int k = 0,j; for(int i = 1; i <= n; i++) rk[sa[i]] = i; for(int i = 0; i < n; height[rk[i++]] = k) for(j = sa[rk[i]-1],k?k--:0;r[i+k] == r[j+k]; k++); } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%s",s); int n = strlen(s); for(int i = 0; i < n; i++) r[i] = s[i]; r[n] = 0; da(r,sa,n+1,256); getheight(r,n); int ans = 0; for(int i = 1; i <= n; i++){ ans += n-sa[i]-height[i]; //printf("%d %d %d\n",n,sa[i],height[i]); } cout<<ans<<endl; } return 0; }