AcWing 1053 修复DNA

题目传送门

零、参考文章

这题的做法为\(AC\)自动机和动态规划。

一、前导知识

1、KMP解决的是什么问题？

一个模板串，一个文本串，问模板串是不是在文本串中出现过，如果是，都是在哪些位置出现的，出现过几次之类。

2、KMP 的next数组记的是什么东西？

是最长公共前后缀的索引位置，在失配时，可以不用从头来过，通过预处理的\(next\)数组以最小代价获得再次匹配的机会。如果多次尝试仍然无法继续匹配，只能回退到字符串开头，从下一个位置继续重新尝试。

3、本题可以使用KMP处理吗？

那就是不断的用每个模板串创建\(ne\)数组，然后一个个跑\(KMP\)，看了一下大神们的分析，\(KMP\)的时间复杂度：$$O(len(s)*n+\sum_{i=1}^{n}len(t[i]))$$
\(AC\)自动机的时间复杂度：$$O(len(s)+\sum_{i=1}^{n}len(t[i]))$$
这两者对比，去掉了一个常数\(n\),如果文本串足够长的话，那么性能差距的就非常大了。

4、AC自动机解决的是什么问题？

给定\(n\)个模式串和\(1\)个文本串，求有多少个模式串在文本串里出现过。

5、AC自动机的感性认识

6、失配指针的含义是什么？

如果一个点\(i\)的失配指针指向\(j\)。那么\(root\)到\(j\)的字符串是\(root\)到\(i\)的字符串的一个后缀，而且是所有\(Trie\)树中最长的的缀。为啥强调最长呢？因为超长越划算，使得文本串回退最少，联想一下\(KMP\)吧。

7、怎么样求失配指针？

设点\(i\)的父亲\(p\)的失配指针指的是\(ne[p]\)，如果\(ne[p]\)有和\(i\)值相同的儿子\(j\)，那么\(i\)的失配指针就指向\(j\)。

在处理\(i\)的情况必须要先处理好\(p\)的情况，求失配指针使用\(bfs\)来实现。

无论\(ne[p]\)存不存在和\(i\)值相同的儿子\(j\)，都可以将\(i\)的失配指针指向\(j\)。因为在处理\(i\)的时候\(j\)已经处理好了,如果有就抄过来，如果没有大不了是\(0\),也是正确的。

8、AC自动机的创建过程是什么？

（1）将多个模式串建成\(Trie\)树。
（2）利用\(bfs\)为每个节点建立失配指针\(ne\)数组。

二、AC自动机分析

具体来说，我们先将不允许出现的短串建\(AC\)自动机，在每个串末尾打一个标记(注意：在当\(ne[p]\),被打标记后，\(p\)上也要打标记，因为从根到\(ne[p]\)所组成的字符串是从根到\(p\)所组成的字符串的后缀）

三、动态规划分析

我们设置\(f[i][j]\)表示处理(修改或不修改)完文本串的前\(i\)个字符，匹配到\(AC\)自动机中的\(j\)号节点的方案中修改字符数量的最小值为多少。
(也就是从根到\(j\)所组成的字符串为长串前\(i\)个字符所组成的字符串的后缀)。(不能匹配到打过标记的点)

四、实现代码

#include 

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1010; //50*20+10

//Trie树
int trie[N][4]; //A:0 G:1 C:2 T:3,4个足够
int st[N];      //i结点是否是某个模板串的终点
int idx;        //记数器

//AC自动机
queue q;
//AC自动机的fail(失配指针)数组
int ne[N];

//f[i,j]前i个字母，当前走到了AC自动机中的第j个位置的所有操作方案中最少修改的字母数量
int f[N][N];

//通过字符计算数组下标，构建Trie的辅助函数
int get(char c) {
    if (c == 'A') return 0;
    if (c == 'T') return 1;
    if (c == 'G') return 2;
    return 3;
}

//创建Tire树
//用trie树对n个模板串做预处理
void insert(string str) {
    int p = 0;
    for (int i = 0; i < str.size(); i++) {
        //计算str[i]是对应的哪个索引号的边
        int t = get(str[i]);
        //如果以前没有分配过节点，那么需要给这个位置分配一个新的节点号
        if (!trie[p][t]) trie[p][t] = ++idx;
        //走进去,准备迎接下一个str[i]
        p = trie[p][t];
    }
    //在每一个模板串的末尾打标记, 标明长串不能匹配到trie树中的该节点;
    //本来这是用来记录模板串个数的，本题目中不需要个数，就是一个结束标识
    st[p] = 1;
}

//计算失配数组,构建AC自动机
void build() {
    //一级节点入队列
    for (int i = 0; i < 4; i++)
        if (trie[0][i]) q.push(trie[0][i]);
    //扩散
    while (!q.empty()) {
        //从队列中取出一个节点
        int t = q.front();
        q.pop();//出队列
        //遍历所有可能的子节点:A-0,G-1,C-2,T-3
        for (int i = 0; i < 4; i++) {
            //Trie树中的p的子节点x
            int p = trie[t][i];
            //第i个子节点存在
            if (p) {
                ne[p] = trie[ne[t]][i];
                q.push(p);
                /*
                下面这句不是AC自动机标准模板的内容，是因为本题要求的是不能包含模板串，
                如果n个模板串之间存在包含关系(即一个串可能是另一个串的子串)
                当最大前缀的末尾（ne[x]）被打上标记了的话,表示这个节点ne[x]是某个模板串的终点。
                这样的节点是不能进行匹配的，现在后缀的末尾(x)也要被打上标记,标识这个节点也是不可以走的。
                */
                //如果自己的标志是true,那么处理完还是true.
                //如果父节点的失配节点的标志是true,地么处理完自己的标志也是true.
                st[p] |= st[ne[p]];
            } else
                trie[t][i] = trie[ne[t]][i];
        }
    }
}

int main() {
    int n;              //n个模式串
    int T = 1;          //第几次输入，为了配合Case %d
    //字符串变量
    string str;

    while (cin >> n && n) { //当输入的n为0时，就停止下来
        //因为有多轮，所以每一轮都需要清空重来
        memset(trie, 0, sizeof trie);
        memset(st, 0, sizeof st);
        memset(ne, 0, sizeof ne);
        memset(f, 0x3f, sizeof f); //预求最小，先设最大
        idx = 0;                               //计数指针也需要回0

        //输入多个模式串，构建Trie树
        for (int i = 1; i <= n; i++) {
            cin >> str;
            insert(str);
        }

        //构建AC自动机
        build();

        //读入字符串
        cin >> str;
        //一个字母都没有，状态显然是0
        f[0][0] = 0;
        //枚举每一个字母
        for (int i = 0; i < str.size(); i++)
            //枚举AC自动机的每一个节点
            for (int j = 0; j <= idx; j++)
                //枚举当前步骤在AC自动机中选择哪一个字母
                for (int k = 0; k < 4; k++) {
                    //在下一个是字母k时，AC自动机会跳到哪个位置
                    int p = trie[j][k];
                    //如果第k步选择的字符和DNA片段的相同，说明这一步没有修改，代价为0，反之为1。
                    int t = get(str[i]) == k ? 0 : 1;
                    //表示下一步必须选择没被标记的点转移，代价为0或1取决于这一步选择的字符。
                    //判断一下p这个位置是不是安全节点，只有st[p]==0表示这个点不是某个模式串的终点，就是说不包含给定的所有模式串,才能走
                    if (!st[p]) f[i + 1][p] = min(f[i + 1][p], f[i][j] + t);
                }
        //预求最小，先设最大
        int res = INF;
        //在走完str.size()个字母的情况下，当前走到了AC自动机中的第i个位置时的值最小
        for (int i = 0; i <= idx; i++) res = min(res, f[str.size()][i]);
        //如果没有被修改过，返回-1
        if (res == INF) res = -1;
        printf("Case %d: %d\n", T++, res);
    }
    return 0;
}

五、不好理解的地方

在上面的实现代码模板中：

• 如果子节点存在：
  ne[x] = son[ne[p]][i] 连在当前节点的失配节点的第i条边连接的节点上，相当于一个指针。这是实现类似\(KMP\)的基本思路。但问题是这个位置真的存在第i条边连接的节点吗？如果存在，当然就接的上，如果不存在，就是0,也就是直接退回到根，也是一样的。

• 如果子节点不存在：
  为什么节点不存在了，还需要写代码吗？想想我们的初衷：

构造失败指针的过程概括起来就一句话：设这个节点上的字母为\(C\)，沿着它父亲节点的失败指针走，直到走到一个节点，它的子结点中也有字母为\(C\)的节点。然后把当前节点的失败指针指向那个字母也为\(C\)的儿子。如果一直走到了\(root\)都没找到，那就把失败指针指向\(root\)。

其实，这是一个不断回溯的过程，在代码实现时，我们一般采用的是\(while\)循环或者递归来不断的向上进行查找，但这样效率上会差一些。有没有更好的办法呢？这得益于我们采用的\(bfs\)策略，我们通过自顶向下的覆盖方式，将上面的信息继承到下面去，换句话说，就是不用儿子去找父亲问，父亲再找爷爷问，这太麻烦了，而且爷爷将答案准备好，告诉父亲，父亲将答案保存好，儿子可以直接获取到。这时就不再是一个\(Trie\)树了，而是一个\(Trie\)图了。