http://acm.pku.edu.cn/JudgeOnline/problem?id=3691
题目大意是说给定一个长度最大为1000的仅由A,T,C,G四个字符组成的字符串，要求改变最少的字符个数，使得得到的字符串中不含有任意预先给定的一系列子串。
一般都会想到用动态规划，但是怎么DP是个问题，怎么设计状态。换个角度，我们要最终的字符串不含有任意模板串，这个涉及到多串匹配的知识。我们知道，可以建立一个有限状态自动机DFA来判断一个字符串中是否还有某些模板串。关于多模板串的DFA的建立，可以利用字符串前缀函数特殊的性质，建立一个TRIE图（具体建立方法可以参见相关论文）。这样，给定一个字符串，就可以在这个TRIE图中沿相应的边转移，如果途经一个危险节点，也就是目标串中出现了一个模板串。所以，给定一个模板串，如果在TRIE图中“走”的过程中没有到达过危险节点，那么这个字符串就符合要求。
现在来看原题，要求把一个字符串改变最小的字符数，使得最终的字符串符合要求。由于模板串不变，DFA也没有变化，所以我们这样DP：设dp[i][j]表示到了目标串的第i个字符，并且走到了自动机的状态点j，中途没有经过任何危险结点，所改变的字符串的最小个数。具体DP过程也是比较简单的。直接看代码就差不多了。最后的答案就是min{dp[len][j]} (len是目标串的长度,j是自动机中的一个状态点，并且状态j不是目标状态)
#include <stdio.h>
#include <string.h>const int maxn=1000;
const int maxnodes=480;
const int maxchar=4;int child[maxnodes][maxchar];
bool danger[maxnodes];
int suffix[maxnodes],q[maxnodes];
int nodes,f,r,p;
int dp[maxn][maxnodes];
char str[maxn];
inline
int getwordid(char c) {
switch(c) {
case 'A':return 0;
case 'G':return 1;
case 'C':return 2;
case 'T':return 3;
}
}bool build_trie() {
char words[30];
int m;
nodes=1;
scanf("%d",&m);
if(m==0) return false;
memset(child,0,sizeof(child));
memset(danger,0,sizeof(danger));
memset(suffix,0,sizeof(suffix));
memset(q,0,sizeof(q));
for(int i=0;i<m;i++) {
scanf("%s",words);
int len=strlen(words);
p=1;
for(int j=0;j<len;j++) {
int d=getwordid(words[j]);
if(child[p][d]==0) {
nodes++;
child[p][d]=nodes;
}
p=child[p][d];
if(danger[p]) break;
}
danger[p]=true;
}
return true;
}void build_graph() {
f=r=0;
for(int i=0;i<maxchar;i++) {
if(child[1][i]==0) {
child[1][i]=1;
}else {
r++;
q[r]=child[1][i];
suffix[child[1][i]]=1;
}
}
while(f<r) {
f++;
danger[q[f]]=danger[q[f]] || danger[suffix[q[f]]];
if(!danger[q[f]]) {
for(int i=0;i<maxchar;i++) {
if(child[q[f]][i]==0)
child[q[f]][i]=child[suffix[q[f]]][i];
else {
r++;
q[r]=child[q[f]][i];
suffix[q[r]]=child[suffix[q[f]]][i];
}
}
}
}
}void checkmin(int& a,int b) {
if(a==-1) a=b;
else if(a>b) a=b;
}int main() {
//freopen("in.txt","r",stdin);
int cases=0;
while(build_trie()) {
cases++;
printf("Case %d: ",cases);
build_graph();
scanf("%s",str);
int len=strlen(str);
memset(dp,-1,sizeof(dp));
if(!danger[child[1][getwordid(str[0])]])
dp[0][child[1][getwordid(str[0])]]=0;
for(int i=0;i<maxchar;i++)
if(getwordid(str[0])!=i&&!danger[child[1][i]])
dp[0][child[1][i]]=1;
for(int i=1;i<len;i++) {
for(int j=1;j<=nodes;j++) {
if(dp[i-1][j]!=-1) {
if(!danger[child[j][getwordid(str[i])]])
checkmin(dp[i][child[j][getwordid(str[i])]],dp[i-1][j]);
for(int k=0;k<maxchar;k++)
if(getwordid(str[i])!=k&&!danger[child[j][k]])
checkmin(dp[i][child[j][k]],dp[i-1][j]+1);
}
}
}
int ans=1<<20;
for(int i=1;i<=nodes;i++)
if(!danger[i]&&dp[len-1][i]!=-1&&dp[len-1][i]<ans)
ans=dp[len-1][i];
if(ans==1<<20) ans=-1;
printf("%d\n",ans);
}
return 0;
}
