后缀数组笔记。
好经典，AcWing 题解区又是一堆看不懂的 SAM。
试图提供 SA 做法。
头有点晕，所以这篇题解写的很乱。

$t=0$ 是好做的。
根据笔记第六题【生成魔咒】可知：

注意其实本质不同子串数可以表示为 $\sum\limits_{i=1}^{n} n - sa_i + 1 - ht_i$，可以通过此公式算出任意一个前缀的答案。

因此相当于是算第 $k$ 小的本质不同子串，直接从小到大遍历后缀直到发现目标串在当前后缀内。

$t=1$ 咋做啊？是不是有二分什么的做法降低复杂度？

直接求排名为 $k$ 的子串很难，考虑换一个角度，二分之后求一个子串的排名（可重）。
由于 $t=1$ 的子串一定在 $t=0$ 中出现过，所以考虑将所有子串排序后二分答案，即二分答案是去重之后的第 $ans$ 个子串。
子串排序也不好做，那就把后缀排序，利用 height 数组求排名。
现在求排序后第 $x$ 个后缀长度为 $len$ 的前缀这一子串的排名：

$$\sum\limits_{i=1}^{x-1} n-sa_i+1 + \sum\limits_{i=x}^{n} \min\big( \text{LCP}(x,i), len \big)$$

由于后缀数组的性质，$[1,x-1]$ 后缀显然字典序小于 $x$；又因为可重，需要把 $[x,n]$ 的 LCP 也算进去。

二分返回值要开 long long。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int t, k, n;
char s[N];

int sa[N], rk[N], x[N << 1], y[N << 1], cnt[N];
void init_SA() {
    int v = 128;
    for (int i = 0; i <= v; i++) cnt[i] = 0;
    for (int i = 1; i <= n; i++) ++cnt[x[i] = (int)s[i]];
    for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--) sa[ cnt[x[i]]-- ] = i;

    for (int len = 1; ; len <<= 1) {
        int tot = 0;
        for (int i = n - len + 1; i <= n; i++) y[++tot] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > len) y[++tot] = sa[i] - len;

        for (int i = 0; i <= v; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++) ++cnt[x[i]];
        for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[ cnt[x[y[i]]]-- ] = y[i], y[i] = 0;

        swap(x, y), tot = 0;
        for (int i = 1; i <= n; i++)
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len]) x[sa[i]] = tot;
            else x[sa[i]] = ++tot;
        v = tot;
        if (v == n) break;
    }
}

int ht[N];
void init_height() {
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, j = 0, now = 0; i <= n; i++) {
        if (rk[i] == 1) { ht[rk[i]] = 0; continue; }
        j = sa[rk[i] - 1], now = max(0, now - 1);
        while (i + now <= n && j + now <= n && s[i + now] == s[j + now]) now++;
        ht[rk[i]] = now;
    }
}

long long check(int k) { //第 k 大去重子串的可重排名
    long long sum = 0, ans = 0; int i;
    for ( i = 1; i <= n; i++) {
        int uniq = n - sa[i] + 1 - ht[i];
        if (sum + uniq >= k) break;
        sum += uniq, ans += n - sa[i] + 1;
    }
    // 在第 i 个后缀内
    // sa[i]; j - sa[i] + 1 - ht[i] <= k - sum;
    // len = max(k - sum + sa[i] - 1 + ht[i] - sa[i] + 1, 0)
    int len = max(k - sum + ht[i], 0ll), Min = ht[i + 1]; ans += len;
    for (int j = i + 1; j <= n; j++) Min = min(Min, ht[j]), ans += min(len, Min);
    return ans;
}

void print(int k) { //输出第 k 大的去重子串
    long long sum = 0; int i;
    for ( i = 1; i <= n; i++) {
        int uniq = n - sa[i] + 1 - ht[i];
        if (sum + uniq >= k) break;
        else sum += uniq;
    }
    for (int j = sa[i]; j - sa[i] + 1 - ht[i] <= k - sum; j++) putchar(s[j]);
}

int main() {
    scanf("%s\n %d %d", s + 1, &t, &k), n = strlen(s + 1);
    if (k > n * 1ll * (n - 1)) return puts("-1"), 0;
    init_SA(), init_height();
    if (t == 0) {
        long long sum = 0;
        for (int i = 1; i <= n; i++) sum += n - sa[i] + 1 - ht[i];
        if (k > sum) return puts("-1"), 0;
        print(k);
    } else {
        int l = 1, r = k;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid) >= k) r = mid;
            else l = mid + 1;
        }
        print(l);
    }
    return 0;
}