【BZOJ3998】【TJOI2015】弦论 后缀自动机

链接:

#include <stdio.h>
int main()
{
puts("转载请注明出处[vmurder]谢谢");
puts("网址:blog.csdn.net/vmurder/article/details/45369569");
}

题解:

首先我们可以建1个后缀自动机。
然后每条路径走到每一个点都是1个串,它们是有字典序的。
我们只需要统计出往每一个点走以后都有多少串就行了。
fi=(fson)+numi
对不计重复的情况下,numi=1
对计算重复的情况下,每一个节点都有多种走到最后的方式,numi 就是看有这个种数。
比如 ababababa 这个串最后可以走成 ababababab 。因而 num 是2。
初值是所有 npnum=1 ,然后 numi=numson

f 处理出来以后,就随意弄了。
每次往下走就好了,类似26分? (雾
无妨看我的 dfs 函数。

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1001000
#define T 26
#define inf 0x3f3f3f3f
using namespace std;
struct SAM
{
int son[N][T],pa[N],dep[N],last,cnt;
int val[N],f[N];
void init(){last=cnt=1;}
int newnode(int p){dep[++cnt]=dep[p]+1;return cnt;}
void add(int x)
{
int p=last;
int np=newnode(p);
while(p&&!son[p][x])son[p][x]=np,p=pa[p];
if(!p)pa[np]=1;
else {
int q=son[p][x];
if(dep[q]==dep[p]+1)pa[np]=q;
else {
int nq=newnode(p);
pa[nq]=pa[q],pa[q]=pa[np]=nq;
memcpy(son[nq],son[q],sizeof son[q]);
while(p&&son[p][x]==q)son[p][x]=nq,p=pa[p];
}
}
val[last=np]=1;
}
int d[N],stk[N],top;
struct Eli
{
int v,next;
}e[N*T/5];
int head[N],ct;
void add(int u,int v)
{
d[v]++;
e[++ct].v=v;
e[ct].next=head[u];
head[u]=ct;
}
void bfsf()
{
int i,j,u,v;
for(i=1;i<=cnt;i++)for(j=0;j<T;j++)if(son[i][j])
add(son[i][j],i);
for(i=1;i<=cnt;i++)if(!d[i])stk[++top]=i;
while(top)
{
u=stk[top--],f[u]++,val[u]=1;
for(i=head[u];i;i=e[i].next)
{
v=e[i].v,f[v]+=f[u];
if(!--d[v])stk[++top]=v;
}
}
f[1]--;
}
void bfsg()
{
int i,j,u,v;
for(i=2;i<=cnt;i++)d[pa[i]]++;
for(i=1;i<=cnt;i++)if(!d[i])stk[++top]=i;
while(top)
{
u=stk[top--];
val[pa[u]]+=val[u];
if(!--d[pa[u]])stk[++top]=pa[u];
}
for(i=1;i<=cnt;i++)for(j=0;j<T;j++)
if(son[i][j])add(son[i][j],i);
for(i=1;i<=cnt;i++)if(!d[i])stk[++top]=i;
while(top)
{
u=stk[top--],f[u]+=val[u];
for(i=head[u];i;i=e[i].next)
{
v=e[i].v,f[v]+=f[u];
if(!--d[v])stk[++top]=v;
}
}
f[1]-=val[1];
}
void dfs(int x,int k)
{
int i,v;
for(i=0;i<T;i++)if(v=son[x][i])
{
if(k<=f[v])
{
printf("%c",'a'+i);
k-=val[v];
if(k>0)dfs(v,k);
return ;
}
else k-=f[v];
}
}
}sam;
char s[N/2];
int main()
{
freopen("test.in","r",stdin);
int i,j,k;

scanf("%s",s+1);
sam.init();
for(i=1;s[i];i++)sam.add(s[i]-'a');
scanf("%d%d",&j,&k);
if(j==0)sam.bfsf();
else sam.bfsg();
sam.dfs(1,k);
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 【BZOJ3998】【TJOI2015】弦论 后缀自动机

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡