弦论

Time Limit: 10 Sec Memory Limit: 256 MB

Description

对于一个给定长度为N的字符串,求它的第K小子串是什么。

Input

第一行是一个仅由小写英文字母构成的字符串S。
  第二行为两个整数T和K,T为0则表示不同位置的相同子串算作一个。
  T=1则表示不同位置的相同子串算作多个。K的意义如题所述。

Output

输出仅一行,为一个数字串,为第K小的子串。如果子串数目不足K个,则输出-1

Sample Input

aabc
 0 3

Sample Output

aab

HINT

N<=5*10^5, T<2, K<=10^9

Solution

首先我们先构造一个后缀自动机,然后分类讨论:

1. 如果T=0,点权为1。为什么呢?一个点有一个Right集合,一个Right集合可以表达多个子串 ,然后我们一个点 -> 另外一个点 其实不止一条边,我们每条边涵盖了一个信息,意味着 这个点->(走这条边)->到达了下一个点 通过这条边得到的那个新子串,而这多个新子串构成了一个 新的点。所以一条合法的路径,就表达了一个子串

2. 如果T=1,点权为Right集合大小。Right集合是结束位置的合集,那么Right集合大小就表示这条路径表达的这个子串出现了多少次。

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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 2e6+5;

int n,T,k;
char ch[500005];

inline int get()
{
int res=1,Q=1; char c;
while( (c=getchar())<48 || c>57)
if(c=='-')Q=-1;
if(Q) res=c-48;
while((c=getchar())>=48 && c<=57)
res=res*10+c-48;
return res*Q;
}

struct SAM
{
int v[500005], q[ONE], num[ONE], size[ONE];
int a[ONE][28], len[ONE], fa[ONE], New;
int last, cnt;

SAM() {last = cnt = 1;}
void Add(int c)
{
int x=last, New=last=++cnt;
len[New] = len[x] + 1;
num[New] = 1;
while(x && !a[x][c]) a[x][c] = New, x = fa[x];
if(!x) {fa[New] = 1; return;}

int q = a[x][c];
if(len[x] + 1 == len[q]) fa[New] = q;
else
{
int Nq = ++cnt; len[Nq] = len[x] + 1;
memcpy(a[Nq], a[q], sizeof(a[q]));
fa[Nq] = fa[q];
fa[New] = fa[q] = Nq;
while(a[x][c] == q) a[x][c] = Nq, x = fa[x];
}
}

void Update()
{
for(int i=1;i<=cnt;i++) v[len[i]]++;
for(int i=1;i<=n;i++) v[i] += v[i-1];
for(int i=cnt;i>=1;i--) q[v[len[i]]--] = i;


for(int i=cnt; i>=1; i--)
{
int x = q[i];
if(!T) num[x] = 1; else num[fa[x]] += num[x];
}
num[1] = 0;

for(int i=cnt; i>=1; i--)
{
int x = q[i];
size[x] = num[x];
for(int j=1; j<=26; j++)
size[x] += size[a[x][j]];
}
}

void Dfs(int u,int k)
{
if(k <= num[u]) return;
k -= num[u];
for(int j=1; j<=26; j++)
if(a[u][j])
{
if(k > size[a[u][j]]) k -= size[a[u][j]];
else
{
printf("%c",j+'a'-1);
Dfs(a[u][j], k);
return;
}
}
}
}S;

int main()
{
scanf("%s",ch+1); n = strlen(ch+1);
T = get(); k = get();
for(int i=1;i<=n;i++) S.Add(ch[i]-'a'+1);

S.Update();

if(k > S.size[1]) printf("-1");
else S.Dfs(1, k);

}