Time Limit: 1000MS

Memory Limit: Unknown

64bit IO Format: %lld & %llu

Description

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.

Source

 

后缀数组裸题。。。代码真不好记。。所以背下来了。。

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 #define maxn 50001 7 #define rep(i,n) for(int i=0;i
        
         =0;i--)10 11 int wa[maxn],wb[maxn],cnt[maxn],tx[maxn];12 int cmp(int *r,int a,int b,int l){13     return r[a]==r[b]&&r[a+l]==r[b+l];14 }15 void BuildSA(int *r,int *sa,int n,int m){16     int i,d,p,*x=wa,*id=wb,*t;17     rep(i,m) cnt[i]=0;18     rep(i,n) cnt[x[i]=r[i]]++;19     rep(i,m) cnt[i+1]+=cnt[i];20     down(i,n) sa[--cnt[x[i]]]=i;21     for(d=1,p=1;p
         
          =d) id[p++]=sa[i]-d;24         rep(i,n) tx[i]=x[id[i]];25         rep(i,m) cnt[i]=0;26         rep(i,n) cnt[tx[i]]++;27         rep(i,m) cnt[i+1]+=cnt[i];28         down(i,n) sa[--cnt[tx[i]]]=id[i];29         swap(x,id);p=1;x[sa[0]]=0;30         Rep(i,n-1)31           x[sa[i]]=cmp(id,sa[i-1],sa[i],d)?(p-1):(p++);32     }33 }34 int rank[maxn],height[maxn];35 void CalHeight(int *r,int *sa,int n){36      int i,j,k=0;37      Rep(i,n) rank[sa[i]]=i;38      for(i=0;i