POJ 3691 DNA Repair：AC 自動機 + DP 求最少修改字符

問題描述

給定 N (≤ 50) 個致病 DNA 片段（模式串，長度 ≤ 20，字符集 {A,G,C,T}）和一條待修復 DNA 主串（長度 ≤ 1000）。允許修改主串中的字符，求最少修改次數使得修復後的主串不包含任何模式串作為子串。無解輸出 -1。

核心思想：AC 自動機狀態機 + 動態規劃

1. 構建 AC 自動機：將所有模式串插入 Trie，構建失配指針（fail 指針）與輸出鏈接，標記每個節點是否為模式串結尾（或通過 fail 指向模式串結尾）。
2. 狀態定義：dp[i][u] = 處理完主串前 i 個字符，自動機處於節點 u 時的最少修改次數。
3. 狀態轉移：對位置 i+1，枚舉四個可能字符 ch ∈ {A,G,C,T}：
   • 從節點 u 沿 ch 轉移到 v = go(u, ch)。
   • 若 v 為「危險節點」（即該節點或其 fail 鏈上有模式串結尾），則不可轉移（會形成禁用子串）。
   • 代價 = dp[i][u] + (ch != S[i+1] ? 1 : 0)。
   • dp[i+1][v] = min(dp[i+1][v], 代價)。
4. 初始與答案：dp[0][0] = 0，其餘 INF。答案為 min_u dp[L][u]（L 為主串長）。若為 INF 輸出 -1。

關鍵細節

• 危險節點標記：構建 fail 指針時，若 fail[v] 為危險節點，則 v 也標記為危險（遞推傳播）。
• 字符映射：將 {A,G,C,T} 映射為 0..3，加速轉移。
• 空間優化：滾動數組 dp[2][MAX_NODES]，因只依賴上一行。

複雜度分析

• 節點數 ≤ 總模式串長度 ≤ 50 × 20 = 1000。
• 時間：O(L × 節點數 × 4) ≈ 1000 × 1000 × 4 = 4×10⁶，極快。
• 空間：O(節點數) ≈ 1000。

參考代碼框架

struct ACAutomaton {
    static const int MAXN = 1010, CH = 4;
    int ch[MAXN][CH], fail[MAXN], danger[MAXN], sz;
    int idx(char c) { return c=='A'?0:c=='G'?1:c=='C'?2:3; }
    void init() { sz = 1; memset(ch[0], 0, sizeof ch[0]); danger[0]=0; }
    void insert(const char *s) {
        int u = 0;
        for (; *s; s++) {
            int c = idx(*s);
            if (!ch[u][c]) {
                ch[u][c] = sz;
                memset(ch[sz], 0, sizeof ch[sz]);
                danger[sz] = 0;
                sz++;
            }
            u = ch[u][c];
        }
        danger[u] = 1; // 模式串結尾
    }
    void build() {
        queue q;
        for (int c = 0; c < CH; c++)
            if (ch[0][c]) q.push(ch[0][c]);
            else ch[0][c] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            danger[u] |= danger[fail[u]]; // 傳播危險標記
            for (int c = 0; c < CH; c++) {
                if (ch[u][c]) {
                    fail[ch[u][c]] = ch[fail[u]][c];
                    q.push(ch[u][c]);
                } else {
                    ch[u][c] = ch[fail[u]][c];
                }
            }
        }
    }
} ac;

int dp[2][1010];
void solve() {
    int L = strlen(str+1);
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    for (int i = 0; i < L; i++) {
        int cur = i&1, nxt = (i+1)&1;
        memset(dp[nxt], 0x3f, sizeof dp[nxt]);
        for (int u = 0; u < ac.sz; u++) if (dp[cur][u] < INF) {
            for (int c = 0; c < 4; c++) {
                int v = ac.ch[u][c];
                if (ac.danger[v]) continue;
                int cost = dp[cur][u] + (c != ac.idx(str[i+1]));
                dp[nxt][v] = min(dp[nxt][v], cost);
            }
        }
    }
    int ans = INF;
    for (int u = 0; u < ac.sz; u++) ans = min(ans, dp[L&1][u]);
    if (ans == INF) ans = -1;
    printf("Case %d: %d\n", ++caseNum, ans);
}

總結

本題是「多模式串匹配 + 序列編輯最小代價」的經典組合。AC 自動機將多模式匹配轉化為確定性有限自動機（DFA），DP 在 DFA 上尋找避開終止狀態的最短路徑。掌握「Trie + Fail + DP」三步曲，可解決大類相似問題（如 HDU 2222、POJ 2778 等）。