题意

求字符串字典序第 $k$ 大子串（本质不同或位置不同）。

$n\leq 5\times 10^5$

题解

DP 求得结点大小（size），再 DP 求 DAG 子树（或子图？）的大小，像平衡树那样转移即可。

代码

const int N = 1e6 + 10;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {

	char s[N];
	int n, t;
	ll k;

	ll f[N], g[N];
	bool vis[N];

	namespace SAM {
		int Last, tot;
		int fail[N], maxlen[N];
		int trans[N][26];
		
		void Build() { Last = tot = 1; }
		void Insert (int c) {
			int p = Last, np = ++tot;
			f[np] = 1;
			maxlen[np] = maxlen[p] + 1;
			for (; p && !trans[p][c]; p = fail[p])
				trans[p][c] = np;
			if (!p) fail[np] = 1;
			else {
				int q = trans[p][c];
				if (maxlen[q] == maxlen[p] + 1) fail[np] = q;
				else {
					int nq = ++tot; fail[nq] = fail[q];
					memcpy (trans[nq], trans[q], 26 << 2);
					maxlen[nq] = maxlen[p] + 1;
					for (; p && trans[p][c] == q; p = fail[p])
						trans[p][c] = nq;
					fail[np] = fail[q] = nq;
				}
			}
			Last = np;
		}

	}

	int head[N], tot;
	struct Edge {
		int to, nxt;
	} e[N];
	void Add(int u, int v) {
		e[++tot] = (Edge) {v, head[u]}, head[u] = tot;
	}

	void dfs(int u) {
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			dfs (v);
			f[u] += f[v];
		}
	}

	void dfs2 (int u) {
		if (vis[u]) return; vis[u] = 1;
		for (int i = 0; i < 26; i++) {
			int v = SAM::trans[u][i];
			if (!v) continue;
			dfs2(v);
			g[u] += g[v];
		}
	}

	void Print (int u, ll k) {
		if (k <= f[u]) return; else k -= f[u];
		for (int i = 0; i < 26; i++) {
			int v = SAM::trans[u][i];
			if (!v) continue;
			else if (k > g[v]) k -= g[v];
			else { printf ("%c", i + 'a'); Print(v, k); return; }
		}
	}

	int main() {
		scanf ("%s", s + 1);
		n = strlen(s + 1);
		t = Read(), k = Read();
		SAM::Build();
		for (int i = 1; i <= n; i++) SAM::Insert (s[i] - 'a');
		for (int i = 2; i <= SAM::tot; i++) Add(SAM::fail[i], i);
		dfs (1);
		for (int i = 1; i <= SAM::tot; i++) g[i] = t? f[i]: (f[i] = 1);	
		f[1] = g[1] = 0, dfs2 (1); 
		if (k > g[1]) puts("-1");
		else Print(1, k);
		return 0;
	}
}

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	return Main::main();
}