P2408 不同子串个数

P2408 不同子串个数

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5+5;
 4 typedef long long ll;
 5 char s[maxn];
 6 int sa[maxn], t[maxn], t2[maxn], c[maxn];
 7 int n;
 8 //构造字符串s的后缀数组， 每个字符值必须为0 ～ m-1
 9 void build_sa(int m) {
10     int *x = t, *y = t2;
11     //基数排序
12     for(int i = 0; i < m; i++) c[i] = 0;
13     for(int i = 0; i < n; i++) c[x[i] = s[i]]++;
14     for(int i = 1; i < m; i++) c[i] += c[i-1];
15     for(int i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;
16     for(int k = 1; k <= n; k <<= 1) {
17         int p = 0;
18         //直接利用sa数组排序第二关键字
19         for(int i = n-k; i < n; i++) y[p++] = i;
20         for(int i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
21         //基数排序第一关键字
22         for(int i = 0; i < m; i++) c[i] = 0;
23         for(int i = 0; i < n; i++) c[x[y[i]]]++;
24         for(int i = 1; i < m; i++) c[i] += c[i-1];
25         for(int i = n-1; i>= 0; i--) sa[--c[x[y[i]]]] = y[i];
26         //根据sa和y数组计算新的x数组
27         swap(x, y);
28         p = 1;
29         x[sa[0]] = 0;
30         for(int i = 1; i < n; i++)
31             x[sa[i]] = (y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i]+k] ? p-1 : p++);
32         if(p >= n) break;
33         m = p;
34     }
35 }
36
37 int rank_[maxn]; //rank[i]代表后缀i在sa数组中的下标
38 int height[maxn]; //height[i] 定义为sa[i-1] 和 sa[i] 的最长公共前缀
39 //后缀j和k的LCP长度等于RMQ(height, rank[j]+1, rank[k])
40 void get_height() {
41     int i, j, k = 0;
42     for(int i = 0; i < n; i++) rank_[sa[i]] = i;
43     for(int i = 0; i < n; i++) {
44         if(!rank_[i]) continue;
45         int j = sa[rank_[i]-1];
46         if(k) k--;
47
48         while(s[i+k] == s[j+k]) k++;
49         height[rank_[i]] = k;
50     }
51 }
52 int main() {
53     scanf("%d",&n);
54     scanf("%s",s);
55     build_sa(128);
56     get_height();
57     ll ans = 0;
58     for (int i = 0; i < n; i++) {
59         ans += n-sa[i]-height[i];
60     }
61     printf("%lld\n",ans);
62     return 0;
63 }