题意：给你只包含‘A’，‘G’，‘T’，‘C’四个字母的n个模板串和1个文本串，问你文本串改变多少个字符就可以使得文本串中没有一个模板串
解题思路：
我们可以知道 dp[i][j] 为文本串到 第i 个字符 AC自动机状态为j的最少的变换次数（这里为什么要用AC自动机，因为end数组可以记录哪一个状态是结束的，而且处理以后可以知道那些后缀等于前缀--也就是不能到达，因为如果能够到达的话那么状态更新就会产生错误。），这样dp即可
解题代码：
1 // File Name: temp.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月11日 星期四 15时18分4秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #include<queue> 25 #define LL long long 26 #define maxn 1005 27 28 using namespace std; 29 int dp[maxn][maxn]; 30 struct Trie 31 { 32 int next[maxn][4],fail[maxn],end[maxn]; 33 int root, L; 34 int newnode() 35 { 36 memset(next[L],-1,sizeof(next[L])); 37 end[L++] = 0 ; 38 return L-1; 39 } 40 void init() 41 { 42 L = 0 ; 43 root = newnode(); 44 } 45 void insert(int buf[],int len) 46 { 47 int now = root; 48 for(int i = 0 ;i < len ;i ++) 49 { 50 if(next[now][buf[i]] == -1) 51 { 52 next[now][buf[i]] = newnode(); 53 } 54 now = next[now][buf[i]]; 55 } 56 end[now] = 1; 57 } 58 void build() 59 { 60 queue<int> Q; 61 fail[root] = root; 62 for(int i = 0;i < 4;i ++) 63 { 64 if(next[root][i] == -1) 65 { 66 next[root][i] = root; //指向root 是没有问题的，我们主要是通过end 数组对个数进行计数的。 67 }else{ 68 fail[next[root][i]] = root; 69 Q.push(next[root][i]); 70 } 71 } 72 while(!Q.empty()) 73 { 74 int now = Q.front(); 75 Q.pop(); 76 for(int i = 0 ;i < 4;i ++) 77 { 78 if(next[now][i] == -1) 79 { 80 next[now][i] = next[fail[now]][i]; 81 } 82 else{ 83 fail[next[now][i]] = next[fail[now]][i]; 84 if(end[next[fail[now]][i]] == 1) 85 end[next[now][i]] = 1; 86 Q.push(next[now][i]); 87 } 88 } 89 } 90 } 91 void query(int buf[],int len,int ca) 92 { 93 //end[3] = 1; 94 memset(dp,2,sizeof(dp)); 95 dp[0][0] = 0; 96 for(int i = 0 ;i < len ;i ++) 97 { 98 for(int j = 0 ;j < L ;j ++ ) 99 { 100 if(dp[i][j] < len && end[j] != 1) 101 for(int s = 0 ;s < 4;s ++) 102 { 103 if(end[next[j][s]] != 1) 104 dp[i+1][next[j][s]] = min(dp[i+1][next[j][s]],dp[i][j] + (buf[i] == s?0:1)); 105 } 106 } 107 } 108 int ans = dp[len][0]; 109 for(int i = 0 ;i < L ;i ++) 110 { 111 if(end[i] != 1) 112 ans = min(dp[len][i],ans); 113 } 114 if(ans <= len) 115 { 116 printf("Case %d: %d ",ca,ans); 117 }else{ 118 printf("Case %d: -1 ",ca); 119 } 120 121 } 122 }; 123 char buf[3000]; 124 int temp[3000]; 125 Trie ac; 126 void change(int len) 127 { 128 for(int i = 0;i < len;i ++) 129 { 130 if(buf[i] == 'A') 131 { 132 temp[i] = 0 ; 133 }else if(buf[i] == 'T'){ 134 temp[i] = 1; 135 }else if(buf[i] == 'G') 136 { 137 temp[i] = 2; 138 }else if(buf[i] == 'C') 139 { 140 temp[i] = 3; 141 } 142 } 143 } 144 int main(){ 145 int n; 146 int ca= 0 ; 147 //freopen("in","r",stdin); 148 while(scanf("%d",&n) != EOF,n) 149 { 150 ca ++ ; 151 ac.init(); 152 int len = strlen(buf); 153 for(int i =1 ;i <= n;i ++) 154 { 155 scanf("%s",buf); 156 len = strlen(buf); 157 change(len); 158 ac.insert(temp,len); 159 } 160 ac.build(); 161 scanf("%s",buf); 162 len = strlen(buf); 163 change(len); 164 ac.query(temp,len,ca); 165 } 166 return 0; 167 }