AC自动机练习2：修改串
2024-08-31 20:59:45
这道题的话用到了dp，一个比较简单的dp方程
1466: 【AC自动机】修改串
时间限制: 1 Sec 内存限制: 128 MB
提交: 18 解决: 14
[提交] [状态] [讨论版] [命题人:admin]题目描述
【题意】
给出n个模式串，然后给出一个修改串，求尽量少修改修改串，使得修改串不含有任何一个模式串，不能的话输出-1
每个串只有'A','C','G','T'四个字母
【输入格式】
有多组数据，输入以一个0结束
每组数据：
输入一个n(n<=50)
接下来n行输入n个模式串（每个模式串长度不超过20）
最后一行输入修改串（长度不超过1000）
【输出格式】
输出Case T: ans
T当前输出的是第T组数据，ans表示最少修改次数，不能修改则ans=-1
【样例输入】
2
AAA
AAG
AAAG
2
A
TG
TGAATG
4
A
G
C
T
AGT
0
【样例输出】
Case 1: 1
Case 2: 4
Case 3: -1
我第一眼看到这道题的时候，一度怀疑是模板题，然后定睛一看，没这么简单，应该我们在修改的时候要尽可能的找位置去修改更多的字符，所以这就意味这我们可能要用到最方便的继承状态的dp（当然作为一个dp盲人，我一开始是没有想到的，只有暴力才是王道），下面看一下讲解
说难的话就不能说特别难，只是有一些细节要弄清楚，
- 多组数据，一定要每一次询问前初始化
- 因为只有四个字符，所以我们可以将四个字符转化为数字，这样我们在处理判断的时候就会方便一些
- fail值初始化为-1，因为我们的f数组（也就是dp数组）0是有意义的
- 构造失败指针的时候用到了我很久以前讲的一个继承的知识点
然后一切问题都游刃而解，剩下的就看代码的实现吧
（注释版，我已经把细节讲清楚了，所以的话可以尝试自己挑战一下，然后再poj提交）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
struct node
{
int s,fail,cnt[];
/*只有四个数字，所以cnt不用定义这么大
fail表示失败指针，s记录模式串的结尾*/
}tr[];
int tot,list[];
char a[];
void clean(int x)/*多组数据清空树*/
{
tr[x].fail=-; tr[x].s=;/*为什么fail的初始化值要为-1呢，因为我们在构造失败指针的时候，
是把孩子节点直接继承失败指针，如果这个时候用0来区分的话，可能会炸掉*/
memset(tr[x].cnt,-,sizeof(tr[x].cnt));
}
int id(char c)/*为了方便，我们把要处理的数字都直接转化成数字*/
{
if(c=='A') return ;
if(c=='C') return ;
if(c=='G') return ;
return ;
}
void build_tree()/*建树板子*/
{
int x=; int len=strlen(a+);
for(int i=;i<=len;i++)
{
int y=id(a[i]);
if(tr[x].cnt[y]==-)
{
tr[x].cnt[y]=++tot;
clean(tot);
}
x=tr[x].cnt[y];
}
tr[x].s++;
}
void bfs()/*构造失败指针*/
{
list[]=; int head=,tail=;
while(head<=tail)
{
int x=list[head];
for(int i=;i<=;i++)
{
int son=tr[x].cnt[i];
if(son==-)/*没有孩子*/
{
if(x==) tr[x].cnt[i]=;/*这里要等于0，因为如果不等于0的话，在下面dp会炸掉*/
else tr[x].cnt[i]=tr[tr[x].fail].cnt[i];/*我在板子里面讲过是可以继承我fail指针的，这个是成立的*/
continue;
}
if(x==) tr[son].fail=;/*根节点的fail值为0*/
else
{
int j=tr[x].fail;
while(j!=-)/*这个点存在*/
{
if(tr[j].cnt[i]!=-)/*有孩子节点*/
{
tr[son].fail=tr[j].cnt[i];/*指向孩子节点，和上面的那个是一样的，可以继承*/
int tt=tr[j].cnt[i];
if(tr[tt].s!=) tr[son].s=;/*如果他的孩子节点是结尾的话，son也是作为结尾
因为继承所以一切都讲通了*/
break;
}
j=tr[j].fail;/*继续继承*/
}
if(j==-) tr[son].fail=;/*如果这个点不存在，那么x儿子的失败指针就指向根节点*/
}
list[++tail]=son;
}
head++;
}
}
int f[][],p,n,ans;
/*f数组是用来运行dp的，p是输入的模式串的个数，n是修改串的长度，ans记录答案
f[i][j]表示当前在第i位（修改串），匹配到AC自动机上（字典树）的第j个结点，
转移时，考虑添加一个字符，在AC自动机上获取添加这个结点会转移到的下一个结点（字符串匹配），并判断这样转移是否形成了一个模式串。
读到i个字符时，对应于j状态（DP的过程要两重循环i和j），要转移到son[j]（j的子节点状态，在这里用k在[1,4]一重循环遍历所有可以转字符），
如果第i个字符跟所要转移到的字符相同，则代价为0，因为不需要改变；否则代价为1，因为需要改变*/
void dp()
{
for(int i=;i<=n;i++) for(int j=;j<=tot;j++) f[i][j]=; f[][]=;/*初始化*/
for(int i=;i<n;i++)
{
for(int j=;j<=tot;j++)
{
if(f[i][j]==) continue;
for(int k=;k<=;k++)/*四种状态*/
{
int son=tr[j].cnt[k];/*要转移的状态*/
if(tr[son].s) continue;/*已经是结尾就没有必要继续搜索了*/
f[i+][son]=min(f[i+][son],f[i][j]+(id(a[i+])!=k));
/*下一位如果等于要转移的状态，代价为0，否则就为1*/
}
}
}
ans=;
for(int i=;i<=tot;i++) ans=min(ans,f[n][i]);
if(ans==) ans=-;/*一遍一遍更新答案*/
}
int main()
{
int t=; while(scanf("%d",&p)!=EOF && p)/*多组数据*/
{
t++; tot=; clean();/*t组数据，多组数据初始化*/
for(int i=;i<=p;i++)
{
scanf("%s",a+);
build_tree();/*输入建树*/
}
scanf("%s",a+); n=strlen(a+);/*长度*/
bfs(); dp();/*失败标记跑一边，然后dp跑一边找答案*/
printf("Case %d: %d\n",t,ans);
}
return ;
}
Tristan Code 注释版
（非注释版，最好就按照这个学习啦）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
struct node
{
int s,fail,cnt[];
}tr[];
int tot,list[];
char a[];
void clean(int x)
{
tr[x].fail=-; tr[x].s=;
memset(tr[x].cnt,-,sizeof(tr[x].cnt));
}
int id(char c)
{
if(c=='A') return ;
if(c=='C') return ;
if(c=='G') return ;
return ;
}
void build_tree()
{
int x=; int len=strlen(a+);
for(int i=;i<=len;i++)
{
int y=id(a[i]);
if(tr[x].cnt[y]==-)
{
tr[x].cnt[y]=++tot;
clean(tot);
}
x=tr[x].cnt[y];
}
tr[x].s++;
}
void bfs()
{
list[]=; int head=,tail=;
tr[].fail=-;
while(head<=tail)
{
int x=list[head];
for(int i=;i<=;i++)
{
int son=tr[x].cnt[i];
if(son==-)
{
if(x==) tr[x].cnt[i]=;
else tr[x].cnt[i]=tr[tr[x].fail].cnt[i];
continue;
}
if(x==) tr[son].fail=;
else
{
int j=tr[x].fail;
while(j!=-)
{
if(tr[j].cnt[i]!=-)
{
tr[son].fail=tr[j].cnt[i];
int tt=tr[j].cnt[i];
if(tr[tt].s!=) tr[son].s=;
break;
}
j=tr[j].fail;
}
if(j==-) tr[son].fail=;
}
list[++tail]=son;
}
head++;
}
}
int f[][],p,n,ans;
void dp()
{
for(int i=;i<=n;i++) for(int j=;j<=tot;j++) f[i][j]=; f[][]=;
for(int i=;i<n;i++)
{
for(int j=;j<=tot;j++)
{
if(f[i][j]==) continue;
for(int k=;k<=;k++)
{
int son=tr[j].cnt[k];
if(tr[son].s) continue;
f[i+][son]=min(f[i+][son],f[i][j]+(id(a[i+])!=k));
}
}
}
ans=;
for(int i=;i<=tot;i++) ans=min(ans,f[n][i]);
if(ans==) ans=-;
}
int main()
{
int t=; while(scanf("%d",&p)!=EOF && p)
{
t++; tot=; clean();
for(int i=;i<=p;i++)
{
scanf("%s",a+);
build_tree();
}
scanf("%s",a+); n=strlen(a+);
bfs(); dp();
printf("Case %d: %d\n",t,ans);
}
return ;
}
Tristan Code 非注释版
最新文章
- 安装cocoapods
- c3p0 连接池
- 使用Spire.Doc来转换文本
- java设计模式 策略模式Strategy
- iOS--UIScrollView图片动画切换【实现每次只加载3张图片,进而减少占用内存，可循环滚动】
- django之分页、cookie装饰器
- Android入门(十四)内容提供器-实现跨程序共享实例
- SQL双重游标（双重循环）--笔记
- 转： PE rva to raw 虚拟偏移地址和文件物理偏移地址
- UTF8与GBK、GB2312等其他字符编码的相互转换
- URAL1113（数学）
- 【转】【Android应用开发详解】第01期：第三方授权认证（一）实现第三方授权登录、分享以及获取用户资料
- 如何使用OLAMI自然语言理解开放平台API制作自己的智能对话助手小程序
- java5 - 数组与排序算法
- 系统引导修复 ---- Windows 和 Ubuntu
- java 查找类的所有子类
- XML的介绍使用
- Codeforces997D Cycles in product 【FFT】【树形DP】
- Linux 文件特殊权限_013
- ADC分类及参数