题目地址：http://poj.org/problem?id=3691
思路：
把所有节点建一棵trie树
那么我们要做的 就是把母串在树上搜索，而且在搜索的时候不会碰到危险节点
也即是对于节点j有条字母边a到son[j] ，
1）如果son[j]是危险节点，那么换一条j的边
2）如果son[j]为空，就顺着前驱节点找另一个字母边a
3）如果以上都不是，那么比较a和插入母串的字符，如果一样，那么不用改变，如果不一样，那么就次数加一，因为要改变插入的母串的该字符，变为a
具体dp思路如下：
对于这样的多字符串模式匹配问题，我们想到了DFA，那就试试吧。
首先按照给出的P个模式串构造一棵DFA出来。这时候，我们发现DFA给我们创建了一个很好的动态规划的平台。迅速给出状态：
Ans[i][j]表示若要用长度为i的母串的前缀遍历DFA树，使之达到节点 j ，至少要修改多少个字符。j 必须不是“危险”节点。
初始情况：
Ans[0][1] = 0 //1是DFA的初始节点
其他所有Ans[i][j] 为无穷大
问题的答案就是
Min{ Ans[len][j] | j 是DFA的安全节点 }
len是母串的长度
试试DFA吧
递推公式为：
由Ans[i][j] 可以推出：
Ans[i+1][son[j]] = min { Ans[i+1][son[j]],Ans[i][j] + ( Char(j,son[j]) != str[i] ) }
( Char(j,son[j]) != str[i] ) 表达式值为0或1Char(j,son[j])表示从节点j走到节点son[j]所经过的字母
str是母串,下标从0开始算
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int letter=4;
const int INF=0x3f3f3f3f;
struct Node{Node *pChilds[letter],*pPrev;bool bBadNode;
}tree[1000+5];
char DNA[30+5];
char str[1000+5];
map<char,int> idx;
int d[1000+5][1000+5],nNode;
//d[i][j]要用长度i的字母串的前缀遍历DFA，
//到达节点j，也即是tree[j] 至少需要修改多少个字符
void Insert(Node* root,char* s)
{for(int i=0;s[i];i++){if(root->pChilds[idx[s[i]]]==NULL)root->pChilds[idx[s[i]]]=tree+nNode++;root=root->pChilds[idx[s[i]]];}root->bBadNode=true;
}
void BuildDfa()
{for(int i=0;i<letter;i++)tree[0].pChilds[i]=tree+1;tree[1].pPrev=tree;tree[0].pPrev=NULL;queue<Node*> Q;Q.push(tree+1);while(!Q.empty()){Node* root=Q.front(); Q.pop();for(int i=0;i<letter;i++){Node* p=root->pChilds[i];if(p==NULL) {continue;} Node* pPrev=root->pPrev;while(pPrev!=NULL){if(pPrev->pChilds[i]!=NULL){p->pPrev=pPrev->pChilds[i];if(p->pPrev->bBadNode) p->bBadNode=true;break;}else pPrev=pPrev->pPrev;}Q.push(p);}}
}
int main()
{idx['A']=0;idx['C']=1;idx['G']=2;idx['T']=3;int n,kase=0;while(cin>>n&&n){memset(tree,0,sizeof(tree));memset(d,INF,sizeof(d));nNode=2;for(int i=0;i<n;i++){scanf("%s",DNA);Insert(tree+1,DNA);}BuildDfa();scanf("%s",str);d[0][1]=0; //0个字母在root点当然不用修改 int len=strlen(str);for(int i=0;i<len;i++)for(int j=1;j<nNode;j++){if(tree[j].bBadNode) continue;for(int k=0;k<letter;k++){Node* pPrev=tree+j;while(pPrev){if(pPrev->pChilds[k]!=NULL){if(pPrev->pChilds[k]->bBadNode) break;int son=pPrev->pChilds[k]-tree;d[i+1][son]=min(d[i+1][son],d[i][j]+(idx[str[i]]!=k));break;} pPrev=pPrev->pPrev;} }}int ans=INF;for(int i=1;i<nNode;i++) ans=min(ans,d[len][i]);printf("Case %d: %d\n",++kase,ans==INF?-1:ans);}return 0;
}
下面是网上优化的算法，直接在建DFA时求出每个节点的孩子节点
时间快了几十MS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int letter=4;
const int INF=0x3f3f3f3f;
struct Node{Node *pChilds[letter],*pPrev;bool bBadNode;
}tree[1000+5];
char DNA[30+5];
char str[1000+5];
map<char,int> idx;
int d[1000+5][1000+5],nNode;
//d[i][j]要用长度i的字母串的前缀遍历DFA，
//到达节点j，也即是tree[j] 至少需要修改多少个字符
void Insert(Node* root,char* s)
{for(int i=0;s[i];i++){if(root->pChilds[idx[s[i]]]==NULL)root->pChilds[idx[s[i]]]=tree+nNode++;root=root->pChilds[idx[s[i]]];}root->bBadNode=true;
}
void BuildDfa()
{for(int i=0;i<letter;i++)tree[0].pChilds[i]=tree+1;tree[1].pPrev=tree;tree[0].pPrev=NULL;queue<Node*> Q;Q.push(tree+1);while(!Q.empty()){Node* root=Q.front(); Q.pop();for(int i=0;i<letter;i++){Node* p=root->pChilds[i];if(p==NULL) {if(root==tree+1) root->pChilds[i]=tree+1;else root->pChilds[i]=root->pPrev->pChilds[i]; continue;} Node* pPrev=root->pPrev;while(pPrev!=NULL){if(pPrev->pChilds[i]!=NULL){p->pPrev=pPrev->pChilds[i];if(p->pPrev->bBadNode) p->bBadNode=true;break;}else pPrev=pPrev->pPrev;}Q.push(p);}}
}
int main()
{idx['A']=0;idx['C']=1;idx['G']=2;idx['T']=3;int n,kase=0;while(cin>>n&&n){memset(tree,0,sizeof(tree));memset(d,INF,sizeof(d));nNode=2;for(int i=0;i<n;i++){scanf("%s",DNA);Insert(tree+1,DNA);}BuildDfa();scanf("%s",str);d[0][1]=0; //0个字母在root点当然不用修改 int len=strlen(str);for(int i=0;i<len;i++)for(int j=1;j<nNode;j++){for(int k=0;k<letter;k++){Node* p=tree[j].pChilds[k];if(p->bBadNode) continue;int son=p-tree;d[i+1][son]=min(d[i+1][son],d[i][j]+(idx[str[i]]!=k));}} int ans=INF;for(int i=1;i<nNode;i++) ans=min(ans,d[len][i]);printf("Case %d: %d\n",++kase,ans==INF?-1:ans);}return 0;
}