BZOJ
这题应该很简单 构建出 SAM 后 求出每个点往后还能构建出几个串 按照拓扑序 dp 一些就好了 然后就是第 k <script type="math/tex" id="MathJax-Element-39">k</script>大，随便搞一下就好
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<map> #include<vector> #include<queue> using namespace std; #define MAX 550000 #define ll long long inline int read() { int x=0,t=1;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t; } struct Node { int son[26]; int ff,len; }t[MAX<<1]; char ch[MAX]; int c[MAX<<1],a[MAX<<1],size[MAX<<1]; ll f[MAX<<1]; int last=1,tot=1,T,K; void extend(int c) { int p=last,np=++tot;last=np; t[np].len=t[p].len+1; while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].ff; if(!p)t[np].ff=1; else { int q=t[p].son[c]; if(t[q].len==t[p].len+1)t[np].ff=q; else { int nq=++tot; t[nq]=t[q]; t[nq].len=t[p].len+1; t[q].ff=t[np].ff=nq; while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].ff; } } size[np]=1; } void Query(int u,int K) { if(K<=size[u])return; K-=size[u]; for(int i=0;i<26;++i) { if(!t[u].son[i])continue; if(f[t[u].son[i]]<K)K-=f[t[u].son[i]]; else { putchar('a'+i); Query(t[u].son[i],K); return; } } } int main() { scanf("%s",ch+1); for(int i=1,l=strlen(ch+1);i<=l;++i)extend(ch[i]-97); T=read();K=read(); for(int i=1;i<=tot;++i)c[t[i].len]++; for(int i=1;i<=tot;++i)c[i]+=c[i-1]; for(int i=1;i<=tot;++i)a[c[t[i].len]--]=i; for(int i=tot;i;--i)size[t[a[i]].ff]+=size[a[i]]; for(int i=1;i<=tot;++i) if(T==0)f[i]=size[i]=1;else f[i]=size[i]; f[1]=size[1]=0; for(int i=tot;i;--i) for(int j=0;j<26;++j) if(t[a[i]].son[j]) f[a[i]]+=f[t[a[i]].son[j]]; if(K>f[1])puts("-1"); else Query(1,K),puts(""); return 0; }