不相同子串的个数

题目链接：https://cn.vjudge.net/contest/318888#problem/C

题意：给定一个字符串，求不相同的子串个数。

思路：

感觉就是记住这个公式吧。。至于怎么推出来的我也不知道。。。。如果有大佬知道怎么推出来的欢迎在底下给我留言

但是这里有一个点需要小心：

因为我们求后缀数组的时候为了防止越界的问题的话，会让最后一个为0(一个最小的从未出现的值)。这样的话我们的末尾会多一个0，所以如果是这样我们推出来的公式应该是

(n-1)-sa[k]+1-height[k]

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <string.h>
  5 #include <stdlib.h>
  6 #include <math.h>
  7 #include <queue>
  8 #include <set>
  9 
 10 #define INF 0x3f3f3f3f
 11 #define pii pair<int,int>
 12 #define LL long long
 13 typedef unsigned long long ull;
 14 using namespace std;
 15 const int maxn = 1e5+10;
 16 
 17 
 18 char s[maxn];
 19 int sa[maxn],t[maxn],t2[maxn],c[maxn];
 20 int height[maxn],Rank[maxn];
 21 
 22 void build_sa(int n,int m){
 23     int i,*x = t,*y = t2;
 24     for (i=0;i<m;i++){
 25         c[i] = 0;
 26     }
 27     for (i=0;i<n;i++){
 28         c[x[i] = s[i]]++;
 29     }
 30     for (i=1;i<m;i++){
 31         c[i] += c[i-1];
 32     }
 33     for (i=n-1;i>=0;i--){
 34         sa[--c[x[i]]] = i;
 35     }
 36     for (int k=1;k<=n;k<<=1){
 37         int p = 0;
 38         for (i=n-k;i<n;i++){
 39             y[p++] = i;
 40         }
 41         for (i=0;i<n;i++){
 42             if (sa[i]>=k)
 43                 y[p++] = sa[i]-k;
 44         }
 45         for (i=0;i<m;i++){
 46             c[i] = 0;
 47         }
 48         for (i=0;i<n;i++){
 49             c[x[y[i]]]++;
 50         }
 51         for (i=1;i<m;i++){
 52             c[i] += c[i-1];
 53         }
 54         for (i=n-1;i>=0;i--){
 55             sa[--c[x[y[i]]]] = y[i];
 56         }
 57         swap(x,y);
 58         p = 1;
 59         x[sa[0]] = 0;
 60         for (i=1;i<n;i++){
 61             x[sa[i]] = y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
 62         }
 63         if (p>=n)
 64             break;
 65         m = p;
 66     }
 67 }
 68 
 69 void getHeight(int n){
 70     int i,j,k=0;
 71     for (i=1;i<=n;i++){
 72         Rank[sa[i]] = i;
 73     }
 74     for (i=0;i<n;i++){
 75         if (k)
 76             k--;
 77         j = sa[Rank[i]-1];
 78         while (s[i+k] == s[j+k])
 79             k++;
 80         height[Rank[i]] = k;
 81     }
 82 }
 83 
 84 void solve(int n){
 85     int ans = 0;
 86     for (int i=1;i<=n;i++){
 87         ans += n-sa[i]-height[i];
 88     }
 89     printf("%d\n",ans);
 90 }
 91 
 92 
 93 int main(){
 94     int T;
 95     scanf("%d",&T);
 96     while (T--){
 97         scanf("%s",s);
 98         int len = strlen(s);
 99         build_sa(len+1,200);
100         getHeight(len);
101         solve(len);
102     }
103     return 0;
104 }

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string.h>
 5 #include <stdlib.h>
 6 #include <math.h>
 7 #include <queue>
 8 #include <set>
 9 
10 #define INF 0x3f3f3f3f
11 #define pii pair<int,int>
12 #define LL long long
13 using namespace std;
14 typedef unsigned long long ull;
15 const int MAXN = 2e5 + 10;
16 
17 int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
18 int sta[MAXN];
19 int cnt[MAXN];
20 void Suffix(int *r, int *sa, int n, int m)
21 {
22     int i, j, k, *x = wa, *y = wb, *t;
23     for(i = 0; i < m; ++i) ws_[i] = 0;
24     for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;
25     for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
26     for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;
27     for(j = 1, k = 1; k < n; j *= 2, m = k)
28     {
29         for(k = 0, i = n - j; i < n; ++i) y[k++] = i;
30         for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;
31         for(i = 0; i < n; ++i) wv[i] = x[y[i]];
32         for(i = 0; i < m; ++i) ws_[i] = 0;
33         for(i = 0; i < n; ++i) ws_[wv[i]]++;
34         for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
35         for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];
36         t = x;
37         x = y;
38         y = t;
39         for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
40             x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
41     }
42 }
43 int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
44 char s[MAXN];
45 int indexx[MAXN],vis[200];
46 void calheight(int *r,int *sa,int n)
47 {
48     int i,j,k=0;
49     for(i=1; i<=n; i++)Rank[sa[i]]=i;
50     for(i=0; i<n; height[Rank[i++]]=k)
51         for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
52 }
53 
54 bool check(int x,int n,int k){
55     int tot = 1;
56     for (int i=1;i<n;i++){
57         if (height[i]>=x){
58             tot++;
59         }
60         else {
61             if (tot>=k)
62                 return true;
63             tot = 1;
64         }
65     }
66     return tot>=k;
67 }
68 
69 
70 
71 int main(){
72     int T;
73     scanf("%d",&T);
74     while (T--){
75         scanf("%s",s);
76         int n = strlen(s);
77         for (int i=0;i<n;i++){
78             r[i] = s[i];
79         }
80         r[n] = 0;
81         Suffix(r,sa,n+1,300);
82         calheight(r,sa,n);
83         LL ans = 0;
84         for (int i=1;i<=n;i++){
85             ans += (n-sa[i]-height[i]);
86         }
87         printf("%lld\n",ans);
88     }
89     return 0;
90 }