「POJ 3691」DNA repair - AC 自动机 + DP

发表于 分类于 ， 阅读次数： Disqus：

题意描述

POJ 链接

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

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

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

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

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

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

解题思路

本题存在多个字符串的匹配问题，可以考虑使用 AC 自动机解决。我们可以先将所有的致病片段都插入 AC 自动机中，并将致病基因字符串作标记。注意如果一个字符串的子串是致病基因，则这个字符串必为致病基因。故构建 AC 自动机时需要看 fail 所指的字符串是否为致病基因，然后更新该节点的信息。即 c->isWord |= c->fail->isWord。

接下来我们需要求解问题。由于求的是最小修改次数，可考虑 DP 解决。由于可使用 AC 自动机匹配是否有子串为致病基因，我们可以考虑以 AC 自动机匹配时的状态为维度进行 DP。

对于需要修复的 DNA 片段 \(s\)，我们可定义 \(f_{i, j}\) 为遍历到 \(s_i\)，且达到位于 AC 自动机 \(j\) 节点的状态时需要最小修改次数。对于可从 \(j\) 到达的状态 \(k\)，我们设 \(l\) 为 \(k\) 所在的字符。设属于致病基因的字符串所代表的节点的集合为 \(\text{Disease}\)，于是有下列转移方程：

\[ f_{i + 1, k} = \begin{cases} \min\{ f_{i + 1, k}, f_{i, j} + [s_{i + 1} = l] \} & k \notin \text{Disaese} \\ \infty & k \in \text{Disease} \end{cases} \]

接下来我们只需要初始化 \(f_{i, j} = \begin{cases} 0 & i = 0 \wedge j = \text{root} \\ \infty & otherwise. \end{cases}\)，然后求解即可。设 AC 自动机中所有点的集合为 \(\text{AC}\)，最终答案则为 \(\min\limits_{i \in \text{AC}}{f_{m, i}}\)。

代码演示

由于这里需要枚举 AC 自动机中的所有节点，故使用内存池编写。

POJ 不支持 C++11 真 TM 烦

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
#include <cstdio>
#include <cstring>
#include <climits>
#include <vector>
#include <queue>
#include <new>

const int MAXN = 1000;
const int CHARSET_SIZE = 4;

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

struct Trie {
    struct Node {
        int id;
        Node *c[CHARSET_SIZE], *fail;
        bool isWord;

        Node(bool isWord = false) : fail(NULL), isWord(isWord) { 
            for (int i = 0; i < CHARSET_SIZE; i++) c[i] = NULL;
        }

        Node(int id, bool isWord = false) : id(id), fail(NULL), isWord(isWord) {
            for (int i = 0; i < CHARSET_SIZE; i++) c[i] = NULL;
        }
    } *root, _pool[MAXN + 1], *_curr;

    int idx;

    Trie() : root(_pool), _curr(_pool + 1), idx(0) { root->id = 0; }

    Node *insert(const char *begin, const char *end) {
        Node **v = &root;
        for (const char *p = begin; p != end; p++) {
            if (!*v) *v = new (_curr++) Node(++idx);
            v = &(*v)->c[get(*p)];
        }
        if (!*v) *v = new (_curr++) Node(++idx);
        (*v)->isWord = true;
        return *v;
    }

    void build() {
        std::queue<Node *> q;
        q.push(root);
        root->fail = root;
        while (!q.empty()) {
            Node *v = q.front();
            q.pop();

            for (int i = 0; i < CHARSET_SIZE; i++) {
                Node *&c = v->c[i];

                if (!c) {
                    c = v == root ? root : v->fail->c[i];
                    continue;
                }
                Node *u = v->fail;

                c->fail = v != root && u->c[i] ? u->c[i] : root;

                q.push(c);

                c->isWord |= c->fail->isWord;
            }
        }
    }
};

int main() {
    int n, counts = 0;

    while (scanf("%d", &n) != EOF && n) {
        static char s[MAXN + 1];
        Trie t;
        std::vector<Trie::Node *> node(n);
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            node[i] = t.insert(s, s + strlen(s));
        }

        t.build();

        scanf("%s", s);
        int m = strlen(s);

        std::vector< std::vector<int> > f(m + 1, std::vector<int>(t.idx + 1, INT_MAX));
        f[0][0] = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j <= t.idx; j++) {
                if (f[i][j] != INT_MAX) {
                    for (int k = 0; k < CHARSET_SIZE; k++) {
                        int l = get(s[i]) != k;
                        Trie::Node *p = t._pool[j].c[k];
                        if (!p->isWord) f[i + 1][p->id] = std::min(f[i + 1][p->id], f[i][j] + l);
                    }
                }
            }
        }

        int ans = INT_MAX;
        for (int i = 0; i <= t.idx; i++) ans = std::min(ans, f[m][i]);

        printf("Case %d: %d\n", ++counts, ans == INT_MAX ? -1 : ans);
    }

    return 0;
}