好像是个经典问题，然而我没做过
建SAM，然后经过每个节点的子串数目就可以求了，多个相同子串算一个的话就把所有siz都搞成$1$，否则就是$right$集合的大小，然后就是常见的递推
求第$k$小是从根节点出发按字典序沿着trans往下走，每次输出对应的字符然后扣掉对应的数量
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=;
int fth[M],trs[M][],len[M],siz[M];
int rnk[M],bkt[M]; long long sum[M];
int typ,kth,lth,lst,tot;
char str[N];
void Insert(int ch)
{
int nde=lst,newn=++tot; lst=newn;
siz[newn]=,len[newn]=len[nde]+;
while(nde&&!trs[nde][ch])
trs[nde][ch]=newn,nde=fth[nde];
if(!nde)
fth[newn]=;
else
{
int tran=trs[nde][ch];
if(len[tran]==len[nde]+)
fth[newn]=tran;
else
{
int rnde=++tot; len[rnde]=len[nde]+;
for(int i=;i<=;i++) trs[rnde][i]=trs[tran][i];
fth[rnde]=fth[tran],fth[tran]=fth[newn]=rnde;
while(nde&&trs[nde][ch]==tran)
trs[nde][ch]=rnde,nde=fth[nde];
}
}
}
int main()
{
register int i,j,k;
scanf("%s%d%d",str+,&typ,&kth);
lth=strlen(str+),lst=tot=;
for(i=;i<=lth;i++) Insert(str[i]-'a');
for(i=;i<=tot;i++) bkt[len[i]]++;
for(i=;i<=lth;i++) bkt[i]+=bkt[i-];
for(i=;i<=tot;i++) rnk[bkt[len[i]]--]=i;
for(i=tot;i;i--)
j=rnk[i],typ?siz[fth[j]]+=siz[j]:siz[j]=;
siz[]=;
for(i=tot;i;i--)
{
j=rnk[i],sum[j]=siz[j];
for(k=;k<=;k++)
if(trs[j][k]) sum[j]+=sum[trs[j][k]];
}
if(kth>sum[]) printf("-1");
else
{
int nde=;
while(kth-siz[nde]>)
{
kth-=siz[nde];
for(i=;i<=&&kth>sum[trs[nde][i]];i++)
kth-=sum[trs[nde][i]];
nde=trs[nde][i],printf("%c",i+'a');
}
}
return ;
}