bzoj 3998 [TJOI2015]弦论

先扯几句

昨天tc怎么都上不去,突然想再补补姿势,然后发现SAM这个东西理解的很不到位,花了一晚上重新理解了一下,做了下题来回顾下>_<_

Description

对于一个给定长度为$N$的字符串,求它的第$K$小子串是什么
第二行为两个整数$T$和$K$,$T$为$0$则表示不同位置的相同子串算作一个
$T=1$则表示不同位置的相同子串算作多个,$K$的意义如题所述。
$k\le 5*10^5,N\le 10^9$

Solution

很容易想到用SAM做,$T=1$正常做,$T=0$时考虑right数组的意义,把right数组都赋值为1,拓扑排序处理下即可
最后$dfs$或者非递归处理一下即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
const int N = 500005 * 2, M = 26;
struct SAM {
int tot, last, step[N], g[N], par[N], son[N][M], cnt[N], Q[N], ch[N], f[N];
void init() {
tot = last = 0;
memset(par, 0, sizeof(par));
par[0] = -1;
memset(son, 0, sizeof(son));
}
void add(int x) {
int p = last, np = ++tot;
step[np] = step[p] + 1, last = np, ++g[np];//right
ch[np] = x;
for (; !son[p][x] && ~p; p = par[p]) son[p][x] = np;
if (p == -1) return;
int q = son[p][x];
if (step[q] == step[p] + 1) par[np] = q;
else {
step[++tot] = step[p] + 1;
ch[tot] = x;
int nq = tot;
memcpy(son[nq], son[q], sizeof(son[q]));
par[nq] = par[q];
par[np] = par[q] = nq;
for (; son[p][x] == q && ~p; p = par[p]) son[p][x] = nq;
}
}
void topo() {
for (int i = 1; i <= tot; ++i) ++cnt[step[i]];
for (int i = 1; i <= tot; ++i) cnt[i] += cnt[i - 1];
for (int i = 1; i <= tot; ++i) Q[cnt[step[i]]--] = i;
}
void gao(int t) {
for (int i = tot; i >= 0; --i) {
if(t == 0) g[Q[i]] = 1;
else g[par[Q[i]]] += g[Q[i]];
f[Q[i]] = g[Q[i]];
for (int j = 0; j < 26; ++j)
f[Q[i]] += f[son[Q[i]][j]];
}
}
}S;
char s[N];
int main() {
scanf("%s", s);
S.init();
int l = strlen(s);
for (int i = 0; i < l; ++i) S.add(s[i] - 'a');
S.topo();
int t, k;
scanf("%d%d", &t, &k);
S.gao(t);
int rt = 0, sum = 0;
for (int i = 0; i < 26; ++i)
sum += S.f[S.son[0][i]];
if (k > sum) puts("-1");
else {
while (k) {
for (int i = 0; i < 26; ++i)
if (S.son[rt][i]) {
if (S.f[S.son[rt][i]] >= k) {
printf("%c", 'a' + i);
k -= S.g[S.son[rt][i]];
rt = S.son[rt][i];
break;
}
else k -= S.f[S.son[rt][i]];
}
}
}
return 0;
}