链接：
#include <stdio.h>
@H_301_7@int main()
{
puts("转载请注明出处[vmurder]谢谢");
puts("网址：blog.csdn.net/vmurder/article/details/45369569");
}题解：
首先我们可以建1个后缀自动机。
然后每条路径走到每一个点都是1个串，它们是有字典序的。
我们只需要统计出往每一个点走以后都有多少串就行了。
对不计重复的情况下，
对计算重复的情况下，每一个节点都有多种走到最后的方式，
比如
初值是所有
每次往下走就好了，类似26分? (雾
无妨看我的
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1001000
#define T 26
#define inf 0x3f3f3f3f
@H_301_7@using @H_301_7@namespace std;
@H_301_7@struct SAM
{
@H_301_7@int son[N][T],pa[N],dep[N],last,cnt;
@H_301_7@int val[N],f[N];
@H_301_7@void init(){last=cnt=1;}
@H_301_7@int newnode(@H_301_7@int p){dep[++cnt]=dep[p]+1;@H_301_7@return cnt;}
@H_301_7@void add(@H_301_7@int x)
{
@H_301_7@int p=last;
@H_301_7@int np=newnode(p);
@H_301_7@while(p&&!son[p][x])son[p][x]=np,p=pa[p];
@H_301_7@if(!p)pa[np]=1;
@H_301_7@else {
@H_301_7@int q=son[p][x];
@H_301_7@if(dep[q]==dep[p]+1)pa[np]=q;
@H_301_7@else {
@H_301_7@int nq=newnode(p);
pa[nq]=pa[q],pa[q]=pa[np]=nq;
memcpy(son[nq],son[q],@H_301_7@sizeof son[q]);
@H_301_7@while(p&&son[p][x]==q)son[p][x]=nq,p=pa[p];
}
}
val[last=np]=1;
}
@H_301_7@int d[N],stk[N],top;
@H_301_7@struct Eli
{
@H_301_7@int v,next;
}e[N*T/5];
@H_301_7@int head[N],ct;
@H_301_7@void add(@H_301_7@int u,@H_301_7@int v)
{
d[v]++;
e[++ct].v=v;
e[ct].next=head[u];
head[u]=ct;
}
@H_301_7@void bfsf()
{
@H_301_7@int i,j,u,v;
@H_301_7@for(i=1;i<=cnt;i++)@H_301_7@for(j=0;j<T;j++)@H_301_7@if(son[i][j])
add(son[i][j],i);
@H_301_7@for(i=1;i<=cnt;i++)@H_301_7@if(!d[i])stk[++top]=i;
@H_301_7@while(top)
{
u=stk[top--],f[u]++,val[u]=1;
@H_301_7@for(i=head[u];i;i=e[i].next)
{
v=e[i].v,f[v]+=f[u];
@H_301_7@if(!--d[v])stk[++top]=v;
}
}
f[1]--;
}
@H_301_7@void bfsg()
{
@H_301_7@int i,v;
@H_301_7@for(i=2;i<=cnt;i++)d[pa[i]]++;
@H_301_7@for(i=1;i<=cnt;i++)@H_301_7@if(!d[i])stk[++top]=i;
@H_301_7@while(top)
{
u=stk[top--];
val[pa[u]]+=val[u];
@H_301_7@if(!--d[pa[u]])stk[++top]=pa[u];
}
@H_301_7@for(i=1;i<=cnt;i++)@H_301_7@for(j=0;j<T;j++)
@H_301_7@if(son[i][j])add(son[i][j],f[u]+=val[u];
@H_301_7@for(i=head[u];i;i=e[i].next)
{
v=e[i].v,f[v]+=f[u];
@H_301_7@if(!--d[v])stk[++top]=v;
}
}
f[1]-=val[1];
}
@H_301_7@void dfs(@H_301_7@int x,@H_301_7@int k)
{
@H_301_7@int i,v;
@H_301_7@for(i=0;i<T;i++)@H_301_7@if(v=son[x][i])
{
@H_301_7@if(k<=f[v])
{
printf("%c",'a'+i);
k-=val[v];
@H_301_7@if(k>0)dfs(v,k);
@H_301_7@return ;
}
@H_301_7@else k-=f[v];
}
}
}sam;
@H_301_7@char s[N/2];
@H_301_7@int main()
{
freopen("test.in","r",stdin);
@H_301_7@int i,k;
scanf("%s",s+1);
sam.init();
@H_301_7@for(i=1;s[i];i++)sam.add(s[i]-'a');
scanf("%d%d",&j,&k);
@H_301_7@if(j==0)sam.bfsf();
@H_301_7@else sam.bfsg();
sam.dfs(1,k);
@H_301_7@return 0;
}
