这道题用后缀数组貌似会T。
后缀自动机做法：
t==0:第k小的本质不同字串
首先把后缀自动机建出来，我们会得到一个DAG，并且只存在一个点入度为0（我们称之为根），可以证明字符串的任意一个本质不同的子串（不包括空串）与该自动机上一条起点为根的长度（路径边数）大于0的路径一一对应。所以我们就可以进行DP了，dp[u]表示以u为起点的串的个数，然后有点像在BST中找第k小的思想。
t==1:第k小的普通字串（不同位置但本质相同的要区分）
还是要dp，我yy的一个状态含义是：dp[u]表示，u节点的对应的后缀（right集合中每个位置对应一个后缀）的所有前缀的个数（空串也是前缀，并且不同位置的空串相互区分）。
这样，我们就默认一个长度为n的字符串有(n+1)*(n+2)/2个子串（包括n+1个空串）。
/**************************************************************
Problem: 3998
User: idy002
Language: C++
Result: Accepted
Time:9736 ms
Memory:134596 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#define N 1000010 typedef long long dnt; int n, k, t;
int son[N][], val[N], pnt[N], rsiz[N], ntot, last;
int idgr[N], stk[N], qu[N], bg, ed, top;
dnt dp[N];
char str[N]; void init() {
ntot = ;
pnt[] = -;
}
void append( int c ) {
int p = last;
int np = ++ntot;
val[np] = val[last]+;
while( ~p && !son[p][c] )
son[p][c]=np,p=pnt[p];
if( p==- ) {
pnt[np] = ;
} else {
int q = son[p][c];
if( val[q]==val[p]+ ) {
pnt[np] = q;
} else {
int nq = ++ntot;
memcpy( son[nq], son[q], sizeof(son[nq]) );
val[nq] = val[p]+;
rsiz[nq] = rsiz[q];
pnt[nq] = pnt[q];
pnt[q] = pnt[np] = nq;
while( ~p && son[p][c]==q ) son[p][c]=nq,p=pnt[p];
}
}
last = np;
while( ~np ) {
rsiz[np]++;
np = pnt[np];
}
}
void print() {
for( int u=; u<=ntot; u++ ) {
fprintf( stderr, "%d(dp[%d]=%lld rsiz[%d]=%d): ", u, u, dp[u], u, rsiz[u] );
for( int c=; c<; c++ ) {
int v=son[u][c];
if( !v ) continue;
fprintf( stderr, "%c,%d ", c+'a', v );
}
fprintf( stderr, "\n" );
}
}
void make_topo() {
for( int u=; u<=ntot; u++ ) {
for( int c=; c<; c++ ) {
int v=son[u][c];
if( !v ) continue;
idgr[v]++;
}
}
top = ;
for( int u=; u<=ntot; u++ )
if( idgr[u]== )
stk[++top] = u;
bg = , ed = ;
while( top ) {
int u=stk[top--];
qu[++ed] = u;
for( int c=; c<; c++ ) {
int v=son[u][c];
if( !v ) continue;
idgr[v]--;
if( idgr[v]== )
stk[++top] = v;
}
}
}
void dodp( int s ) {
make_topo();
rsiz[s] = ;
if( t== )
for( int i=; i<=ed; i++ )
rsiz[qu[i]] = ;
for( int i=ed; i>=; i-- ) {
int u=qu[i];
dp[u] = rsiz[u];
for( int c=; c<; c++ ) {
int v=son[u][c];
if( !v ) continue;
dp[u] += dp[v];
}
}
if( dp[]<k ) {
printf( "-1\n" );
return;
}
int u = ;
int kth = k;
while() {
if( kth<=rsiz[u] ) {
printf( "\n" );
return;
} else kth-=rsiz[u];
for( int c=; c<; c++ ) {
int v=son[u][c];
if( !v ) continue;
if( dp[v]>=kth ) {
u = v;
printf( "%c", c+'a' );
break;
} else {
kth -= dp[v];
}
}
}
}
int main() {
scanf( "%s", str );
scanf( "%d%d", &t, &k );
init();
for( int i=; str[i]; i++ )
append( str[i]-'a' );
dodp();
// print();
}