先用AC自动机构建一个不含有任何病毒串的 DFA , dp[i][j] 表示到目标串的第 i 个字符,DFA 状态为 j 时的最小修改数量。则 dp[i][ son[j] ]= min{ dp[i][ son[j] ], dp[i-1][j]+ (tran[j][ son[j] ]!= str[i] ) } tran[j][ son[j] ]表示从 j 到 son[j] 经过的字母边。
代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define inf 0x7fffffff
int const N= 2000;
struct Node{
int next[4];
int fail, flag;
void init(){
for( int i= 0; i< 4; ++i ) next[i]= 0;
fail= -1; flag= 0;
}
}tb[N];
char str[N];
int dp[N][N], n, cnt;
int inline toInt( char ch ){
if( ch== 'A' ) return 0;
if( ch== 'T' ) return 1;
if( ch== 'G' ) return 2;
if( ch== 'C' ) return 3;
}
void insert( char*s ){
int rt= 0;
while( *s ){
int t= toInt( *s );
if( tb[rt].next[t]== 0 ){
tb[++cnt].init();
tb[rt].next[t]= cnt;
}
rt= tb[rt].next[t]; s++;
}
tb[rt].flag= 1;
}
int que[N], head, tail;
void bfs(){
int p, q, now;
head= 0, tail= 0, que[0]= 0;
while( head<= tail ){
now= que[head++];
for( int t= 0; t< 4; ++t )
if( tb[now].next[t] ){
p= tb[now].next[t]; q= tb[now].fail;
while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
if( q== -1 ) tb[p].fail= 0;
else{
tb[p].fail= tb[q].next[t];
tb[p].flag|= tb[ tb[p].fail ].flag;
}
que[++tail]= p;
}
else{
q= tb[now].fail;
while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
if( q== -1 ) tb[now].next[t]= 0;
else tb[now].next[t]= tb[q].next[t];
}
}
}
int main(){
int test= 1;
while( scanf("%d",&n)!= EOF ){
if( n== 0 ) return 0;
cnt= 0; tb[0].init();
for( int i= 0; i< n; ++i ){
scanf("%s", str );
insert( str );
}
bfs();
scanf("%s",str);
int len= strlen(str);
for( int i= 0; i<= len; ++i )
for( int j= 0; j<= cnt; ++j ) dp[i][j]= inf;
dp[0][0]= 0;
for( int i= 1; i<= len; ++i ){
for( int j= 0; j<= cnt; ++j )
if( dp[i-1][j]!= inf && !tb[j].flag ){
for( int t= 0; t< 4; ++t )
if( !tb[ tb[j].next[t] ].flag ){
int k= tb[j].next[t];
dp[i][k]= min( dp[i][k], dp[i-1][j]+ ( t!= toInt( str[i-1] ) ) );
}
}
}
int ans= inf;
for( int i= 0; i<= cnt; ++i ) ans= min( ans, dp[len][i] );
printf("Case %d: ", test++ );
if( ans== inf ) printf("-1\n");
else printf("%d\n", ans );
}
return 0;
}
分享到:
相关推荐
PKU 、POJ ACM/ICPC300多题的代码,还有各种典型问题的分类代码
ACM PKU_poj 1197 仓库问题源代码,愿与大家共享。若谁更好的代码,多谢提供。
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks
用Java代码实现POJ(PKU)上题2494!
acm 1001 到1009代码,已通过验证
O(nlogn)凸包问题 poj2187
http://acm.pku.edu.cn/JudgeOnline/ acm的AC解题报告
acm pku poj 1000 1001 1002 1003 1201
acm.pku.edu.cn/OnlineJudge上一些已经通过的代码
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
没钱了,拿点东西出来换点钱...这题的想法是老师在讲最优二元树时偶然想到的...感觉还行
PKU 1000-1050我ac的代码!绝对保证质量!
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
poj1088原代码, 这是最新的版本, 经过我们dhuACM团队合作而编写的!
#include using namespace std; #define M 1000000 char t[M+1],p[M+1]; int lent,lenp; bool kmp(char *t,char *p) { int i,j; for(i=lenp,j=0;i;i++) { if(t[i]!=p[j]) return false;...}
本科参加ACM竞赛的过程中积累下来的一部分算法模板,和自己在PKU上面做的一部分题目。 模板目录结构: 目录: 动态规划 O(n^2)的最长上升子序列 nlogn最长上升子序列 高精度 计算几何 Graham扫描法 两线段交点 凸...
pku 123 题目代码 pku acm poj
基于Python的北京大学/北大/PKU 智慧场馆 场地预约 自动化 +源代码+文档说明 - 不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分...
pku acm 1007 DNA Sorting代码 逆序数 排序 解题报告请访问:http://blog.csdn.net/china8848