又领悟到了一点新的东西，后缀自动机其实可以分为两个数据结构，一个是后缀树，还有一个是自动机
后缀树用来划分endpos集合，并且维护后缀之间的关系，此时每个结点代表的是一些后缀相同且长度连续的子串
自动机用来处理边的转移，或者用来解决串的匹配问题，此时每个结点代表的只是一个串，这个串等于从root开始到这结点经过的路径，由于路径可能有很多条，所以对应到后缀树上，就是有一段连续的串啦
字典序第k小的串刚好可以用SAM的性质解决
/* 题目要求考虑两种情况： 首先来考虑算重复子串的情况 处理后缀树：先求出每个状态endpos的大小(即这个状态代表的所有串出现的次数)size[i]（endpos的大小即该状态的后缀子树的大小，所有的前缀结点贡献为1，克隆结点大小为0） 处理自动机：自底向上求出从每个状态出发能形成的子串个数 sum[i]+=sum{sum[j]} ,初始有sum[i]=size[i](即从这种状态开始有多少不同的子串,当然这种状态本身的方案数也算) 最后以root为起点，在自动机上进行搜索即可，具体搜索方式类似于多叉树(DAG)查询 然后来考虑不算重复子串的情况 处理后缀树：求endpos的大小 处理自动机：自底向上求每个状态出发能形成的子串个数sum[i]=sum{sum[j]} 初始有sum[i]=1,即这个状态的每个串认为只出现一次 再换一种思路：其实只要维护处每个状态作为起点的不同路径数即可 搜索过程不变 */ #include<bits/stdc++.h> using namespace std; #define maxn 500005 long long T,K; char s[maxn]; struct SAM{ int last,cnt; int nxt[maxn<<1][26]; int len[maxn<<1]; int link[maxn<<1]; int size[maxn<<1]; long long sum[maxn<<1];//sum[i]表示从状态i开始的子串总数 SAM(){ last=cnt=1; } void add(int c){ int p=last,np=last=++cnt; len[np]=len[p]+1; size[np]=1; for(;p&&!nxt[p][c];p=link[p]) nxt[p][c]=np; if(!p){link[np]=1;return;} int q=nxt[p][c]; if(len[q]==len[p]+1){link[np]=q;return;} int clone=++cnt; link[clone]=link[q]; len[clone]=len[p]+1; memcpy(nxt[clone],nxt[q],sizeof nxt[q]); link[q]=link[np]=clone; for(;p&&nxt[p][c]==q;p=link[p]) nxt[p][c]=clone; } int id[maxn<<1],t[maxn<<1]; void sort(){ for(int i=1;i<=cnt;i++)t[len[i]]++; for(int i=1;i<=cnt;i++)t[i]+=t[i-1]; for(int i=1;i<=cnt;i++)id[t[len[i]]--]=i; } void work(){//求子串的总数 //处理后缀树上的endpos for(int i=cnt;i>=1;i--) size[link[id[i]]]+=size[id[i]]; for(int i=1;i<=cnt;i++) if(T==0)sum[i]=size[i]=1;//要求去重，每个状态代表的串只统计一次 else sum[i]=size[i]; size[1]=sum[1]=0; //自底向上处理自动机 for(int i=cnt;i>=1;i--) for(int j=0;j<26;j++) if(nxt[id[i]][j]) sum[id[i]]+=sum[nxt[id[i]][j]]; } }p; void print(long long now,long long k){ if(k<=p.size[now])return;//如果这个结点代表的串也不能走完，返回 k-=p.size[now]; for(int i=0;i<26;i++){ int tmp=p.nxt[now][i]; if(!tmp)continue; if(k>p.sum[tmp]){ k-=p.sum[tmp]; continue; } putchar(i+'a');//沿着这个状态往下搜 print(tmp,k); return; } } int main(){ scanf("%s%lld%lld",s,&T,&K); int len=strlen(s); for(int i=0;i<len;i++) p.add(s[i]-'a'); p.sort(); p.work(); if(p.sum[1]<K)printf("-1"); else print(1,K); puts(""); }