 | |||||||||||||
| |||||||||||||
| BestCoder官方QQ群：385386683 欢迎加入~ 寻人启事：2014级新生看过来！ | |||||||||||||
DNA repairTime Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1352 Accepted Submission(s): 734 Problem Description Biologists finally invent techniques of repairing DNA that contains segments causing kinds of inherited diseases. For the sake of simplicity, a DNA is represented as a string containing characters 'A', 'G' , 'C' and 'T'. The repairing techniques are simply to change some characters to eliminate all segments causing diseases. For example, we can repair a DNA "AAGCAG" to "AGGCAC" to eliminate the initial causing disease segments "AAG", "AGC" and "CAG" by changing two characters. Note that the repaired DNA can still contain only characters 'A', 'G', 'C' and 'T'. You are to help the biologists to repair a DNA by changing least number of characters. Input The input consists of multiple test cases. Each test case starts with a line containing one integers N (1 ≤ N ≤ 50), which is the number of DNA segments causing inherited diseases. The following N lines gives N non-empty strings of length not greater than 20 containing only characters in "AGCT", which are the DNA segments causing inherited disease. The last line of the test case is a non-empty string of length not greater than 1000 containing only characters in "AGCT", which is the DNA to be repaired. The last test case is followed by a line containing one zeros. Output For each test case, print a line containing the test case number( beginning with 1) followed by the number of characters which need to be changed. If it's impossible to repair the given DNA, print -1. Sample Input |
最近做AC自动机跟DP结合的题，总结一下，首先构建AC自动机，然后根据AC自动机构造转台转移，就是说不能往单词节点转移，那种构造字符串的题，可以利用矩阵计算，也可以用DP进行计算，还有像这种修改字符串达到要求的，则可以用dp计算。
其实就是利用AC自动机的每个节点作为状态进行转移
对于这个题：构造完AC自动机后，进行转移，遇到单词节点跳过，不是的话判断此节点的字母与要匹配的串的字母是否相等，相等说明不用修改，否则加1，转移到下一个节点
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=1010;
const int INF=1000000000;
const int SIGMA_SIZE=4;
int N;
char s[30],str[maxn];
struct AC
{
int ch[maxn][4],val[maxn];
int fail[maxn];
int dp[maxn][maxn];
int sz;
void clear(){memset(ch[0],0,sizeof(ch[0]));sz=1;}
int idx(char x)
{
if(x=='A')return 0;
else if(x=='C')return 1;
else if(x=='G')return 2;
return 3;
}
void insert(char *s)
{
int n=strlen(s);
int u=0;
for(int i=0;i<n;i++)
{
int c=idx(s[i]);
if(!ch[u][c])
{
memset(ch[sz],0,sizeof(ch[sz]));
val[sz]=0;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=1;
}
void getfail()
{
queue<int> q;
fail[0]=0;
int u=0;
for(int c=0;c<SIGMA_SIZE;c++)
{
u=ch[0][c];
if(u){fail[u]=0;q.push(u);}
}
while(!q.empty())
{
int r=q.front();q.pop();
if(val[fail[r]])val[r]=1;
for(int c=0;c<SIGMA_SIZE;c++)
{
u=ch[r][c];
if(!u){ch[r][c]=ch[fail[r]][c];continue;}
q.push(u);
int v=fail[r];
while(v&&!ch[v][c])v=fail[v];
fail[u]=ch[v][c];
}
}
}
void solve(char *s)
{
int n=strlen(s);
for(int i=0;i<=n;i++)
for(int j=0;j<sz;j++)dp[i][j]=INF;
dp[0][0]=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<sz;j++)
{
for(int k=0;k<4;k++)
{
//刚开始这里不太明白为什么单词节点要跳过去，因为自己觉得也可以修改这个点来维护，后来一想真是自己秀逗了
//跳过去之后，去匹配下一个，肯定会修改的（ACGA是单词节点，当前匹配到G了，往下走的时候，发现A是单词节点，跳过去
//在去匹配G的孩子C，C!=A，所以多一次修改，还是相当于修改了A这个点）
if(val[ch[j][k]])continue;
int tmp;
if(k==idx(s[i]))tmp=dp[i][j];
else tmp=dp[i][j]+1;
dp[i+1][ch[j][k]]=min(dp[i+1][ch[j][k]],tmp);
}
}
}
int ans=INF;
for(int i=0;i<sz;i++)
if(dp[n][i]<ans)ans=dp[n][i];//这里要是dp[n][i]，因为最后一步也需要转移
if(ans>=INF)printf("-1\n");
else printf("%d\n",ans);
}
}ac;
int main()
{
int cas=1;
while(scanf("%d",&N)!=EOF,N)
{
ac.clear();
for(int i=0;i<N;i++)
{
scanf("%s",s);
ac.insert(s);
}
ac.getfail();
scanf("%s",str);
printf("Case %d: ",cas++);
ac.solve(str);
}
return 0;
}