694. Distinct Substrings

Problem code: DISUBSTR

 

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.

 

 这个超时，有待检查：

#include
     
      #include
      
       #include
       
        using namespace std;const int maxn=1010;char str[maxn];int wa[maxn],wb[maxn],wv[maxn],wn[maxn],a[maxn],sa[maxn];int cmp(int *r,int a,int b,int l){    return r[a]==r[b] && r[a+l]==r[b+l];}void da(int *r,int *sa,int n,int m){    int i,j,p,*x=wa,*y=wb,*t;    for(i=0; i
        
         =0; i--)   sa[--wn[x[i]]]=i;    for(j=1,p=1; p
         
          =j)    y[p++]=sa[i]-j;        for(i=0; i
          
           =0; i--) sa[--wn[wv[i]]]=y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i
          
         
        
       
      
     

 

 

AC：

#include
     
      #include
      
       #include
       
        using namespace std;const int maxn=1010;char str[maxn];int wa[maxn],wb[maxn],wv[maxn],wn[maxn],a[maxn],sa[maxn];int cmp(int *r,int a,int b,int l){    return r[a]==r[b] && r[a+l]==r[b+l];}void da(int *r,int *sa,int n,int m){    int i,j,p,*x=wa,*y=wb,*t;    for(i=0; i
        
         =0; i--)   sa[--wn[x[i]]]=i;    for(j=1,p=1; p
         
          =j)    y[p++]=sa[i]-j;        for(i=0; i
          
           =0; i--) sa[--wn[wv[i]]]=y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i