UVA 11468：AC 自動機 + DP - 避開模式串的概率

問題描述

給定 k 個模式串（病毒特徵），隨機生成長度 L 的字符串，每位字符獨立按概率分布選取。求生成串不包含任何模式串的概率。

核心思路：AC 自動機 + DP

1. 構建 AC 自動機，每個節點標記 is_end（是否為某模式串的結尾，或通過 fail 指向結尾）。
2. DP 狀態：dp[i][u] = 生成前 i 字符，自動機狀態在節點 u，且至今未匹配任何模式串的概率。
3. 轉移：對每個字符 c，下一狀態 v = go(u, c)。若 v 非終結態，dp[i+1][v] += dp[i][u] * prob[c]。
4. 答案：Σ dp[L][u] 對所有非終結態 u 求和。

代碼框架

struct Node {
    int next[62]; // 0-9, A-Z, a-z 共 62
    int fail;
    bool danger; // 是否包含模式串
} ac[MAXN];

double dp[105][MAXN]; // L ≤ 100
double prob[62];

int char_id(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'A' && c <= 'Z') return c - 'A' + 10;
    return c - 'a' + 36;
}

void build_fail() {
    queue q;
    for (int c = 0; c < 62; ++c) {
        int v = ac[0].next[c];
        if (v) { ac[v].fail = 0; q.push(v); }
        else ac[0].next[c] = 0;
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ac[u].danger |= ac[ac[u].fail].danger; // 繼承危險標記
        for (int c = 0; c < 62; ++c) {
            int v = ac[u].next[c];
            if (!v) ac[u].next[c] = ac[ac[u].fail].next[c];
            else { ac[v].fail = ac[ac[u].fail].next[c]; q.push(v); }
        }
    }
}

double solve(int L) {
    dp[0][0] = 1.0;
    for (int i = 0; i < L; ++i) {
        for (int u = 0; u < node_cnt; ++u) if (!ac[u].danger) {
            for (int c = 0; c < 62; ++c) {
                int v = ac[u].next[c];
                if (!ac[v].danger)
                    dp[i+1][v] += dp[i][u] * prob[c];
            }
        }
    }
    double ans = 0;
    for (int u = 0; u < node_cnt; ++u) if (!ac[u].danger) ans += dp[L][u];
    return ans;
}

關鍵優化

• 字符集壓縮至 62（數字+大小寫），節省空間與時間。
• danger 標記在構建 fail 時傳播：ac[u].danger |= ac[ac[u].fail].danger，避免匹配時沿 fail 鏈檢查。
• DP 數組滾動可優化至 O(節點數) 空間。

總結

AC 自動機將多模式匹配轉化為狀態機，DP 在狀態機上計算避開「危險狀態」的概率。是「字符串概率 + 多模式匹配」的經典結合。