POJ 3691 DNA Repair：AC 自動機 + DP 求最小修改次數

問題建模

給定長度 ≤ 1000 的 DNA 序列（A,C,G,T），及若干禁止模式串。可修改序列中任意字符（代價 1），求使序列不包含任何禁止模式的最小修改代價。

AC 自動機構建

• 將所有禁止串插入 Trie，標記結尾節點 flag=1。
• 構建失敗指針 fail，並傳播 flag：若節點的 fail 祖先有 flag，則它也視為危險（不可進入）。

DP 定義

dp[i][u]：處理前 i 字符，自動機狀態為 u 的最小修改數。
初始 dp[0][0] = 0，其餘 INF。
轉移：對每個狀態 u，嘗試 4 種字符 c：

• 若 next[u][c] 存在且安全 → dp[i+1][v] = min(dp[i+1][v], dp[i][u] + (c==s[i]?0:1))
• 若不存在，沿 fail 跳轉找到安全節點 v → 同樣更新

關鍵函數

bool safe(int u) { // 遞歸判斷 u 及其 fail 鏈是否無 flag
    if (u == -1) return true;
    if (trie[u].flag) return false;
    return safe(trie[u].fail);
}
int trans(int u, int c) { // 返回從 u 讀 c 到達的安全節點，或 -1
    if (u == -1) return 0;
    if (trie[u].next[c] != -1) {
        int v = trie[u].next[c];
        return (trie[v].flag || !safe(v)) ? -1 : v;
    }
    return trans(trie[u].fail, c);
}

複雜度

狀態數 ≤ 總模式長度 ≤ 1000。DP O(L × 狀態數 × 4) ≈ 4×10⁶，極快。