题目大意：求一个字符串的第$k$大字串，$t$表示长得一样位置不同的字串是否算多个
题解：$SAM$，先求出每个位置可以到达多少个字串（$Right$数组），然后在转移图上$DP$，若$t=1$，初始值赋成$Right$数组大小，否则赋成$1$
卡点：无
C++ Code：
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#define maxn 500010int n, t, k;
namespace SAM {
#define N (maxn << 1)int R[N], nxt[N][26], fail[N];int lst = 1, idx = 1, sz[N];void append(char __ch) {int ch = __ch - 'a';int p = lst, np = lst = ++idx; R[np] = R[p] + 1, sz[np] = 1;for (; p && !nxt[p][ch]; p = fail[p]) nxt[p][ch] = np;if (!p) fail[np] = 1;else {int q = nxt[p][ch];if (R[p] + 1 == R[q]) fail[np] = q;else {int nq = ++idx;fail[nq] = fail[q], R[nq] = R[p] + 1, fail[q] = fail[np] = nq;std::copy(nxt[q], nxt[q] + 26, nxt[nq]);for (; p && nxt[p][ch] == q; p = fail[p]) nxt[p][ch] = nq;}}}int sum[N];int buc[N], rnk[N];void make() {for (int i = 1; i <= idx; i++) ++buc[R[i]];for (int i = 1; i <= idx; i++) buc[i] += buc[i - 1];for (int i = idx; i; i--) rnk[buc[R[i]]--] = i;for (int i = idx; i; i--) {int u = rnk[i];sz[fail[u]] += sz[u];if (!t && u != 1) sz[u] = 1;sum[u] = sz[u];for (int j = 0; j < 26; j++) sum[u] += sum[nxt[u][j]];}}void print(int u) {if (k <= sz[u]) {putchar('\n');exit(0);}k -= sz[u];for (int i = 0; i < 26; i++) {int v = nxt[u][i];if (sum[v] >= k) putchar(i + 'a'), print(v);else k -= sum[v];}}void work() {make();if (sum[1] < k) {puts("-1");exit(0);}sz[1] = 0;print(1);putchar('\n');}
#undef N
}char s[maxn];
int main() {scanf("%s", s); n = strlen(s);for (int i = 0; i < n; i++) SAM::append(s[i]);scanf("%d%d", &t, &k);SAM::work();return 0;
}