思路:首先将病变的基因串建立Trie数,然后构造AC自动机的fail指针,trie上所有末节点都是不能到的,赋值1,所有指向末节点的点也是不能到的,同样赋值。
之后就是一个动态规划的过程。dp[i][j]代表前i个字符到达在trie上的j节点状态需要改动的最小个数,然后根据这个向后递推,枚举下一位是什么,在ac自动机上状态转移。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<map> #define maxn 1<<29 using namespace std; int ch[1111][4],val[1111]; int f[1111]; int sz,n,m; char str[22]; char s[1111]; int dp[1111][1111]; int ans; void init() { sz=0; memset(ch[0],0,sizeof(ch[0])); } int getnum(char c) { switch(c) { case 'A': return 0; case 'C': return 1; case 'G': return 2; case 'T': return 3; } } void insert(char *a,int vv) { int u=0,l=strlen(a); for(int i=0; i<l; i++) { int c=getnum(a[i]); if(!ch[u][c]) { ch[u][c]=++sz; memset(ch[sz],0,sizeof(ch[sz])); val[sz]=0; } u=ch[u][c]; } val[u]=vv; } void getfail() { queue<int>q; f[0]=0; for(int i=0; i<4; i++) { int u=ch[0][i]; if(u) { f[u]=0; q.push(u); } } while(!q.empty()) { int r=q.front(); q.pop(); for(int i=0; i<4; i++) { int u=ch[r][i]; if(!u)continue; q.push(u); int v=f[r]; while(v&&!ch[v][i])v=f[v]; f[u]=ch[v][i]; if(val[f[u]])val[u]=val[f[u]]; } } } void solve() { int l=strlen(s); for(int i=0; i<=l; i++) { for(int j=0; j<=sz; j++)dp[i][j]=maxn; } dp[0][0]=0; for(int i=0; i<l; i++) { for(int j=0; j<=sz; j++) { if(val[j]||dp[i][j]==maxn)continue; for(int k=0; k<4; k++) { int u=ch[j][k]; if(u) { if(val[u])continue; else { if(getnum(s[i])==k)dp[i+1][u]=min(dp[i][j],dp[i+1][u]); else dp[i+1][u]=min(dp[i][j]+1,dp[i+1][u]); } } else { int r=j; while(r&&!ch[r][k])r=f[r]; int v=ch[r][k]; if(v) { if(!val[v]) { if(getnum(s[i])==k)dp[i+1][v]=min(dp[i][j],dp[i+1][v]); else dp[i+1][v]=min(dp[i][j]+1,dp[i+1][v]); } } else { if(getnum(s[i])==k)dp[i+1][v]=min(dp[i][j],dp[i+1][v]); else dp[i+1][v]=min(dp[i][j]+1,dp[i+1][v]); } } } } } for(int i=0;i<=sz;i++)ans=min(ans,dp[l][i]); } int main() { int ca=1; while(scanf("%d",&n)&&n) { init(); for(int i=0; i<n; i++) { scanf("%s",str); insert(str,1); } getfail(); scanf("%s",s); ans=maxn; solve(); printf("Case %d: ",ca++); if(ans==maxn)printf("-1\n"); else printf("%d\n",ans); } return 0; }