AC自动机 + dp状态机模板题
AC自动机模板参考
AcWing 1282. 搜索关键词
本题的状态机dp模型做法与 AcWing 1052. 设计密码 类似
状态表示
f[i][j]
表示DNA序列走到第i
个位置,AC自动机走到第j
个位置(相当于DNA序列不包含AC自动机的前j个元素)
的所有方案中最少修改的数量
状态:DNA序列上每一位都可以修改成’A’, ‘G’ , ‘C’ , ‘T’四种,所以对应的就是四种不同的状态
状态计算
大致计算过程与AcWing 1052. 设计密码类似,
(注意:在当fail[p]
,被打标记后,p
上也要打标记,因为从根到fail[p]
所组成的字符串是从根到p
所组成的字符串的后缀),
枚举第DNA序列,对于DNA序列的第i
位,枚举他可以修改的四种状态,当前DNA的第i
位的新位置在树中的位置就是f[i][p]
,然后判断这个新的DNA序列是否含有致病序列,如果不含有就计算这个状态的值:从前i - 1
位f[i - 1][j]
转移过来,并且操作次数加上1
(或0
)
for (int i = 1; i <= m; i ++ ) //枚举DNA序列长度
for (int j = 0; j <= idx; j ++ )//枚举第i位DNA能匹配到的所有致病串的节点
for (int k = 0; k < 4; k ++ )//枚举可以写入的第i个节点(状态机模型:有4个状态)
{
int t = get(str[i]) != k; //t状态表示需不需要进行修改,相同则不需要修改
int p = trie[j][k]; //写入第i个字符,到trie树的p指针位置
//没打上标记表示不包含致病串,只有不包含致病串才更新状态
//写入第i个字符后的状态是f[i][p],它是由只写入前i-1个字符时且匹配到了AC自动机的j位置的指针转移而来
if (!cnt[p]) f[i][p] = min(f[i][p], f[i - 1][j] + t);
}
//在当fail[p],被打标记后,p上也要打标记,因为从根到fail[p]所组成的字符串是从根到p所组成的字符串的后缀
cnt[trie[ans][i]] |= cnt[fail[trie[ans][i]]];
C++代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int trie[N][4]; //trie树,只有’A’, ‘G’ , ‘C’ , ‘T’四个分支
int fail[N]; //失配数组
int cnt[N]; //给结尾元素标记
int que[N]; //队列,用于构造fail
int f[N][N];
//f[i][j]表示DNA序列走到第i个位置,AC自动机走到第j个位置(相当于DNA序列不包含AC自动机的前j个元素)的所有方案中最少修改的数量
char str[N];
int n,idx; //idx为树节点的指针
int get(char c){
if(c == 'A') return 0;
if(c == 'G') return 1;
if(c == 'C') return 2;
return 3;
}
void insert(){ //将致病片段构造成trie树
int p = 0;
for(int i = 0;str[i];++i){
int u = get(str[i]);
if(!trie[p][u]) trie[p][u] = ++idx;
p = trie[p][u];
}
cnt[p] = 1;
}
void build(){
int hh = 0,tt = -1;
for(int i = 0;i < 4;++i){ //将第一层存在的节点先入队
if(trie[0][i]) que[++tt] = trie[0][i];
}
while(hh <= tt){
int ans = que[hh++];
for(int i = 0;i < 4;++i){ //枚举队头所有可能的分支
if(!trie[ans][i]){
trie[ans][i] = trie[fail[ans]][i];
}else{
fail[trie[ans][i]] = trie[fail[ans]][i];
que[++tt] = trie[ans][i];
//在当nxt[p],被打标记后,p上也要打标记,因为从根到nxt[p]所组成的字符串是从根到p所组成的字符串的后缀
cnt[trie[ans][i]] |= cnt[fail[trie[ans][i]]];
}
}
}
}
int main()
{
int T = 1;
while (scanf("%d", &n), n)
{
memset(trie, 0, sizeof trie);
memset(cnt, 0, sizeof cnt);
memset(fail, 0, sizeof fail);
idx = 0;
for (int i = 0; i < n; i ++ )
{
scanf("%s", str);
insert();
}
build();
scanf("%s", str + 1); //下面从1开始枚举,所以开始记录的下标也要从1开始
int m = strlen(str + 1);
memset(f, 0x3f, sizeof f);
f[0][0] = 0; //什么都没有匹配修改次数为0
for (int i = 1; i <= m; i ++ ) //枚举DNA序列长度
for (int j = 0; j <= idx; j ++ )//枚举第i位DNA能匹配到的所有致病串的节点
for (int k = 0; k < 4; k ++ )//枚举可以写入的第i个节点(状态机模型:有4个状态)
{
int t = get(str[i]) != k; //t状态表示需不需要进行修改,相同则不需要修改
int p = trie[j][k]; //写入第i个字符,到trie树的p指针位置
//没打上标记表示不包含致病串,只有不包含致病串才更新状态
//写入第i个字符后的状态是f[i][p],它是由只写入前i-1个字符时且匹配到了AC自动机的j指针位置转移而来
if (!cnt[p]) f[i][p] = min(f[i][p], f[i - 1][j] + t);
}
int res = 0x3f3f3f3f;
//因为匹配致病串的字符不论匹配到了哪个位置,只要没有人一个致病串出现过都是合法的,
//所以枚举idx个可能匹配到的致病串的长度,从中选出最小值
for (int i = 0; i <= idx; i ++ ) res = min(res, f[m][i]);
if (res == 0x3f3f3f3f) res = -1;
printf("Case %d: %d\n", T ++, res);
}
return 0;
}
看注释好像明白了些,感谢!