fjwc2019 D1T2 原样输出(后缀自动机+dp)
2024-09-02 03:18:26
暴力对每个串建后缀自动机,然后暴力枚举每个自动机的子串。可以拿到部分分。
然鹅我们可以把每个后缀自动机连起来。
我们知道,后缀自动机是用最少的点(空间)表示出一个串的所有子串。
那么我们为啥不在后缀自动机上直接跑dp呢?于是我们把它们连起来。
复制一段ppt:
可以怎么拼呢?
我们考虑如何判断一个字符串是否是可能的输出文件
显然我们可以贪心地匹配,每次拿起一个输入串,一直匹配到不能再加字符了才放下,这样一定是正确的
于是我们可以告诉自动机如果失配了要往哪走
比如有一个节点没有C的转移边,那么就要向之后第一个包含字符C的字符串的后缀自动机接受字符串C的节点连一条C的转移边
当然如果这样的字符串不存在就不需要连边
把自动机建起来后
对于$k=1$的情况,直接dfs搞定
但是面对大数据,dfs显然是会TLE的鸭
但是仔细一看
对于 100% 的数据,保证输入文件大小不超过 1MB ,保证输出文件大小不超过 200MB 。
显然大数据的$k=0$,否则输出文件就超过限制了。
于是我们在新图上跑个$dp$就行辣
#include<cstdio>
#include<iostream>
using namespace std;
#define N 10000005
const int mod=1e9+;
char fr1[]={'A','C','G','T'},s[N];
int n,k,fr2[],now[N],st[N],tp,ans;
int nxt[N][],fa[N],len[N],ed,last,rt[N],f[N];
void dfs(int tp,int x){//k=1时用dfs找每个子串并输出
st[tp]=x; puts(s+); ++ans;
for(;now[tp]<;++now[tp]){
if(nxt[x][now[tp]]){
s[tp+]=fr1[now[tp]];
now[tp+]=;
dfs(tp+,nxt[x][now[tp]]);
s[tp+]=;
}
}
}
void dp(int tp,int x){//k=0时直接dp,应对大数据
if(f[x]>) return;
f[x]=;
for(;now[tp]<;++now[tp]){
if(nxt[x][now[tp]]){
dp(tp+,nxt[x][now[tp]]);
now[tp+]=;
f[x]=(f[x]+f[nxt[x][now[tp]]])%mod;
}
}
}
struct sam{//裸裸的后缀自动机
void init(int x){
last=rt[x]=++ed; char c=getchar();
while(c<'A'||'T'<c) c=getchar();
while(c!='\n') add(fr2[c],x),c=getchar();
}
void add(int c,int x){
int q,p=last; len[last=++ed]=len[p]+;
for(;p&&!nxt[p][c];p=fa[p]) nxt[p][c]=ed;
if(!p) fa[ed]=rt[x];
else{
q=nxt[p][c];
if(len[q]==len[p]+) fa[ed]=q;
else{
len[++ed]=len[p]+;
for(int k=;k<;++k) nxt[ed][k]=nxt[q][k];
fa[ed]=fa[q]; fa[q]=fa[ed-]=ed;
for(;nxt[p][c]==q;p=fa[p]) nxt[p][c]=ed;
}
}
}
}S; int main(){
freopen("copy.in","r",stdin);
freopen("copy.out","w",stdout);
fr2['A']=;fr2['C']=;fr2['G']=;fr2['T']=;
scanf("%d",&n);
for(int i=;i<=n;++i) S.init(i);
for(int i=n-;i;--i)
for(int j=rt[i];j!=rt[i+];++j)
for(int c=;c<;++c)
if(!nxt[j][c]) nxt[j][c]=nxt[rt[i+]][c];//贪心连边
scanf("%d",&k);
if(k) dfs(,rt[]),printf("%d",ans);
else dp(,rt[]),printf("%d",f[rt[]]);
return ;
}
最新文章
- 机器学习之K-近邻算法
- 最短路径问题的Dijkstra和SPFA算法总结
- PopuWindow_1
- setsockopt的作用列表
- javascript中ajax post实例详解
- YAR 并行RPC框架研究
- 采用thinkphp框架实现添加管理员功能
- 在Eclipse中安装spket插件
- synchronized和vilatile
- STM32的优先级NVIC_PriorityGroupConfig
- angular js 和 dajango 标签{{}} 冲突
- java面试之Hashmap
- 日历类和日期类转换 并发修改异常 泛型的好处 *各种排序 成员和局部变量 接口和抽象类 多态 new对象内存中的变化
- P1525 关押罪犯
- Win8驱动的兼容性问题
- Linux内核分析——进程的切换和系统的一般执行过程
- 视角同步NewViewTarget
- SD从零开始15-18
- LINUX下动态链接库的使用-dlopen dlsym dlclose dlerror(转)
- Same Tree,判断两个二叉树是不是相同的树,结构相同,每个节点的值相同
热门文章
- 【LeetCode每天一题】Remove Element(移除指定的元素)
- 使用Pyinstaller打包python py文件注意事项
- [LeetCode] 566. Reshape the Matrix_Easy
- .Net Core资源
- Xcode 常用命令
- iOS 新浪微博-4.0 OAuth授权
- python list成员函数extend与append的区别
- Git操作说明
- 46.HTML---18个学习 flexbox 的优质资源
- 关于c语言中的program_invocation_short_name