Fork me on GitHub

Hdu 2457(AC自动机)

Hdu 2457
Bzoj 1030思想差不多,就是方程不一样
这里方程是设$dp(i,j)$为考虑了$i$个字符,在自动机的$j$点上的最小代价
$$dp(i,v) = min(dp(i,v), dp(i-1,j)+(c != S_i))$$
其中$v$点是$ch(j, c)$(不存在则走失配边,直到有为止),即从$j$点转移到$v$点
$S$是带修理的主串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 50 * 20 + 5, INF = 1000000000;
int kase = 0, n, m, sz = 50 * 20;
char s[1005];
int f[MAXN], ch[MAXN][7], danger[MAXN], dp[1005][MAXN];
int idx(char c) {
switch (c) {
case 'A' : return 0;
case 'G' : return 1;
case 'C' : return 2;
case 'T' : return 3;
}
return -1;
}
void insert(char *s) {
int now = 0, len = strlen(s);
for (int i = 0; i < len; i++) {
int c = idx(s[i]);
if (!ch[now][c]) ch[now][c] = ++sz;
now = ch[now][c];
if (i == len - 1) danger[now] = true;
}
}
void getFail() {
queue<int> q;
f[0] = 0;
for (int c = 0; c < 4; c++) {
int v = ch[0][c];
if (v) q.push(v), f[v] = 0;
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int c = 0; c < 4; c++) {
int v = ch[u][c];
if (!v) {ch[u][c] = ch[f[u]][c]; continue;}
q.push(v);
int j = f[u]; while (j && !ch[j][c]) j = f[j];
f[v] = ch[j][c];
if (danger[ch[j][c]]) danger[v] = true;
}
}
}
void cal() {
dp[0][0] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 0; j <= sz; j++) {
if (danger[j] || dp[i - 1][j] == INF) continue;
for (int c = 0; c < 4; c++) {
int v = ch[j][c];
dp[i][v] = min(dp[i][v], dp[i - 1][j] + (c != idx(s[i])));
}
}
}
}
void clean() {
for (int i = 0; i <= sz; i++) {
for (int j = 0; j < 4; j++) ch[i][j] = 0;
f[i] = danger[i] = 0;
for (int j = 0; j <= 1000; j++) dp[j][i] = INF;//<=
}
sz = 0;
}
void solve() {
clean();
for (int i = 1; i <= n; i++) {
scanf("%s", s);
insert(s);
}
scanf("%s", s + 1), m = strlen(s + 1);
getFail(), cal();
int taki = INF;
for (int i = 0; i <= sz; i++) if (!danger[i]) taki = min(taki, dp[m][i]);
if (taki == INF) printf("Case %d: -1\n", ++kase); else printf("Case %d: %d\n", ++kase, taki);
}
int main() {
while (scanf("%d", &n) == 1 && n) solve();
return 0;
}

------ 本文结束 ------