题目传送门：https://ac.nowcoder.com/acm/contest/551/C
题目描述
众所周知，CSL 最喜欢的密码是 ******。于是有一天……
为了改变这一点，他决定重新设定一个密码。于是他随机生成了一个很长很长的字符串，并打算选择一个子串作为新密码。他认为安全的密码长度至少为 m，那么他有多少种不同选择方式呢？两种方案不同，当且仅当选出的密码内容不同。
输入描述:
第一行有两个整数 n 和 m ，分别表示 CSL 随机生成的字符串长度和安全的密码的最短长度。
第二行有一个长度为 n 的只含小写字母的字符串 s 表示 CSL 随机生成的字符串。
1≤m≤n≤1051≤m≤n≤105
输出描述:
在一行输出一个整数，表示 CSL 能选择的方案数。
备注:
除样例外，所有的测试数据的字符串的每个字符均从小写字母 a - z 等概率随机生成。
解题思路：
① 枚举长度不超过 10 的子串，用set去重。
为什么是长度不超过 10 呢？因为题目说明了是随机生成，“串中单个字符的选择有26种，串越短，碰撞概率越高，越长则串的可能性越多，碰撞概率很小”
（听说出题人为了让不会后缀数组的童鞋也能 A 这道题，特意搞成了随机），以后在字符串题目看见“随机”二字就要想办法莽一波了。
AC code：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std; const int MAXN = 2e5+;
int N, M;
set<string>ans[MAXN];
string str;
string tp; int main()
{
scanf("%d %d", &N, &M);
cin >> str;
int len = min(N, );
LL res = (LL)(N-M+)*(N-M+)/;
for(int i = M; i <= len; i++){
for(int j = ; j+i- < N; j++){
tp = str.substr(j, i);
if(ans[i].find(tp) != ans[i].end()){
res--;
}
ans[i].insert(tp);
}
}
printf("%lld\n", res);
return ;
}
② 用后缀数组，预处理出 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：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#define MAXN 555555
#define MAXM 200
#define INF 1000000000
#define LL long long
using namespace std;
int r[MAXN];
int wa[MAXN], wb[MAXN], wv[MAXN], tmp[MAXN];
int sa[MAXN]; //index range 1~n value range 0~n-1
int cmp(int *r, int a, int b, int l)
{
return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int *r, int *sa, int n, int m)
{
int i, j, p, *x = wa, *y = wb, *ws = tmp;
for (i = ; i < m; i++) ws[i] = ;
for (i = ; i < n; i++) ws[x[i] = r[i]]++;
for (i = ; i < m; i++) ws[i] += ws[i - ];
for (i = n - ; i >= ; i--) sa[--ws[x[i]]] = i;
for (j = , p = ; p < n; j *= , m = p)
{
for (p = , i = n - j; i < n; i++) y[p++] = i;
for (i = ; i < n; i++)
if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = ; i < n; i++) wv[i] = x[y[i]];
for (i = ; i < m; i++) ws[i] = ;
for (i = ; i < n; i++) ws[wv[i]]++;
for (i = ; i < m; i++) ws[i] += ws[i - ];
for (i = n - ; i >= ; i--) sa[--ws[wv[i]]] = y[i];
for (swap(x, y), p = , x[sa[]] = , i = ; i < n; i++)
x[sa[i]] = cmp(y, sa[i - ], sa[i], j) ? p - : p++;
}
}
int Rank[MAXN]; //index range 0~n-1 value range 1~n
int height[MAXN]; //index from 1 (height[1] = 0)
void calheight(int *r, int *sa, int n)
{
int i, j, k = ;
for (i = ; i <= n; ++i) Rank[sa[i]] = i;
for (i = ; i < n; height[Rank[i++]] = k)
for (k ? k-- : , j = sa[Rank[i] - ]; r[i + k] == r[j + k]; ++k);
return;
}
char s[MAXN];
int main()
{
int lenn = , n = ;
scanf("%d %d", &n, &lenn);
scanf("%s", s);
int m = ;
for(int i = ; i < n; i++)
{
r[i] = (int)s[i];
m = max(m, r[i]);
}
r[n] = ;
da(r, sa, n + , m + );
calheight(r, sa, n);
long long ans = ;
for(int i = ; i <= n; i++){
if(sa[i] <= n-lenn){
ans += n - sa[i] - height[i];
if(height[i] < lenn-) ans-=(lenn--height[i]);
}
}
printf("%lld\n", ans);
return ;
}
当然，正解还有AC自动机，不过本zZ太弱了，还在啃后缀数组。
一个队友打的AC自动机用了 一百多ms， 而我们打的后缀数组用了 18ms，暴力那个直接用了八百多ms...