（SPOJ687，后缀数组）

传送门

Distinct Substrings

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

ByteCode '06

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

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 #define maxn 50001
 7 #define rep(i,n) for(int i=0;i<n;i++)
 8 #define Rep(i,n) for(int i=1;i<=n;i++)
 9 #define down(i,n) for(int i=n-1;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<n;d*=2,m=p){
22         for(p=0,i=n-d;i<n;i++) id[p++]=i;
23         rep(i,n) if(sa[i]>=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<n;height[rank[i++]]=k)
39        for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
40      return;
41 }
42 
43 char s[maxn];
44 int r[maxn],sa[maxn];
45 int main(){
46     int i,n,t,ans;
47     scanf("%d",&t);
48     while(t--){
49         scanf("%s",s);
50         n=strlen(s);
51         rep(i,n) r[i]=s[i];
52         r[n]=0;
53         BuildSA(r,sa,n+1,128);
54         CalHeight(r,sa,n);
55         ans=n*(n+1)/2;
56         Rep(i,n) ans-=height[i];
57         printf("%d
",ans);
58     }
59     return 0;
60 }