Description：

对于不同位置相同子串算作一个 $/$ 多个，分别求第 $k$ 小子串。

$1\le len \le 500000$

Solution：

不同位置算作一个那么后缀自动机上从根节点开始每一条路径都代表了一个本质不同的子串，所以可以把每个状态赋 $1$ 再 $DP$ 求和，不同位置算作多个那么每个状态代表的字符串个数是这个状态的 $right$ 集合大小，可以先递推求出这个，再 $DP$ 求和，询问就在对应的数组上跑即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

#define MAXL 500010

char str[MAXL];

struct node

{

	int tr[26],maxl,par;

}s[MAXL << 1];

int last = 1,root = 1,ptr = 1;

inline int newnode(int k){++ptr;s[ptr].maxl = k;return ptr;}

typedef long long ll;

ll siz[MAXL << 1][2];

ll f[MAXL << 1][2];

inline void extend(int k)

{

	register int p = last;

	register int np = newnode(s[p].maxl + 1);siz[np][1] = 1;

	for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

	if(p == 0)s[np].par = root;

	else

	{

		register int q = s[p].tr[k];

		if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

		else

		{

			register int nq = newnode(s[p].maxl + 1);

			memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

			s[nq].par = s[q].par;

			s[q].par = s[np].par = nq;

			for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

		}

	}

	last = np;

	return;

}

int c[MAXL << 1],a[MAXL << 1];

void dp()

{

	register int l = strlen(str + 1);

	for(register int i = 1;i <= ptr;++i)c[s[i].maxl]++;

	for(register int i = 1;i <= l;++i)c[i] += c[i - 1];

	for(register int i = ptr;i >= 1;--i)a[c[s[i].maxl]--] = i;

	for(register int i = ptr;i >= 1;--i)siz[s[a[i]].par][1] += siz[a[i]][1];

	for(register int i = 1;i <= ptr;++i)f[i][0] = siz[i][0] = 1,f[i][1] = siz[i][1];

	for(register int i = ptr;i >= 1;--i)

	{

		register int u = a[i];

		for(int k = 0;k < 26;++k)

		{

			if(s[u].tr[k] != 0)

			{

				f[u][0] += f[s[u].tr[k]][0];

				f[u][1] += f[s[u].tr[k]][1];

			}

		}

	}

	return;

}

inline void solve(ll t,ll k)

{

	register int cur = root;

	if(k > f[root][t])

	{

		puts("-1");

		return;

	}

	while(true)

	{

		if(k == 0)break;

		for(register int i = 0;i < 26;++i)

		{

			if(s[cur].tr[i] != 0 && k <= f[s[cur].tr[i]][t])

			{

				putchar(i + 'a');

				cur = s[cur].tr[i];

				k -= siz[cur][t];

				break;

			}

			k -= f[s[cur].tr[i]][t];

		}

	}

	puts("");

	return;

}

int main()

{

	scanf("%s",str + 1);

	register int l = strlen(str + 1);

	for(register int i = 1;i <= l;++i)extend(str[i] - 'a');

	dp();

	register ll t,k;

	scanf("%lld%lld",&t,&k);

	solve(t,k);

	return 0;

}