(color{#0066ff}{ 题目描述 })
为了提高智商,ZJY开始学习弦论。这一天,她在《 String theory》中看到了这样一道问题:对于一个给定的长度为n的字符串,求出它的第k小子串是什么。你能帮帮她吗?
(color{#0066ff}{输入格式})
第一行是一个仅由小写英文字母构成的字符串s
第二行为两个整数t和k,t为0则表示不同位置的相同子串算作一个,t为1则表示不同位置的相同子串算作多个。k的意义见题目描述。
(color{#0066ff}{输出格式})
输出数据仅有一行,该行有一个字符串,为第k小的子串。若子串数目不足k个,则输出-1。
(color{#0066ff}{输入样例})
aabc
0 3
aabc
1 3
aabc
1 11
(color{#0066ff}{输出样例})
aab
aa
-1
(color{#0066ff}{数据范围与提示})
对于10%的数据，n ≤ 1000。
对于50%的数据，t = 0。
对于100%的数据，n ≤ 5 × 10^5, t < 2, k ≤ 10^9。
(color{#0066ff}{ 题解 })
求第k小字串，SAM上贪心跑就行
但是有一些限制
一个是相同的算一个， 一个是相同的算多个
如果算多个，就要算出字串出现次数（鸡排倒推siz）
贪心的时候不能再-1，要减siz（siz个相同的）
然而。。。MLE
本题及其卡指针
写大鸡排5个点MLE
写toposort1个点MLE
幸好上帝还开了一扇窗---->数据水！！！
TM数组少开100000居然A了(雾~
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL in() {
char ch; int x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int maxn = 9e5 + 1;
int type;
struct SAM {
protected:
struct node {
node *ch[26], *fa;
int len, siz, num, du;
node(int len = 0, int siz = 0, int num = 0, int du = 0): fa(NULL), len(len), siz(siz), num(num), du(du) {
memset(ch, 0, sizeof ch);
}
};
node *root, *tail, *lst;
node pool[maxn];
int in[maxn];
void extend(int c) {
node *o = new(tail++) node(lst->len + 1, 1), *v = lst;
for(; v && !v->ch[c]; v = v->fa) v->ch[c] = o;
if(!v) o->fa = root;
else if(v->len + 1 == v->ch[c]->len) o->fa = v->ch[c];
else {
node *n = new(tail++) node(v->len + 1), *d = v->ch[c];
std::copy(d->ch, d->ch + 26, n->ch);
n->fa = d->fa, d->fa = o->fa = n;
for(; v && v->ch[c] == d; v = v->fa) v->ch[c] = n;
}
lst = o;
}
void clr() {
tail = pool;
root = lst = new(tail++) node();
}
void getnum(node *o) {
if(o->num) return;
o->num = type? o->siz : 1;
for(int i = 0; i <= 25; i++) if(o->ch[i]) getnum(o->ch[i]), o->num += o->ch[i]->num;
}
void kth(node *o, int k) {
if(!k) return;
for(int i = 0; i <= 25; i++) {
if(o->ch[i]) {
if(o->ch[i]->num >= k) {
putchar((char)i + 'a');
kth(o->ch[i], type? k - o->ch[i]->siz : k - 1);
return;
}
else k -= o->ch[i]->num;
}
}
}
public:
SAM() { clr(); }
void ins(char *s) { for(char *p = s; *p; p++) extend(*p - 'a'); }
void getnum() { getnum(root); }
void getsiz() {
for(node *o = pool; o != tail; o++) if(o->fa) o->fa->du++;
std::queue<node*> q;
while(!q.empty()) q.pop();
for(node *o = pool; o != tail; o++) if(!o->du) q.push(o);
while(!q.empty()) {
node *o = q.front(); q.pop();
if(o->fa) {
o->fa->siz += o->siz;
o->fa->du--;
if(!o->fa->du) q.push(o->fa);
}
}
}
void kth(int k) { return kth(root, k); }
}sam;
char s[maxn];
int main() {
scanf("%s", s);
type = in();
sam.ins(s);
sam.getsiz();
sam.getnum();
sam.kth(in());
return 0;
}