python/TangDou/AcWing/Statemachine/1053.md

##AcWing 1053. 修复DNA

一、题目描述

生物学家终于发明了修复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

输入样例：

2
AAA
AAG
AAAG    
2
A
TG
TGAATG
4
A
G
C
T
AGT
0

输出样例：

Case 1: 1
Case 2: 4
Case 3: -1

二、前导知识

AC自动机

AcWing 1282. 搜索关键词

本题是多模式串，单文本串的问题，所以将不允许出现的模板串建AC自动机，在每个串末尾打一个标记。

三、解题思路

构建AC自动机，然后开始动态规划即可。

Q:修复DNA是怎么个修复法,为什么引入AC自动机后就能使得修复DNA的修改量最小呢？

答： ① AC自动机 不管怎样，你得首先知道现在你的文本串中是不是有了病毒DNA片段，要是有了这样的片断，你还不知道，那就没的玩了，更不用谈怎么改了吧？

那你怎么才能快速知道你的文本串中是不是有了病毒DNA片段呢？而且 这些片断可是不止一组 啊！噢，以前学习过的 AC自动机 可以解决这个问题。

构建AC自动机是顺理成章的。构建目的：快速判断目前的文本串中是不是存在病毒DNA片断。

② 状态表示 在引入了AC自动机后，我们手中现在就有两个东西，一个是文本大串，另一个就是AC自动机，它们肯定要结合起来才能有用吧？ AC自动机的知识告诉我们，它是通过模式串+Trie树+Fail指针进行构建的（如果你这里不明白，先再看下AcWing 1282 搜索关键词 吧） 然后，把长串开始逐个枚举字符，并在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嘛：

4
A
G
C
T
AGT

A,G,C,T全是病毒片断，把你的路全堵上。

⑧ 为什么cnt[c] |= cnt[ne[c]];,这是啥意思？ 举个栗子秒懂:

四、Code

#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;
}