题目链接
分析： SAM S A M 求第 K K 大子串
首先我们建出SAMSAM 假如我们把 SAM S A M 变成一棵 dfs d f s 树 那么每一个结点（代表一个状态）后面都跟着一棵子树， 我们就假设这个结点的状态是 S S ，那么子树中的每一个结点代表的子串一定有SS的前缀
如果我们已经确定了第 K K 个子串的前缀是SS，我们需要确定下一个字符 那么我们就需要知道每个状态后面的子树大小： sumi s u m i 这样我们就可以从小到大枚举当前字符， 如果 sumi>=K s u m i >= K ，说明下一位的字符就是 i i 如果sumi<Ksumi<K，说明下一位的字符肯定大于 i i ，所以K−=sumiK−=sumi，继续向下枚举
那么 sum s u m 数组怎么确定呢 其实很简单，以为在 SAM S A M 上不同的状态仅出现一次，这恰好符合题目要求 所以初始值 sumi=1(sumroot=0) s u m i = 1 ( s u m r o o t = 0 ) sumi=∑sumson s u m i = ∑ s u m s o n
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int N=90005; int ch[N<<1][26],dis[N<<1],sum[N<<1],fa[N<<1],root=1,sz=1,last=1,len; int c[N],pos[N],size[N<<1]; char s[N]; void insert(int x) { int now=++sz,pre=last; last=now; size[now]=1; dis[now]=dis[pre]+1; for (;pre&&!ch[pre][x];pre=fa[pre]) ch[pre][x]=now; if (!pre) fa[now]=root; else { int q=ch[pre][x]; if (dis[q]==dis[pre]+1) fa[now]=q; else { int nows=++sz; dis[nows]=dis[pre]+1; memcpy(ch[nows],ch[q],sizeof(ch[q])); fa[nows]=fa[q]; fa[q]=fa[now]=nows; for (;pre&&ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows; } } } void solve(int K) { int now=root; while ((K-=size[now])>0) { int x=0; while (K>sum[ch[now][x]]&&x<26) K-=sum[ch[now][x++]]; printf("%c",'a'+x); now=ch[now][x]; } printf("\n"); } int main() { scanf("%s",s+1); len=strlen(s+1); for (int i=1;i<=len;i++) insert(s[i]-'a'); int T; scanf("%d",&T); size[root]=0; for (int i=1;i<=sz;i++) c[dis[i]]++; for (int i=1;i<=len;i++) c[i]+=c[i-1]; for (int i=1;i<=sz;i++) pos[c[dis[i]]--]=i; for (int i=sz;i>=1;i--) { sum[pos[i]]=size[pos[i]]; for (int j=0;j<26;j++) if (ch[pos[i]][j]) sum[pos[i]]+=sum[ch[pos[i]][j]]; } while (T--) { int K; scanf("%d",&K); solve(K); } }