HDU_2457

链接

• 点此跳转
• 推荐博客1
• 推荐博客2

题目描述

生物学家终于发明了修复 $DNA$ 的技术，能够将包含各种遗传疾病的 $DNA$ 片段进行修复。

为了简单起见，$DNA$ 看作是一个由 $A,G,C,T$ 构成的字符串。

修复技术就是通过改变字符串中的一些字符，从而消除字符串中包含的致病片段。

例如，我们可以通过改变两个字符，将 $DNA$ 片段 $AAGCAG$ 变为 $AGGCAC$ ，从而使得 $DNA$ 片段中不再包含致病片段 $AAG$ ，$AGC$ ，$CAG$ ，以达到修复该 $DNA$ 片段的目的。

需注意，被修复的 $DNA$ 片段中，仍然只能包含字符 $A,G,C,T$ 。

请你帮助生物学家修复给定的 $DNA$ 片段，并且修复过程中改变的字符数量要尽可能的少。

输入格式

输入包含多组测试数据。

每组数据第一行包含整数 $N$ ，表示致病 $DNA$ 片段的数量。

接下来 $N$ 行，每行包含一个长度不超过 $20$ 的非空字符串，字符串中仅包含字符 $A,G,C,T$ 用以表示致病 $DNA$ 片段。

再一行，包含一个长度不超过 $1000$ 的非空字符串，字符串中仅包含字符 $A,G,C,T$ 用以表示待修复 $DNA$ 片段。

最后一组测试数据后面跟一行，包含一个 $0$ ，表示输入结束。

输出格式

每组数据输出一个结果，每个结果占一行。

输入形如 Case x: y ，其中 $x$ 为测试数据编号（从 $1$ 开始)，$y$ 为修复过程中所需改变的字符数量的最小值，如果无法修复给定 $DNA$ 片段，则 $y$ 为 $-1$ 。

数据范围

$1\le N\le 50$

方法

首先，将读入的所有模式串 $T$ 建成 $AC$ 自动机，之后的匹配操作在 $AC$ 自动机上进行。

在创建 $AC$ 自动机时需要注意，若当前节点的后缀上有标记，那么当前节点也需要打上标记。

即

st[v] |= st[ne[v]];
1

设 $f[i][j]$ 为当前匹配到主串 $S$ 的第 $i$ 位（第 $i$ 位已经匹配成功），并且当前处在 $AC$ 自动机第 $j$ 个状态的最小操作数。

我不理解的地方是，若 $i<j$ ，字符串的长度没有状态机的状态多，这种情况怎么理解？

我们可以假想它们的长度相等，且原串的任意一个后缀都和状态机的任意一个前缀都不匹配，这就是我们现在所处的状态。

然后我们可以枚举下一个位置可以填的字符，在自动机上进行转移，但根据要求，我们不能向有标记的状态转移。

根据定义 $f[0][0]=0$ ，初始时所有 $f[][]$ 均为 $INF$ ，因为需要求最小值。

转移方程为 f [ i + 1 ] [ p ] = m i n { f [ i + 1 ] [ p ] , f [ i ] [ j ] + t } f[i+1][p]=min\{f[i+1][p],f[i][j]+t\} f[i+1][p]=min{f[i+1][p],f[i][j]+t} ，$p$ 为 $j$ 所能转移到的点，$t$ 为从 $f[i][j]$ 转移到 $f[i+1][p]$ 的花费。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 


#define endl '\n'
#define PI acos(-1)
#define LL long long
#define INF 0x3f3f3f3f
#define lowbit(x) (-x&x)
#define mem(a, b) memset(a, b, sizeof a)
#define rev(x) reverse(x.begin(), x.end())
#define IOS ios::sync_with_stdio(false),cin.tie(0)


using namespace std;

const int N = 1010;

int tr[N][4], st[N], ne[N], idx;
int f[N][N];
char str[N];
int n;

int get(char c) {
	if (c == 'A') return 0;
	else if (c == 'T') return 1;
	else if (c == 'G') return 2;
	else return 3;
}

void insert() {
	int p = 0;
	for (int i = 0; str[i]; i ++ ) {
		int j = get(str[i]);
		if (!tr[p][j]) tr[p][j] = ++ idx;
		p = tr[p][j];
	}
	st[p] = 1;
}

void build() {
	queue<int> q;
	for (int i = 0; i < 4; i ++ ) {
		if (tr[0][i]) q.push(tr[0][i]);
	}
	
	while(q.size()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < 4; i ++ ) {
			int v = tr[u][i];
			if (!v) tr[u][i] = tr[ne[u]][i];
			else {
				ne[v] = tr[ne[u]][i];
				st[v] |= st[ne[v]];
				q.push(v);
			}
		}
	}
}

void solve() {
	int T = 1;
	while (cin >> n, n) {
		mem(f, 0x3f), mem(tr, 0), mem(ne, 0), mem(st, 0);
		idx = 0;
		
		for (int i = 0; i < n; i ++ ) {
			cin >> str;
			insert();
		}
		
		build();
		
		cin >> str + 1;
		int m = strlen(str + 1);
		f[0][0] = 0;
		for (int i = 0; i < m; i ++ ) {
			for (int j = 0; j < idx; j ++ ) {
				for (int k = 0; k < 4; k ++ ) {
					int t = get(str[i + 1]);
					int p = tr[j][k];
					if (!st[p]) {
						f[i + 1][p] = min(f[i + 1][p],
						f[i][j] + (t == k ? 0 : 1));
					}
				}
			}
		}
		
		int res = INF;
		for (int i = 0; i <= idx; i ++ ) res = min(res, f[m][i]);
		
		printf("Case %d: %d\n", T ++ , (res == INF ? -1 : res));
	}
}

int main() {
	IOS;
	
	solve();
	
	return 0;
}
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119