题意：

给你N个模板串,并且给你一个文本串,

现在问你这个文本串最少需要改变几个字符才能使得它不包含任何模板串.

(以上字符只由A,T,G,C构成)

 

题解：

刚开始做这一题的时候表示很懵逼，好像没有学过这种类型的问题。

后面仔细想想，在之前的题目中，学会了求出不包含任何模板串的方案数。

这题可以转化下，求出所有不包含任何模板串的方案中与原串最少的不同数目。

根据这个DP

dp【i】【j】 表示走到长度为 i 的时候，在AC自动机 j 这个节点上最多与原串不同的个数。

然后这题就变成SB题了。

 

1 #include 
      
         2 #include 
       

Q; 91 fail[root] = root; 92 for (int i = 0; i < 4; i++) 93 if (next[root][i] == -1) next[root][i] = root; 94 else { 95 fail[next[root][i]] = root; 96 Q.push(next[root][i]); 97 } 98 while (!Q.empty()) { 99 int now = Q.front();100 Q.pop();101 if (End[fail[now]]) End[now] = 1;102 for (int i = 0; i < 4; i++)103 if (next[now][i] == -1) next[now][i] = next[fail[now]][i];104 else {105 fail[next[now][i]] = next[fail[now]][i];106 Q.push(next[now][i]);107 }108 }109 }110 111 int solve() {112 int len = strlen(buf);113 for (int i = 0; i <= len; ++i)114 for (int j = 0; j < cnt; ++j)115 dp[i][j] = INF;116 dp[0][0] = 0;117 for (int i = 0; i < len; ++i) {118 for (int j = 0; j < cnt; ++j) {119 if (dp[i][j] == INF || End[j]) continue;120 for (int k = 0; k < 4; ++k) {121 int idx = next[j][k];122 if (End[idx]) continue;123 dp[i + 1][idx] = min(dp[i + 1][idx], dp[i][j] + (get_num(buf[i]) != k));124 }125 }126 }127 int ans = INF;128 for (int i = 0; i < cnt; ++i) ans = min(ans, dp[len][i]);129 if (ans == INF) return -1;130 return ans;131 }132 133 void debug() {134 for (int i = 0; i < cnt; i++) {135 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);136 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);137 printf("]\n");138 }139 }140 } ac;141 142 143 int main() {144 //FIN;145 int cas = 1;146 while (sfi(n) && n) {147 ac.init();148 for (int i = 1; i <= n; ++i) {149 sfs(str[i]);150 ac.insert(str[i]);151 }152 ac.build();153 sfs(buf);154 printf("Case %d: %d\n", cas++, ac.solve());155 }156 return 0;157 }