题意
给定字符串,\(q\) 次询问,每次查询字典序第 \(k\) 小的子串。
思路
后缀自动机模版题。
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int maxm = maxn << 1;
struct SAM {
int link[maxm], cnt[maxm], len[maxm];
int nxt[maxm][26];
int last, tot;
void init() {
len[0] = link[0] = 0;
last = tot = 1;
}
void extend(int c) {
c -= 'a';
int cur = ++tot, p = last;
len[cur] = len[last] + 1;
// cnt[cur] = 1;
for (; p && !nxt[p][c]; p = link[p]) nxt[p][c] = cur;
if (!p) {
link[cur] = 1;
} else {
int q = nxt[p][c];
if (len[q] == len[p] + 1) {
link[cur] = q;
} else {
int clone = ++tot;
len[clone] = len[p] + 1;
memcpy(nxt[clone], nxt[q], sizeof(nxt[q]));
link[clone] = link[q];
for (; p && nxt[p][c] == q; p = link[p]) nxt[p][c] = clone;
link[q] = link[cur] = clone;
}
}
last = cur;
}
void dfs(int x) {
cnt[x] = 1;
for (int i = 0; i < 26; ++i) {
if(!nxt[x][i]) continue;
if(!cnt[nxt[x][i]]) dfs(nxt[x][i]);
cnt[x] += cnt[nxt[x][i]];
}
}
void query(int x, int k) {
if (!k) return puts(""), void();
for (int i = 0; i < 26; ++i) {
if (!nxt[x][i]) continue;
if (k <= cnt[nxt[x][i]]) {
putchar(i + 'a');
query(nxt[x][i], k - 1);
break;
} else {
k -= cnt[nxt[x][i]];
}
}
}
} sam;
char str[maxn];
int q, x;
int main() {
// freopen("input.in", "r", stdin);
sam.init();
scanf("%s", str);
for (int i = 0; str[i]; ++i) sam.extend(str[i]);
sam.dfs(1);
scanf("%d", &q);
while (q--) {
scanf("%d", &x);
sam.query(1, x);
}
return 0;
}