题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3998
题意概述：对于一个给定长度为N的字符串，求它的第K小子串是什么，T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。N<=500000,K<=10^9.
应该是有三种做法的（当然后缀树我还没有看），于是就把这个东西当成后缀自动机的板子了（因为它很裸啊！！！）。
可以注意到当T=0的时候每走动一步的贡献是1，而T=1的时候每走动一步之后的贡献都是走到的这个状态的right集合大小。同时从同一个状态走出去得到的字符串又有很多种，不难想到可以搞个dp表示从这个点出发（包括这个点自己）可以找到的不同子串数（根据T而定）。
有个技巧是根据MAX把所有的状态排序之后就可以欢快地topo图上转移dp啦！（SAM的转移图是一张DAG）
所以还是好好理解一下SAM上的状态和转移吧，，，。。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
using namespace std;
const int MAXN=; int T,K,n; char S[MAXN]; struct SAM{
static const int maxn=;
static const int sigma_sz=;
int pa[maxn<<],to[maxn<<][sigma_sz],mx[maxn<<],val[maxn<<]; long long cnt[maxn<<];
int sz,last,c[maxn],a[maxn<<];
SAM(){ last=sz=; memset(to[],,sizeof(to[])); }
int newnode(){
memset(to[++sz],,sizeof(to[sz]));
pa[sz]=mx[sz]=val[sz]=cnt[sz]=;
return sz;
}
void extend(int w){
int p=last,np=newnode(); last=np;
pa[np]=mx[np]=cnt[np]=;
mx[np]=mx[p]+,val[np]=;
while(p&&!to[p][w]) to[p][w]=np,p=pa[p];
if(!p) pa[np]=;
else{
int q=to[p][w];
if(mx[p]+==mx[q]) pa[np]=q;
else{
int nq=newnode(); mx[nq]=mx[p]+;
memcpy(to[nq],to[q],sizeof(to[nq]));
pa[nq]=pa[q];
pa[np]=pa[q]=nq;
while(p&&to[p][w]==q) to[p][w]=nq,p=pa[p];
}
}
}
void ready(){
for(int i=;i<=sz;i++) c[mx[i]]++;
for(int i=;i<=n;i++) c[i]+=c[i-];
for(int i=sz;i>;i--) a[c[mx[i]]--]=i;
for(int i=sz;i>;i--){
if(T) val[pa[a[i]]]+=val[a[i]];
else val[a[i]]=;
}
val[]=;
for(int i=sz;i>;i--){
cnt[a[i]]=val[a[i]];
for(int j=;j<;j++) cnt[a[i]]+=cnt[to[a[i]][j]];
}
}
void dfs(int i){
if(val[i]>=K) return;
K-=val[i];
for(int j=;j<;j++) if(to[i][j]){
if(cnt[to[i][j]]>=K){
putchar(j+'a'); dfs(to[i][j]);
return;
}
K-=cnt[to[i][j]];
}
}
}sam; void data_in()
{
gets(S);
scanf("%d%d",&T,&K);
}
void work()
{
n=strlen(S);
for(int i=;i<n;i++) sam.extend(S[i]-'a');
sam.ready();
if(sam.cnt[]<K) printf("%d\n",-);
else sam.dfs();
}
int main()
{
data_in();
work();
return ;
}