# 某岛

… : "…アッカリ～ン . .. . " .. .
March 21, 2020

## Luogu P3975 [TJOI2015]弦论

Luogu 传送门

```
const int N = int(1e6) + 9, Z = 26;

namespace SAM{

int trans[N][Z],par[N],len[N],sum[N],cnt[N],tail,tot;
char buf[N];

int new_node(){
RST(trans[tot]);
}
int new_node(int u){
CPY(trans[tot],trans[u]),par[tot]=par[u];
}
#define v trans[u]
#define p par[u]
#define pp par[uu]

int Ext(int c){
int u = tail, uu = new_node(); len[uu] = len[u] + 1;
while (u && !v) v = uu, u = p;
if (!u && !v) v = uu, pp = 0;
else{
if (len[v] == len[u] + 1) pp = v;
else{
int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;
par[_v] = pp = vv; while (v == _v) v = vv, u = p;
}
}

return tail = uu;
}

void Init(){
tail = tot = 0; new_node(), RS(buf); REP_S(cur, buf) cnt[Ext(*cur - 'a')] = 1;

static int C[N], Q[N];
REP(i, tot) ++C[len[i]];
REP_1(i, len[tail]) C[i] += C[i-1];
REP(i, tot) Q[--C[len[i]]] = i;

//FOR(u, 1, tot) {

DWN(i, tot, 1) {
int u = Q[i];
if (p) cnt[p] += cnt[u];
//cout << u << " " << cnt[u] << endl;
}

int t; RD(t);

DWN(i, tot, 0){
int u = Q[i];

if (t == 0) cnt[u] = 1;

int t = 0;

sum[u] = cnt[u];
REP(c, Z) if (v){
sum[u] += sum[v];
}
}

DWN(u, tot, 0){
//cnt[p] += cnt[u];
//   cout << u << " " << sum[u] << " " << cnt[u] << endl;
}
cnt[0] = 0;

}

#undef c
void kth(int k){
--k;

if (k >= sum[0]) {
cout << -1 << endl;
return;
}

int u = 0; while (k >= cnt[u]){
k -= cnt[u]; for (int i=0;;++i){
if (k >= sum[v]) k -= sum[v];
else{
putchar(c+'a');
u = v; break;
}
}
}
puts("");
}

} using namespace SAM;

int main(){

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

Init(); //Rush kth(RD());
kth(RD());

}
```