SPOJ Distanct Substrings(求不同子串的数量)

Given a string, we need to find the total number of its distinct substrings.

Input

T- number of test cases. T<=20;
Each test case consists of one string, whose length is <= 1000

Output

For each test case output one number saying the number of distinct substrings.

Example

Sample Input:
2
CCCCC
ABABA

Sample Output:
5
9

Explanation for the testcase with string ABABA: 
len=1 : A,B
len=2 : AB,BA
len=3 : ABA,BAB
len=4 : ABAB,BABA
len=5 : ABABA
Thus, total number of distinct substrings is 9.

题解：题意就是让你求子串的种类；

思路：后缀数组，然后每个字符的贡献为n-sa[i]-height[i];(n为字符的个数)；

参考代码：

 //#include<bits/stdc++.h>

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 #define clr(a,val) memset(a,val,sizeof(a))

 #define lowbit(x) x&-x

 #define eps 1e-6

 typedef long long ll;

 const int INF=0x3f3f3f3f;

 const int maxn=;

 struct SuffixArray{

     int s[maxn];

     int sa[maxn],height[maxn],rank[maxn],n;

     int t[maxn*],t2[maxn*];

     int cnt[maxn];

     void build_sa(int m)//字符都属于0~m-1范围

     {

         int i,*x=t,*y=t2;

         for(i=;i<m;i++) cnt[i]=;

         for(i=;i<n;i++) cnt[x[i]=s[i]]++;

         for(i=;i<m;i++) cnt[i]+=cnt[i-];

         for(i=n-;i>=;i--) sa[--cnt[x[i]]]=i;

         for(int k=,p;k<=n;k <<=)//k<=n

         {

             p=;

             for(i=n-k;i<n;i++) y[p++]=i;

             for(i=;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;

             for(i=;i<m;i++) cnt[i]=;

             for(i=;i<n;i++) cnt[x[y[i]]]++;

             for(i=;i<m;i++) cnt[i]+=cnt[i-];

             for(i=n-;i>=;i--) sa[--cnt[x[y[i]]]]=y[i];

             swap(x,y);

             p=;x[sa[]]=;

             for(i=;i<n;i++)

                    x[sa[i]]=y[sa[i-]]==y[sa[i]]&&y[sa[i-]+k]==y[sa[i]+k]? p-:p++;

             if(p>=n) break;

             m=p;

         }

     }

     void build_height()

     {

         int k=;

         for(int i=;i<n;i++) rank[sa[i]]=i;

         for(int i=;i<n-;i++)

         {

             if(k) k--;

             int j=sa[rank[i]-];

             while(s[i+k]==s[j+k]) k++;

             height[rank[i]]=k;

         }

     }

 } SA;

 int main()

 {

     int n, m, t;

     string str;

     cin>>t;

     while(t--)

     {

         cin>>str;

         int n = str.size();

         for(int i = ; i<n; i++) SA.s[i] = str[i];

         SA.s[n] = ;SA.n=n+;

         SA.build_sa();

         SA.build_height();

         int ans = ;

         for(int i=;i<=n;i++) ans+=n-SA.sa[i]-SA.height[i];

         cout<<ans<<endl;

     }

     return ;

 }