题意：
给n个模式串和1个主串，求主串最少改变多少个字符才能不含n个模式串中的任何一个。
分析：
多模式串匹配问题可以考虑ac自动机，把自动机构造出来后在上面dp,dp[len][s]表示主串到len个字符且位于自动机son状态时的最优值，则dp[len][son]=min(dp[len][s],dp[len-1][father]+(s[i]!=trans(father,son)))，trans(father,son)表示自动机中father状态转到son状态经过的字母边。
代码：
//poj 3691
//sep9
#include <iostream>
#include <queue>
using namespace std;
const int max_l=1024;
struct node
{int s[4],fail;bool word;
}a[max_l];queue<int> Q;
int len,index;
char s[max_l];
int dp[max_l][max_l];
int get_code(char c)
{if(c=='A') return 0;if(c=='G') return 1;if(c=='C') return 2;if(c=='T') return 3;
}void build_trie(int h,int k)
{if(k==len){a[h].word=true;return ;} int p=get_code(s[k]);if(!a[h].s[p])a[h].s[p]=++index;build_trie(a[h].s[p],k+1);
}void build_AC_Automation()
{int h,i;while(!Q.empty()) Q.pop(); Q.push(0);while(!Q.empty()){h=Q.front();Q.pop();for(i=0;i<4;++i)if(a[h].s[i]){Q.push(a[h].s[i]);if(h) a[a[h].s[i]].fail=a[a[h].fail].s[i];if(a[a[a[h].s[i]].fail].word==true) a[a[h].s[i]].word=true;}else if(h)a[h].s[i]=a[a[h].fail].s[i]; }
}int get_ans()
{memset(dp,0x7f,sizeof(dp));dp[0][0]=0;int i,j,k,son;for(i=1;i<=len;++i)for(j=0;j<=index;++j)if(dp[i-1][j]<max_l)for(k=0;k<4;++k)if(a[a[j].s[k]].word==false){son=a[j].s[k];dp[i][son]=min(dp[i][son],dp[i-1][j]+(k!=get_code(s[i-1])));}int ans=INT_MAX;for(i=0;i<=index;++i)ans=min(ans,dp[len][i]);if(ans<max_l) return ans;return -1;
}int main()
{int cases=0,n;while(scanf("%d",&n)==1&&n){memset(a,0,sizeof(a));index=0;while(n--){scanf("%s",s);len=strlen(s);build_trie(0,0);}build_AC_Automation();scanf("%s",s);len=strlen(s);printf("Case %d: %d\n",++cases,get_ans());}return 0;
}