前几天写的题，今天补写个blog
T的情况get right集合的时候特判一下。
因为SAM就是有序的，所以可以dfs求解。
把parent树构建出来，sum表示当前子树的right和，搜一下就出来了。
upd:第二次写这个题，搜索的时候记得减去right[now]
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int len,a[1100000]; struct node { int w[30]; }ch[1100000];int root,last,cnt; int dep[1100000],parent[1100000]; void add(int k) { int x=a[k]; int now=++cnt,p=last; dep[now]=k; while(p!=0&&ch[p].w[x]==0)ch[p].w[x]=now,p=parent[p]; if(p==0)parent[now]=root; else { int pre=ch[p].w[x]; if(dep[p]+1==dep[pre])parent[now]=pre; else { int npre=++cnt; ch[npre]=ch[pre]; dep[npre]=dep[p]+1; parent[npre]=parent[pre]; parent[now]=parent[pre]=npre; while(ch[p].w[x]==pre)ch[p].w[x]=npre,p=parent[p]; } } last=now; } int Rsort[1100000],sa[1100000]; int Right[1100000]; void get_Right(int T) { for(int i=1;i<=cnt;i++)Rsort[dep[i]]++; for(int i=1;i<=len;i++)Rsort[i]+=Rsort[i-1]; for(int i=cnt;i>=1;i--)sa[Rsort[dep[i]]--]=i; int now=root; for(int i=1;i<=len;i++) { int x=a[i]; now=ch[now].w[x]; Right[now]++; } for(int i=cnt;i>=1;i--) { if(T==1) Right[parent[sa[i]]]+=Right[sa[i]]; else Right[sa[i]]=1; } Right[root]=0; } int T,k; int sum[1100000]; void dfs(int now) { if(k<=Right[now])return ; k-=Right[now]; for(int x=1;x<=26;x++) { if(ch[now].w[x]!=0) { int next=ch[now].w[x]; if(k>sum[next])k-=sum[next]; else { printf("%c",x+'a'-1); dfs(next); return ; } } } } char ss[1100000]; int main() { scanf("%s",ss+1);len=strlen(ss+1); for(int i=1;i<=len;i++)a[i]=ss[i]-'a'+1; root=last=cnt=1; for(int i=1;i<=len;i++)add(i); scanf("%d%d",&T,&k); get_Right(T); for(int i=cnt;i>=1;i--) { int now=sa[i];sum[now]=Right[now]; for(int x=1;x<=26;x++) if(ch[now].w[x]!=0)sum[now]+=sum[ch[now].w[x]]; } if(k>sum[root])printf("-1 "); else dfs(root); return 0; }
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int a[510000],len; struct SAM { int w[30],dep,fail; }ch[1100000];int last,cnt; void insert(int dep,int x) { int pre=last,now=++cnt; ch[now].dep=dep; last=now; while(pre!=0&&ch[pre].w[x]==0) ch[pre].w[x]=now, pre=ch[pre].fail; if(pre==0)ch[now].fail=1; else { int nxt=ch[pre].w[x]; if(ch[nxt].dep==ch[pre].dep+1)ch[now].fail=nxt; else { int nnxt=++cnt; ch[nnxt]=ch[nxt]; ch[nnxt].dep=ch[pre].dep+1; ch[nxt].fail=ch[now].fail=nnxt; while(pre!=0&&ch[pre].w[x]==nxt) ch[pre].w[x]=nnxt, pre=ch[pre].fail; } } } //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~init~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int T,Right[1100000];//根到当前节点组成的子串出现次数 int Rsort[1100000],sa[1100000]; void GetRight() { memset(Rsort,0,sizeof(Rsort)); for(int i=1;i<=cnt;i++)Rsort[ch[i].dep]++; for(int i=1;i<=len;i++)Rsort[i]+=Rsort[i-1]; for(int i=cnt;i>=1;i--)sa[Rsort[ch[i].dep]--]=i; int now=1; memset(Right,0,sizeof(Right)); for(int i=1;i<=len;i++) now=ch[now].w[a[i]], Right[now]++; for(int i=cnt;i>=1;i--) { int u=sa[i],v=ch[u].fail; if(T==0)Right[u]=1; else Right[v]+=Right[u]; } Right[1]=0; } int sum[1100000];//以根到当前节点为前缀的子串个数 void GetSum() { for(int i=cnt;i>=1;i--) { int now=sa[i];sum[now]=Right[now]; for(int x=1;x<=26;x++) if(ch[now].w[x]!=0)sum[now]+=sum[ch[now].w[x]]; } } //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //------------------------------------------------------SAM----------------------------------------------------------------- int K; void dfs(int now) { if(K==Right[now])return ; K-=Right[now]; for(int x=1;x<=26;x++) if(ch[now].w[x]!=0) { if(sum[ch[now].w[x]]>=K) { printf("%c",x+'a'-1); dfs(ch[now].w[x]); return ; } else K-=sum[ch[now].w[x]]; } } //-----------------------------------------------------solve---------------------------------------------------------------- char ss[510000]; int main() { scanf("%s%d%d",ss+1,&T,&K); last=cnt=1; len=strlen(ss+1); for(int i=1;i<=len;i++) a[i]=ss[i]-'a'+1, insert(i,a[i]); GetRight(); GetSum(); if(K>sum[1])printf("-1 "); else dfs(1); return 0; }