修复DNA
输入格式
输入包含多组测试数据。
每组数据第一行包含整数N,表示致病DNA片段的数量。
接下来N行,每行包含一个长度不超过20的非空字符串,字符串中仅包含字符’A’, ‘G’ , ‘C’ , ‘T’,用以表示致病DNA片段。
再一行,包含一个长度不超过1000的非空字符串,字符串中仅包含字符’A’, ‘G’ , ‘C’ , ‘T’,用以表示待修复DNA片段。
最后一组测试数据后面跟一行,包含一个0,表示输入结束。
输出格式
每组数据输出一个结果,每个结果占一行。
输入形如”Case x: y”,其中x为测试数据编号(从1开始),y为修复过程中所需改变的字符数量的最小值,如果无法修复给定DNA片段,则y为”-1”。
数据范围
$1≤N≤50$
样例
输入样例:
2
AAA
AAG
AAAG
2
A
TG
TGAATG
4
A
G
C
T
AGT
0
输出样例:
Case 1: 1
Case 2: 4
Case 3: -1
算法
(AC自动机) $O(?)$
首先简要介绍一下AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室, 是著名的多模匹配算法之一。 一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。要搞懂AC自动机,先得有模式树(字典树)Trie和KMP模式匹配算法的基础知识。KMP算法是单模式串的字符匹配算法,AC自动机是多模式串的字符匹配算法。
AC自动机和KMP和trie树的关系比较大,所以先来简单的了解下字典树Trie。
字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
简而言之:字典树就是像平时使用的字典一样的,我们把所有的单词编排入一个字典里面,当我们查找单词的时候,我们首先看单词首字母,进入首字母所再的树枝,然后看第二个字母,再进入相应的树枝,假如该单词再字典树中存在,那么我们只用花费单词长度的时间查询到这个单词。
接着,我们再看看KMP(算法基础课里面有讲到,这里写一下我的看法)我个人感觉AC自动机只是和KMP有点沾边,所以就讲一下
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
时间复杂度
这个……我不是很清楚,哪位大神来帮我解决一下,我不擅长算时间复杂度
参考文献
百度百科(好,我承认,我是找了几个写的比较好的然后直接复制的,因为我觉得我自己并没有给别人讲清楚知识点的天分🤦)
C++ 代码
(我觉得应该是大家的关注重点,但是我的代码很丑陋,大家不要喷我好吗?)
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,tr[1005][4],dar[1005],idx,q[1005],ne[1005],f[1005][1005];
char str[1005];
int get(char c){
if(c=='A')return 0;
if(c=='T')return 1;
if(c=='G')return 2;
return 3;
}
void insert(){
int p=0,i,t;
for(i=0;str[i];i++){
t=get(str[i]);
if(tr[p][t]==0)tr[p][t]=++idx;
p=tr[p][t];
}
dar[p]=1;
}
void build()
{
int h=0,t=-1,i,x,p;
for(i=0;i<4;i++)if(tr[0][i])q[++t]=tr[0][i];
while(h<=t){
x=q[h++];
for(i=0;i<4;i++){
p=tr[x][i];
if(!p)tr[x][i]=tr[ne[x]][i];
else ne[p]=tr[ne[x]][i],q[++t]=p,dar[p]|=dar[ne[p]];
}
}
}
int main()
{
int T=1,i,j,k,t,p,ans;
while(scanf("%d",&n),n){
memset(tr,0,sizeof tr);
memset(dar,0,sizeof dar);
memset(ne,0,sizeof ne);
idx=0;
for(i=0;i<n;i++)scanf("%s",str),insert();
build();
scanf("%s",str+1),m=strlen(str+1);
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(i=0;i<m;i++)for(j=0;j<=idx;j++)for(k=0;k<4;k++){
t=get(str[i+1])!=k,p=tr[j][k];
if(!dar[p])f[i+1][p]=min(f[i+1][p],f[i][j]+t);
}
ans=0x3f3f3f3f;
for(i=0;i<=idx;i++)ans=min(ans,f[m][i]);
if(ans==0x3f3f3f3f)ans=-1;
printf("Case %d: %d\n",T++,ans);
}
return 0;
}