P3975-[TJOI2015]弦论
题目:
题目描述:
为了提高智商，ZJY 开始学习弦论。这一天，她在《String theory》中看到了这样一道问题：对于一个给定的长度为 $n$ 的字符串，求出它的第 $k$ 小子串是什么。你能帮帮她吗?
输入格式:
第一行是一个仅由小写英文字母构成的字符串 $s$。
第二行为两个整数 $t$ 和 $k$，$t$ 为 $0$ 则表示不同位置的相同子串算作一个，$t$ 为 $1$ 则表示不同位置的相同子串算作多个。$k$ 的意义见题目描述。
输出格式:
输出数据仅有一行,该行有一个字符串，为第 $k$ 小的子串。若子串数目不足 $k$ 个，则输出 $-1$。
样例:
样例输入 1:
样例输出 1:
样例输入 2:
样例输出 2:
样例输入 3:
样例输出 3:
思路:
实现:
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| #include "ybwhead/ios.h"
int nl, flag;
int k;
const int maxn = 1e6 + 10;
struct SAM
{
struct node
{
int fa, len;
int siz, mp[26];
int sum;
} x[maxn << 1];
int las, cnt;
SAM()
{
las = cnt = 1;
}
void insert(int c)
{
int p = las;
x[las = ++cnt] = {0, nl, 1, {0}, 0};
for (; p && !x[p].mp[c]; p = x[p].fa)
x[p].mp[c] = las;
if (!p)
{
x[las].fa = 1;
return;
}
int q = x[p].mp[c];
if (x[q].len == x[p].len + 1)
{
x[las].fa = q;
return;
}
x[++cnt] = x[q];
x[cnt].len = x[p].len + 1;
x[cnt].siz = 0;
x[q].fa = x[las].fa = cnt;
for (; x[p].mp[c] == q; p = x[p].fa)
x[p].mp[c] = cnt;
}
int a[maxn];
void pre()
{
if (flag)
{
for (int i = 1; i <= cnt; i++)
x[x[a[i]].fa].siz += x[a[i]].siz;
}
for (int i = 1; i <= cnt; i++)
x[i].sum = x[i].siz = max(x[i].siz, 1);
x[1].siz = x[1].sum = 0;
// x[0].sum = 0;
for (int i = 1; i <= cnt; i++)
{
for (int j = 0; j < 26; j++)
{
x[a[i]].sum += x[x[a[i]].mp[j]].sum;
}
}
}
void print()
{
if (k > x[1].sum)
{
puts("-1");
return;
}
int now = 1;
k -= x[now].siz;
while (k > 0)
{
int p = 0;
while (k > x[x[now].mp[p]].sum)
{
k -= x[x[now].mp[p]].sum;
p++;
}
now = x[now].mp[p];
putchar('a' + p);
k -= x[now].siz;
}
}
} s;
string s1;
int cmp(int a, int b)
{
return s.x[a].len > s.x[b].len;
}
int main()
{
yin >> s1;
yin >> flag >> k;
for (nl = 1; nl <= s1.size(); nl++)
s.insert(s1[nl - 1] - 'a');
for (int i = 1; i <= s.cnt; i++)
s.a[i] = i;
sort(s.a + 1, s.a + s.cnt + 1, cmp);
s.pre();
s.print();
return 0;
}
|