题目链接：http://www.spoj.com/problems/DISUBSTR/
思路：
每个子串一定是某个后缀的前缀,那么原问题等价于求所有后缀之间的不相同的前缀的个数。如果所有的后缀按照suffix(sa[1]),suffix(sa[2]),suffix(sa[3]),……suffix(sa[n])的顺序计算，不难发现，对于每一次新加进来的后缀suffix(sa[k]),它将产生n-sa[k]+1个新的前缀。但是其中有height[k]个是和前面的字符串的前缀是相同的。所以suffix(sa[k])将“贡献”出n-sa[k]+1-height[k]个不同的子串。累加后便是原问题的答案。这个做法的时间复杂度为O(na)。
代码如下：
1 #include<cstring> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<cstring> 5 #include<iostream> 6 using namespace std; 7 const int maxn=1010; 8 int wa[maxn],wb[maxn],wv[maxn],wq[maxn]; 9 int rank[maxn],sa[maxn]; 10 int r[maxn]; 11 char s[maxn]; 12 int height[maxn]; 13 int cmp(int *r,int a,int b,int l) 14 {return r[a]==r[b]&&r[a+l]==r[b+l];} 15 void da(int* r,int *sa,int n,int m) 16 { 17 int i,j,p,*x=wa,*y=wb,*t; 18 for(i=0;i<m;i++) wq[i]=0; 19 for(i=0;i<n;i++) wq[x[i]=r[i]]++; 20 for(i=1;i<m;i++) wq[i]+=wq[i-1]; 21 for(i=n-1;i>=0;i--) sa[--wq[x[i]]]=i; 22 23 for(j=1,p=1;p<n;j*=2,m=p) 24 { 25 for(p=0,i=n-j;i<n;i++) y[p++]=i; 26 for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j; 27 for(i=0;i<n;i++) wv[i]=x[y[i]]; 28 for(i=0;i<m;i++) wq[i]=0; 29 for(i=0;i<n;i++) wq[wv[i]]++; 30 for(i=1;i<m;i++) wq[i]+=wq[i-1]; 31 for(i=n-1;i>=0;i--) sa[--wq[wv[i]]]=y[i]; 32 for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++) 33 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 34 35 } 36 return ; 37 38 } 39 void callheight(int *r,int n) 40 { 41 int i,j,k=0; 42 for(i=1;i<=n;i++) rank[sa[i]]=i; 43 for(i=0;i<n;i++) 44 { 45 if(k) k--; 46 j=sa[rank[i]-1]; 47 while(r[i+k]==r[j+k]) k++; 48 height[rank[i]]=k; 49 } 50 } 51 int main() 52 { 53 int t; 54 scanf("%d",&t); 55 while(t--) 56 { 57 scanf("%s",s); 58 59 int n=strlen(s); 60 for(int i=0;i<n;i++) 61 r[i]=s[i]; 62 r[n]=0; 63 da(r,sa,n+1,130); 64 callheight(r,n); 65 int ans=0; 66 for(int i=1;i<=n;i++) 67 ans+=(n-sa[i]-height[i]); 68 cout<<ans<<endl; 69 70 } 71 return 0; 72 }