POJ 3691：DNA repair——AC 自動機 + DP 求最少修改

題目描述

給定 N 個致病 DNA 片段（長 ≤ 20）和一條待修復 DNA（長 ≤ 1000），修改最少字符使其不含任何致病片段。字符集 {A,C,G,T}。

解法：Aho-Corasick 自動機 + DP

1. 將致病片段構建 AC 自動機，標記終結節點及其 fail 鏈上的終結節點為「危險」
2. DP 狀態：dp[i][u] = 處理前 i 字符，自動機狀態為 u 的最少修改數
3. 轉移：對每個可能字符 c ∈ {A,C,G,T}，從 u 沿 c 轉移到 v，若 v 危險則跳過，否則 dp[i+1][v] = min(dp[i+1][v], dp[i][u] + (c != s[i]))

關鍵結構

struct Node {
    int next[4], fail;
    bool danger;
} trie[2100]; // 總節點 ≤ 50×20 = 1000
int dp[1005][2100];

C++ 實現（核心）

int char_id(char c) { return c=='A'?0:c=='C'?1:c=='G'?2:3; }

void build_ac() {
    queue<int> q; q.push(0);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int c=0;c<4;++c) {
            int v = trie[u].next[c];
            if(v) {
                trie[v].fail = trie[trie[u].fail].next[c];
                trie[v].danger |= trie[trie[v].fail].danger;
                q.push(v);
            } else
                trie[u].next[c] = trie[trie[u].fail].next[c];
        }
    }
}

int solve(char* s) {
    int L = strlen(s);
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for(int i=0;i

複雜度

構建 AC：O(總長度 × 字符集) ≈ 1000 × 4
DP：O(L × 狀態數 × 4) ≤ 1000 × 1000 × 4 = 4×10⁶