给定一个长度为(n(nle 5 imes 10^5))的字符串，求它的第(k)小字串。有两种模式：
- (Type=0)，不同位置的相同字串只算一个
- (Type=1)，不同位置相同字串算多个
Sample Input
aabc
0 3
Sample Output
aab
分析
我们知道，后缀自动机的从小到大遍历可以按顺序得到字符串的所有子串，所以要得到第(k)小的字串，只要用类似线段树上二分的做法，记录每一个出去的边后面有多少个即可。记(val[i])为每个点的值，只要求一下(sum[i]=val[i]+sum _{trans(i,x)}sum[x])。对于两种不同的模式，我们对于(val)的设置不同。对于(type=0)，我们把每个点的(val)始终为1，对于(type=1)，初始时我们把(val)设为1，每次新加点的时候，把这个点的整条suffix-link上的点的(val)都加一，因为suffix-link代表的是后缀，形成了一个新的字符串后所有后缀的出现次数都增多了，由于一样的子串出现多次算多次，我们要给它算进去。最后dfs一下沿着路查找输出就好啦。很简单的题。
计算(sum)的时候，我用的方法是直接dfs一次，而这样会爆栈，所以我手工开栈了。还有一种方法，可以不需要dfs即可解决。我们知道，后缀自动机的(trans)组成了一个有向无环图，并且每个点代表的(len)与它们的拓扑序相符，而且(len)的大小不会超过(n)，所以我们可以直接对(len)进行一次基数排序，相当于完成了拓扑排序，再按照拓扑倒序更新(sum)值。这种方法完全不需要递归，就不需要手工开栈了。复杂度同样是(O(n))的。
代码
学一下手工开栈的方法。
更正：bzoj上提交不开栈也能过，因为系统是linux
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
using namespace std;
int read() {
int x=0,f=1;
char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int maxn=5e5+1;
const int maxc=26;
char s[maxn];
int sta[maxn<<2],top=0;
bool alr[maxn<<1];
struct SAM {
int t[maxn<<1][maxc],len[maxn<<1],link[maxn<<1],val[maxn<<1],sum[maxn<<1],last,tot;
SAM ():last(1),tot(1) {}
void add(int x,int T) {
int nw=++tot,i;
len[nw]=len[last]+1;
val[nw]=1;
for (i=last;i && !t[i][x];i=link[i]) t[i][x]=nw;
if (i) {
int p=t[i][x];
if (len[p]==len[i]+1) link[nw]=p; else {
int q=++tot;
val[q]=val[p];
len[q]=len[i]+1;
memcpy(t[q],t[p],sizeof t[p]);
for (int j=i;j && t[j][x]==p;j=link[j]) t[j][x]=q;
link[q]=link[p];
link[p]=link[nw]=q;
}
} else link[nw]=1;
if (T) for (int i=link[nw];i;i=link[i]) ++val[i];
last=nw;
}
void dfs(int x) {
sum[x]=val[x];
for (int i=0;i<maxc;++i) if (t[x][i]) {
int v=t[x][i];
if (!alr[v]) {
alr[v]=true;
dfs(v);
}
sum[x]+=sum[v];
}
}
bool run(int x,int k) {
if (!k) return false;
for (int i=0;i<maxc;++i) if (t[x][i]) {
int v=t[x][i];
if (k>sum[v]) k-=sum[v]; else {
putchar(i+'a');
return run(v,k-val[v]);
}
}
return true;
}
} sam;
int main() {
int size=128<<20;
char *p=size+(char*)malloc(size);
__asm__("movl %0, %%esp
" :: "r"(p));
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
freopen("my.out","w",stdout);
#endif
scanf("%s",s+1);
int n=strlen(s+1);
int T=read(),k=read();
for (int i=1;i<=n;++i) sam.add(s[i]-'a',T);
sam.dfs(1);
int ret=sam.run(1,k);
if (ret) puts("-1"); else puts("");
return 0;
}