5
18
2016
0

[BZOJ3998] [TJOI2015]弦论

第一次写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;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 583

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com