题目传送门：https://ac.nowcoder.com/acm/contest/551/C
第一行有两个整数 n 和 m ，分别表示 CSL 随机生成的字符串长度和安全的密码的最短长度。
在一行输出一个整数，表示 CSL 能选择的方案数。
除样例外，所有的测试数据的字符串的每个字符均从小写字母 a - z 等概率随机生成。
① 枚举长度不超过 10 的子串，用set去重。
为什么是长度不超过 10 呢？因为题目说明了是随机生成，“串中单个字符的选择有26种，串越短，碰撞概率越高，越长则串的可能性越多，碰撞概率很小”
（听说出题人为了让不会后缀数组的童鞋也能 A 这道题，特意搞成了随机），以后在字符串题目看见“随机”二字就要想办法莽一波了。
AC code：
1 #include <bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 #define LL long long 4 using namespace std; 5 6 const int MAXN = 2e5+10; 7 int N, M; 8 set<string>ans[MAXN]; 9 string str; 10 string tp; 11 12 int main() 13 { 14 scanf("%d %d", &N, &M); 15 cin >> str; 16 int len = min(N, 10); 17 LL res = (LL)(N-M+2)*(N-M+1)/2; 18 for(int i = M; i <= len; i++){ 19 for(int j = 0; j+i-1 < N; j++){ 20 tp = str.substr(j, i); 21 if(ans[i].find(tp) != ans[i].end()){ 22 res--; 23 } 24 ans[i].insert(tp); 25 } 26 } 27 printf("%lld\n", res); 28 return 0; 29 }
② 用后缀数组，预处理出 sa 和 height 数组
不同子串的个数数是 n-sa[ k ] - height[ k ] (前提 sa[i] <= n-m, 因为要求子串长度至少为 m)
每个子串都是某个后缀的前缀, 对于一个后缀。 它将产生n - sa[k]个前缀
但是有height[k]个前缀是跟前一个字符串的前缀相同。
故每个后缀的贡献是n - sa[k] - height[k]
求和即可
但是这里会把 长度小于 m 的子串也加进来，所以特判一下如果 height[ k ] < m-1 ，则把小于 m 长度的子串数（m-1-height[ k ] ) 删掉即可。
AC code：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <set> 6 #include <queue> 7 #include <algorithm> 8 #define MAXN 555555 9 #define MAXM 200 10 #define INF 1000000000 11 #define LL long long 12 using namespace std; 13 int r[MAXN]; 14 int wa[MAXN], wb[MAXN], wv[MAXN], tmp[MAXN]; 15 int sa[MAXN]; //index range 1~n value range 0~n-1 16 int cmp(int *r, int a, int b, int l) 17 { 18 return r[a] == r[b] && r[a + l] == r[b + l]; 19 } 20 void da(int *r, int *sa, int n, int m) 21 { 22 int i, j, p, *x = wa, *y = wb, *ws = tmp; 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, p = 1; p < n; j *= 2, m = p) 28 { 29 for (p = 0, i = n - j; i < n; i++) y[p++] = i; 30 for (i = 0; i < n; i++) 31 if (sa[i] >= j) y[p++] = sa[i] - j; 32 for (i = 0; i < n; i++) wv[i] = x[y[i]]; 33 for (i = 0; i < m; i++) ws[i] = 0; 34 for (i = 0; i < n; i++) ws[wv[i]]++; 35 for (i = 1; i < m; i++) ws[i] += ws[i - 1]; 36 for (i = n - 1; i >= 0; i--) sa[--ws[wv[i]]] = y[i]; 37 for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++) 38 x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++; 39 } 40 } 41 int Rank[MAXN]; //index range 0~n-1 value range 1~n 42 int height[MAXN]; //index from 1 (height[1] = 0) 43 void calheight(int *r, int *sa, int n) 44 { 45 int i, j, k = 0; 46 for (i = 1; i <= n; ++i) Rank[sa[i]] = i; 47 for (i = 0; i < n; height[Rank[i++]] = k) 48 for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; ++k); 49 return; 50 } 51 char s[MAXN]; 52 int main() 53 { 54 int lenn = 0, n = 0; 55 scanf("%d %d", &n, &lenn); 56 scanf("%s", s); 57 int m = 0; 58 for(int i = 0; i < n; i++) 59 { 60 r[i] = (int)s[i]; 61 m = max(m, r[i]); 62 } 63 r[n] = 0; 64 da(r, sa, n + 1, m + 1); 65 calheight(r, sa, n); 66 long long ans = 0; 67 for(int i = 1; i <= n; i++){ 68 if(sa[i] <= n-lenn){ 69 ans += n - sa[i] - height[i]; 70 if(height[i] < lenn-1) ans-=(lenn-1-height[i]); 71 } 72 } 73 printf("%lld\n", ans); 74 return 0; 75 }
当然，正解还有AC自动机，不过本zZ太弱了，还在啃后缀数组。
一个队友打的AC自动机用了 一百多ms， 而我们打的后缀数组用了 18ms，暴力那个直接用了八百多ms...
C、CSL 的密码 【set暴力 || 后缀数组】 (“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛 )
原文：https://www.cnblogs.com/ymzjj/p/10665023.html
