不相同子串的个数

题目链接：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 }