第一次写SAM，遵循nixy大爷的教导来写这道题
据说是一个裸的SAM，然后我仔细观(抄)察(写)了这道题目的代码
感觉SAM很难理解啊，熟练运用就更难了
觉得fhq博客里面对于SAM的理解写的非常好，推荐一下
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N=1000005;
int t,k,len,root,cnt,last,a[N],b[N];
char s[N];
struct SAM{
int next[26],fa,mx,sum,val;
}sam[N];
int Newnode(int x){
sam[++cnt].mx=x;
return cnt;
}
void Extend(int x){
int np=Newnode(sam[last].mx+1),p=last;
sam[np].val=1;last=np;
for(;p && !sam[p].next[x];p=sam[p].fa)sam[p].next[x]=np;
if(!p){sam[np].fa=root;return;}
int q=sam[p].next[x];
if(sam[q].mx==sam[p].mx+1){sam[np].fa=q;return;}
int nq=Newnode(sam[p].mx+1);
sam[nq].fa=sam[q].fa;
sam[q].fa=sam[np].fa=nq;
memcpy(sam[nq].next,sam[q].next,sizeof(sam[q].next));
for(;p && sam[p].next[x]==q;p=sam[p].fa)sam[p].next[x]=nq;
}
void Toposort(){
for(int i=1;i<=len;i++)b[i]=0;
for(int i=1;i<=cnt;i++)b[sam[i].mx]++;
for(int i=1;i<=len;i++)b[i]+=b[i-1];
for(int i=cnt;i;i--)a[b[sam[i].mx]--]=i;
if(t==1)for(int i=cnt;i;i--)sam[sam[a[i]].fa].val+=sam[a[i]].val;
else for(int i=cnt;i;i--)sam[sam[a[i]].fa].val=1;
sam[root].val=0;
for(int i=cnt;i;i--){
sam[a[i]].sum=sam[a[i]].val;
for(int j=0;j<26;j++)sam[a[i]].sum+=sam[sam[a[i]].next[j]].sum;
}
}
void dfs(int rt,int k){
if(k<=sam[rt].val)return;
k-=sam[rt].val;
for(int i=0;i<26;i++){
if(k<=sam[sam[rt].next[i]].sum){putchar(i+'a');dfs(sam[rt].next[i],k);return;}
k-=sam[sam[rt].next[i]].sum;
}
}
int main(){
freopen("3998.in","r",stdin);
freopen("3998.out","w",stdout);
scanf("%s %d %d",s,&t,&k);
len=strlen(s);
last=root=Newnode(0);
for(int i=0;i<len;i++)Extend(s[i]-'a');
Toposort();
if(k>sam[root].sum)puts("-1");
else dfs(root,k);
return 0;
}
评论 (0)
