题目分析

这道题是一个字符串处理相关的动态规划问题，结合了AC自动机算法。题目要求我们在一个DNA序列（由A、C、G、T四种字符组成）中，找出最少需要改变多少个字符，使得处理后的序列中不包含给定的任何一个模式串作为子串。

解题思路

1. 构建AC自动机：首先将所有模式串插入到AC自动机中，构建失败指针，以便高效地进行多模式串匹配。
2. 动态规划（DP）：使用DP数组f[i][j]表示处理前i个字符，当前在AC自动机的节点j时，最少需要改变的字符数。
3. 状态转移：对于每个位置的字符，尝试将其改为A、C、G、T四种字符之一，根据AC自动机的转移规则更新状态，并记录最少改变次数。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 2100;
int id, ch[N][5], ne[N], ed[N], ys[150];
char str[N];

void ins(char *s) {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int j = ys[s[i]];
        if (ch[p][j] == 0) ch[p][j] = ++id;
        p = ch[p][j];
    }
    ed[p]++;
}

void build() {
    queue<int> Q;
    for (int i = 1; i <= 4; ++i)
        if (ch[0][i]) Q.push(ch[0][i]);
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();
        for (int i = 1; i <= 4; ++i) {
            int y = ch[x][i];
            if (y == 0)
                ch[x][i] = ch[ne[x]][i];
            else {
                int k = ne[x];
                while (ch[k][i] == 0 && k) k = ne[k];
                ne[y] = ch[k][i];
                if (ed[ne[y]] > 0) ed[y] = 1;
                Q.push(y);
            }
        }
    }
}

int f[1100][2100], n;

int main() {
    int T = 0;
    ys['A'] = 1; ys['C'] = 2; ys['G'] = 3; ys['T'] = 4;
    while (scanf("%d", &n) != EOF && n) {
        id = 0;
        memset(ch, 0, sizeof(ch));
        memset(ed, 0, sizeof(ed));
        for (int i = 1; i <= n; i++) {
            scanf("%s", str);
            ins(str);
        }
        memset(ne, 0, sizeof(ne));
        build();
        
        scanf("%s", str + 1);
        int len = strlen(str + 1);
        const int INF = 0x3f3f3f3f;
        memset(f, 63, sizeof(f));
        f[0][0] = 0;
        
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= id; j++) {
                if (f[i][j] == INF) continue;
                for (int k = 1; k <= 4; k++) {
                    int y = ch[j][k];
                    if (ed[y]) continue;
                    f[i + 1][y] = min(f[i + 1][y], f[i][j] + (ys[str[i + 1]] != k));
                }
            }
        }
        
        int ans = INF;
        for (int i = 0; i <= id; i++)
            ans = min(ans, f[len][i]);
        printf("Case %d: %d\n", ++T, ans == INF ? -1 : ans);
    }
    return 0;
}

代码解释

1. AC自动机构建：

   • ins函数：将模式串插入到AC自动机的Trie树中，标记每个模式串的结束节点。
   • build函数：构建失败指针（BFS实现），并将结束节点的标记传递给其失败节点的子节点，确保一旦匹配到模式串，所有相关节点都被标记。

2. 动态规划：

   • f[i][j]表示处理前i个字符，当前在AC自动机节点j时的最少修改次数。
   • 初始状态f[0][0] = 0表示未处理任何字符，在根节点，修改次数为0。
   • 状态转移：对于每个位置的字符，尝试改为A、C、G、T四种字符，根据AC自动机的转移规则找到下一个节点，若该节点标记为匹配到模式串则跳过，否则更新DP状态。

3. 结果计算：处理完所有字符后，在所有可能的AC自动机节点中取最小值，即为最少修改次数；若无法避免匹配到模式串，则输出-1。