题意：
给你N个模板串,并且给你一个文本串,
现在问你这个文本串最少需要改变几个字符才能使得它不包含任何模板串.
(以上字符只由A,T,G,C构成)
题解：
刚开始做这一题的时候表示很懵逼，好像没有学过这种类型的问题。
后面仔细想想，在之前的题目中，学会了求出不包含任何模板串的方案数。
这题可以转化下，求出所有不包含任何模板串的方案中与原串最少的不同数目。
根据这个DP
dp【i】【j】 表示走到长度为 i 的时候，在AC自动机 j 这个节点上最多与原串不同的个数。
然后这题就变成SB题了。
1 #include <set>
2 #include <map>
3 #include <stack>
4 #include <queue>
5 #include <cmath>
6 #include <ctime>
7 #include <cstdio>
8 #include <string>
9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13 #include <unordered_map>
14
15 #define pi acos(-1.0)
16 #define eps 1e-9
17 #define fi first
18 #define se second
19 #define rtl rt<<1
20 #define rtr rt<<1|1
21 #define bug printf("******\n")
22 #define mem(a, b) memset(a,b,sizeof(a))
23 #define name2str(x) #x
24 #define fuck(x) cout<<#x" = "<<x<<endl
25 #define sfi(a) scanf("%d", &a)
26 #define sffi(a, b) scanf("%d %d", &a, &b)
27 #define sfffi(a, b, c) scanf("%d %d %d", &a, &b, &c)
28 #define sffffi(a, b, c, d) scanf("%d %d %d %d", &a, &b, &c, &d)
29 #define sfL(a) scanf("%lld", &a)
30 #define sffL(a, b) scanf("%lld %lld", &a, &b)
31 #define sfffL(a, b, c) scanf("%lld %lld %lld", &a, &b, &c)
32 #define sffffL(a, b, c, d) scanf("%lld %lld %lld %lld", &a, &b, &c, &d)
33 #define sfs(a) scanf("%s", a)
34 #define sffs(a, b) scanf("%s %s", a, b)
35 #define sfffs(a, b, c) scanf("%s %s %s", a, b, c)
36 #define sffffs(a, b, c, d) scanf("%s %s %s %s", a, b,c, d)
37 #define FIN freopen("../date.txt","r",stdin)
38 #define gcd(a, b) __gcd(a,b)
39 #define lowbit(x) x&-x
40 #define IO iOS::sync_with_stdio(false)
41
42
43 using namespace std;
44 typedef long long LL;
45 typedef unsigned long long ULL;
46 const ULL seed = 13331;
47 const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
48 const int maxn = 1e6 + 7;
49 const int maxm = 8e6 + 10;
50 const int INF = 0x3f3f3f3f;
51 const int mod = 1e9 + 7;
52
53
54 char str[55][22], buf[1010];
55 int n, dp[1010][1010];
56
57 int get_num(char ch) {
58 if (ch == 'A') return 0;
59 if (ch == 'T') return 1;
60 if (ch == 'C') return 2;
61 if (ch == 'G') return 3;
62 }
63
64 struct Aho_Corasick {
65 int next[1010][4], fail[1010], End[1010];
66 int root, cnt;
67
68 int newnode() {
69 for (int i = 0; i < 4; i++) next[cnt][i] = -1;
70 End[cnt++] = 0;
71 return cnt - 1;
72 }
73
74 void init() {
75 cnt = 0;
76 root = newnode();
77 }
78
79 void insert(char buf[]) {
80 int len = strlen(buf);
81 int now = root;
82 for (int i = 0; i < len; i++) {
83 if (next[now][get_num(buf[i])] == -1) next[now][get_num(buf[i])] = newnode();
84 now = next[now][get_num(buf[i])];
85 }
86 End[now]++;
87 }
88
89 void build() {
90 queue<int> 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 }
View Code