SPOJ 694 Distinct Substrings

Distinct Substrings

Time Limit: 1000ms

Memory Limit: 262144KB

This problem will be judged on SPOJ. Original ID: DISUBSTR
64-bit integer IO format: %lld Java class name: Main

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] - 1表示当前后缀的前缀个数，然后减去 height[i]，也就是减去与前面的重复的。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 100010;
 4 int sa[maxn],rk[maxn],height[maxn];
 5 int c[maxn],t[maxn],t2[maxn],n;
 6 char s[maxn];
 7 void build_sa(int m) {
 8     int i,j,*x = t,*y = t2;
 9     for(i = 0; i < m; ++i) c[i] = 0;
10     for(i = 0; i < n; ++i) c[x[i] = s[i]]++;
11     for(i = 1; i < m; ++i) c[i] += c[i-1];
12     for(i = n-1; i >= 0; --i) sa[--c[x[i]]] = i;
13 
14     for(int k = 1; k <= n; k <<= 1) {
15         int p = 0;
16         for(i = n-k; i < n; ++i) y[p++] = i;
17         for(i = 0; i < n; ++i)
18             if(sa[i] >= k) y[p++] = sa[i] - k;
19         for(i = 0; i < m; ++i) c[i] = 0;
20         for(i = 0; i < n; ++i) c[x[y[i]]]++;
21         for(i = 1; i < m; ++i) c[i] += c[i-1];
22         for(i = n-1; i >= 0; --i)
23             sa[--c[x[y[i]]]] = y[i];
24         swap(x,y);
25         x[sa[0]] = 0;
26         p = 1;
27         for(i = 1; i < n; ++i)
28             if(y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k])
29                 x[sa[i]] = p-1;
30             else x[sa[i]] = p++;
31         if(p >= n) break;
32         m = p;
33     }
34 }
35 void getHeight(){
36     int i,j,k = 0;
37     for(i = 0; i < n; ++i) rk[sa[i]] = i;
38     for(i = 0; i < n; ++i){
39         if(k) --k;
40         j = sa[rk[i]-1];
41         while(i+k<n&&j+k<n&&s[i+k]==s[j+k]) ++k;
42         height[rk[i]] = k;
43     }
44 }
45 int main() {
46     int kase;
47     scanf("%d",&kase);
48     while(kase--){
49         scanf("%s",s);
50         n = strlen(s) + 1;
51         build_sa(128);
52         getHeight();
53         int ret = 0;
54         for(int i = 1; i < n; ++i)
55             ret += n - sa[i] - height[i] - 1;
56         printf("%d
",ret);
57     }
58     return 0;
59 }

View Code

后缀自动机

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 2010;
 4 char str[maxn];
 5 int ret,n;
 6 struct SAM{
 7     struct node{
 8         int son[26],f,len;
 9         void init(){
10             f = -1;
11             len = 0;
12             memset(son,-1,sizeof son);
13         }
14     }e[maxn];
15     int tot,last;
16     int newnode(int len = 0){
17         e[tot].init();
18         e[tot].len = len;
19         return tot++;
20     }
21     void init(){
22         tot = last = 0;
23         newnode();
24     }
25     void extend(int c){
26         int p = last,np = newnode(e[p].len + 1);
27         while(p != -1 && e[p].son[c] == -1){
28             e[p].son[c] = np;
29             p = e[p].f;
30         }
31         if(p == -1) e[np].f = 0;
32         else{
33             int q = e[p].son[c];
34             if(e[p].len + 1 == e[q].len) e[np].f = q;
35             else{
36                 int nq = newnode();
37                 e[nq] = e[q];
38                 e[nq].len = e[p].len + 1;
39                 e[q].f = e[np].f = nq;
40                 while(p != -1 && e[p].son[c] == q){
41                     e[p].son[c] = nq;
42                     p = e[p].f;
43                 }
44             }
45         }
46         last = np;
47     }
48     void solve(){
49         ret = 0;
50         for(int i = 1; i < tot; ++i)
51             ret += e[i].len - e[e[i].f].len;
52         printf("%d
",ret);
53     }
54 }sam;
55 
56 int main(){
57     int kase;
58     scanf("%d",&kase);
59     while(kase--){
60         scanf("%s",str);
61         n = strlen(str);
62         sam.init();
63         for(int i = ret = 0; str[i]; ++i)
64             sam.extend(str[i]-'A');
65         sam.solve();
66     }
67     return 0;
68 }

View Code