|
|
|
|
##[$AcWing$ $1053$. 修复$DNA$](https://www.acwing.com/problem/content/1055/)
|
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
生物学家终于发明了修复$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≤N≤50$
|
|
|
|
|
|
|
|
|
|
**输入样例**:
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
2
|
|
|
|
|
AAA
|
|
|
|
|
AAG
|
|
|
|
|
AAAG
|
|
|
|
|
2
|
|
|
|
|
A
|
|
|
|
|
TG
|
|
|
|
|
TGAATG
|
|
|
|
|
4
|
|
|
|
|
A
|
|
|
|
|
G
|
|
|
|
|
C
|
|
|
|
|
T
|
|
|
|
|
AGT
|
|
|
|
|
0
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
**输出样例**:
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
Case 1: 1
|
|
|
|
|
Case 2: 4
|
|
|
|
|
Case 3: -1
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
### 二、前导知识
|
|
|
|
|
|
|
|
|
|
#### $AC$自动机
|
|
|
|
|
[$AcWing$ $1282$. 搜索关键词](https://www.cnblogs.com/littlehb/p/15861241.html)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
本题是**多模式串,单文本串**的问题,所以**将不允许出现的模板串建$AC$自动机**,在每个串末尾打一个标记。
|
|
|
|
|
|
|
|
|
|
### 三、解题思路
|
|
|
|
|
|
|
|
|
|
构建$AC$自动机,然后开始动态规划即可。
|
|
|
|
|
|
|
|
|
|
#### $Q$:修复$DNA$是怎么个修复法,为什么引入$AC$自动机后就能使得修复$DNA$的修改量最小呢?
|
|
|
|
|
**答**:
|
|
|
|
|
① **$AC$自动机**
|
|
|
|
|
不管怎样,你得首先知道现在你的文本串中是不是有了病毒$DNA$片段,要是有了这样的片断,你还不知道,那就没的玩了,更不用谈怎么改了吧?
|
|
|
|
|
|
|
|
|
|
那你怎么才能快速知道你的文本串中是不是有了病毒$DNA$片段呢?而且 **这些片断可是不止一组** 啊!噢,以前学习过的 **$AC$自动机** 可以解决这个问题。
|
|
|
|
|
|
|
|
|
|
构建$AC$自动机是顺理成章的。构建目的:**快速判断目前的文本串中是不是存在病毒$DNA$片断**。
|
|
|
|
|
|
|
|
|
|
② **状态表示**
|
|
|
|
|
在引入了$AC$自动机后,我们手中现在就有两个东西,一个是文本大串,另一个就是$AC$自动机,它们肯定要结合起来才能有用吧?
|
|
|
|
|
$AC$自动机的知识告诉我们,它是通过模式串+$Trie$树+$Fail$指针进行构建的(如果你这里不明白,先再看下[<b>$AcWing$ $1282$ 搜索关键词</b>](https://www.cnblogs.com/littlehb/p/15861241.html) 吧)
|
|
|
|
|
然后,把长串开始逐个枚举字符,并在$AC$自动机中匹配相应的结点,它们两是这样关联在一起的啊!所以状态定义的形式就呼之预出了!
|
|
|
|
|
|
|
|
|
|
$\large f[i][j]$:$DNA$长串扫描到第$i$个字母,且当前走到了$trie$里面的第$j$个节点的所有操作方案。
|
|
|
|
|
|
|
|
|
|
值是什么呢?面向答案编程嘛,**定义为最少的修改数量**
|
|
|
|
|
|
|
|
|
|
**③ 状态转移**
|
|
|
|
|
状态转移这玩意,一般都是找一个最普通的状态位置,比如$(i,j)$,别靠左,别靠右,别靠上,别靠下,就认为在中间,这样叫 **最普通** ,对了,还得加一个限制:**符合题意**。
|
|
|
|
|
|
|
|
|
|
假设$f[i][j]$已经取得最小代价值,那么它将如何转移呢?
|
|
|
|
|
首先要想明白这是啥意思:就是已经成功走完了前$i$个字符,$Trie$中游标位置是$j$,现在已经取得了最小修改代价值$f[i][j]$,而且,目前没有出现过病毒片断。
|
|
|
|
|
|
|
|
|
|
考虑下一个可能的变化: 变化肯定是依托于文本串再读入一位吧,也就是$i+1$位,它变化了,那$j$怎么对应它的变化呢?
|
|
|
|
|
|
|
|
|
|
这个$i+1$位,它有两种可能:
|
|
|
|
|
- **需要修改**(有$3$种改法)
|
|
|
|
|
- **不需要修改**
|
|
|
|
|
|
|
|
|
|
**啥时候需要修改,啥时候不需要修改呢?**
|
|
|
|
|
为了尽量让修改次数小,那么当然是如果能不修改就不修改,实在不行再去修改。这么想就是贪心思路了,只能是局部最优,不是全局最优,**这样想并不对**。
|
|
|
|
|
|
|
|
|
|
**为啥呢?**
|
|
|
|
|
你想啊,如果现在改了,是增加了一次修改次数,但这条路线的后面可能就不用再修改,整不好还节约资源了呢。
|
|
|
|
|
|
|
|
|
|
**那咋办?**
|
|
|
|
|
这就是一个动态规划的过程,你要把所有可能的前序都准备好,思考他们改与不改的所有可能性,综合决策呗。
|
|
|
|
|
|
|
|
|
|
也就是当前在$Trie$树中的$j$节点上,有四条出边$AGCT$,我们要避开那些走完了就出现病毒片段终点的位置,走可以走的点,但走的代价是不相同的。
|
|
|
|
|
|
|
|
|
|
**状态转移**
|
|
|
|
|
回到理性思考:$f[i+1][?]$一定与$f[i][j]$之间存在$DP$关系,我们来思考一下第二维的转移关联关系:
|
|
|
|
|
也就是$j$可以转移成哪些$x$?肯定是$AGCT$四选一啊,也就是不改走其中之一,改的话走另三个呗。
|
|
|
|
|
|
|
|
|
|
**那代价呢?**
|
|
|
|
|
代价不就是修改的数量吗?如果$str[i+1]$和出边一致,那么代价就是$0$,如果不一致,就表示需要修改一下当前字符,代价就是$1$。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
④ **初始化**
|
|
|
|
|
- 预求最小,先设最大,$INF$预备上!
|
|
|
|
|
- 不能都是$INF$,思考一下起点,当然是$f[0][0]$,表示$DNA$还没有开始枚举,$Trie$树还处在$root$位置,此时的修改代价当然是$0$了,其它的靠递推吧
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
⑤ **答案在哪里?**
|
|
|
|
|
当$DNA$文本串走完全程,$Tire$树中的节点可以在任意位置,需要一次循环,找到$f[m][i]$的$PK$最小值即可。
|
|
|
|
|
|
|
|
|
|
⑥ **为什么枚举答案时,$Trie$树中节点要包含$0$号?**
|
|
|
|
|
答:因为可能是匹配最后一个字符中,由$fail$指针跳过来的,也是合法数据啊。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
⑦ **什么情况下没有最小值呢?不是应该都有最小值吗?**
|
|
|
|
|
举个栗子秒懂:就是用例$3$嘛:
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
4
|
|
|
|
|
A
|
|
|
|
|
G
|
|
|
|
|
C
|
|
|
|
|
T
|
|
|
|
|
AGT
|
|
|
|
|
```
|
|
|
|
|
$A,G,C,T$全是病毒片断,把你的路全堵上。
|
|
|
|
|
|
|
|
|
|
**⑧ 为什么`cnt[c] |= cnt[ne[c]];`,这是啥意思?**
|
|
|
|
|
举个栗子秒懂:
|
|
|
|
|
|
|
|
|
|

|
|
|
|
|
|
|
|
|
|
### 四、$Code$
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
using namespace std;
|
|
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
|
|
const int N = 1010; // 致病DNA片段的数量上限50,每个DNA片段的长度不超过20,所以Trie树的结点个数最多不超过50*20=1000个节点
|
|
|
|
|
|
|
|
|
|
int n, m;
|
|
|
|
|
int tr[N][4], cnt[N], idx; // Trie树,每个节点最多四条出边ATGC,映射就0123,cnt表示每个节点为结尾的结束标识,idx:配合创建Trie树的导航员
|
|
|
|
|
int q[N], ne[N]; // AC自动机需要的队列数组,失配指针数组,ne[u]描述在u结点失配时,找到root~u的最长后缀相同的最长前缀root~v
|
|
|
|
|
char str[N]; // 第一轮当作模板串的录入存储器,完成构建Trie树后,第二轮当做文本串的存储器
|
|
|
|
|
int f[N][N]; // f[i][j]:DNA扫描到第i个字母,且当前走到了trie里面的第j个节点 的 所有操作方案中,最少的修改数量
|
|
|
|
|
|
|
|
|
|
int get(char c) {
|
|
|
|
|
if (c == 'A') return 0;
|
|
|
|
|
if (c == 'T') return 1;
|
|
|
|
|
if (c == 'G') return 2;
|
|
|
|
|
return 3;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
void insert() { // 利用模板串构建Trie树
|
|
|
|
|
int p = 0;
|
|
|
|
|
for (int i = 0; str[i]; i++) {
|
|
|
|
|
int t = get(str[i]);
|
|
|
|
|
if (tr[p][t] == 0) tr[p][t] = ++idx;
|
|
|
|
|
p = tr[p][t];
|
|
|
|
|
}
|
|
|
|
|
cnt[p] = 1; // 记录结束标识
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// 构建AC自动机
|
|
|
|
|
void bfs() {
|
|
|
|
|
int hh = 0, tt = -1;
|
|
|
|
|
for (int i = 0; i < 4; i++) // 利用bfs进行构建,把第一层的节点入队列
|
|
|
|
|
if (tr[0][i]) q[++tt] = tr[0][i];
|
|
|
|
|
|
|
|
|
|
while (hh <= tt) {
|
|
|
|
|
int p = q[hh++];
|
|
|
|
|
for (int i = 0; i < 4; i++) { // 尝试四个出边
|
|
|
|
|
int &c = tr[p][i];
|
|
|
|
|
if (!c)
|
|
|
|
|
c = tr[ne[p]][i];
|
|
|
|
|
else {
|
|
|
|
|
ne[c] = tr[ne[p]][i];
|
|
|
|
|
q[++tt] = c;
|
|
|
|
|
// c是不是终止节点,有两个判断来源:
|
|
|
|
|
// 1、自己本身就是模示串A的终点
|
|
|
|
|
// 2、它的失配指针指向的结点是模示串B的终点
|
|
|
|
|
cnt[c] |= cnt[ne[c]];
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
int T = 1;
|
|
|
|
|
while (scanf("%d", &n), n) {
|
|
|
|
|
memset(tr, 0, sizeof tr);
|
|
|
|
|
memset(cnt, 0, sizeof cnt);
|
|
|
|
|
memset(ne, 0, sizeof ne);
|
|
|
|
|
idx = 0;
|
|
|
|
|
|
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
|
|
|
scanf("%s", str);
|
|
|
|
|
insert();
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
bfs();
|
|
|
|
|
|
|
|
|
|
// Q:为什么不直接从索引0开始读入呢?
|
|
|
|
|
// 答:你可以尝试以索引0开始读入,你会发现,后面的状态转移方程就无法使用f[i-1][j],因为数组下标越界了~哈哈,看来啊,都是先有状态转移方程,后有初始值,枚举序等东西
|
|
|
|
|
scanf("%s", str + 1);
|
|
|
|
|
m = strlen(str + 1);
|
|
|
|
|
|
|
|
|
|
memset(f, 0x3f, sizeof f); // 初始化动态规划数组,预求最小,先设最大
|
|
|
|
|
f[0][0] = 0; // 匹配了前0个字符,在Trie树中的节点号是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]) != k;
|
|
|
|
|
int p = tr[j][k];
|
|
|
|
|
if (!cnt[p]) f[i + 1][p] = min(f[i + 1][p], f[i][j] + t);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// 找出最小值
|
|
|
|
|
int res = INF;
|
|
|
|
|
for (int i = 0; i <= idx; i++) res = min(res, f[m][i]);
|
|
|
|
|
|
|
|
|
|
// 没有最小值,返回-1
|
|
|
|
|
if (res == INF) res = -1;
|
|
|
|
|
printf("Case %d: %d\n", T++, res);
|
|
|
|
|
}
|
|
|
|
|
return 0;
|
|
|
|
|
}
|
|
|
|
|
```
|