705. New Distinct Substrings

Problem code: SUBST1

 

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 <= 50000

Output

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

Example

Input:2CCCCCABABAOutput:59

---

Added by:
Date:	2006-01-18
Time limit:	2s
Source limit:	50000B
Memory limit:	256MB
Cluster:
Languages:	All except: NODEJS PERL 6
Resource:	Base on a problem in ByteCode06

 

 

 

 

 

 

 

 

 

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 using namespace std; 5 #define N 51000 6 char a[N]; 7 int c[N],d[N],e[N],sa[N],height[N],n,b[N],m; 8 int cmp(int *r,int a,int b,int l) 9 {10     return r[a]==r[b]&&r[a+l]==r[b+l];11 }12 void da()13 {14     int i,j,p,*x=c,*y=d,*t;15     for(i=0;i
          
           =0; i--)sa[--b[x[i]]]=i;19     for(j=1,p=1; p
           
            =j)y[p++]=sa[i]-j;23         for(i=0; i
            
             =0; i--)sa[--b[e[i]]]=y[i];28 for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i
             
              >t;45 for(i=0;i