POJ 1625 Censored!：AC 自動機 + DP + 高精度計數合法字符串

問題建模

給定字符集（可能超過 128，需映射）、P 個禁用模式串。求長度為 M 的字符串中不包含任何禁用模式的數量。N=字符集大小, M≤100, P≤100。答案極大需高精度。

AC 自動機構建

1. Trie 插入所有禁用模式，標記終結節點 end=1。
2. BFS 構建 fail 指針，並傳遞 end 標記（若 fail 祖先是終結，當前也視為終結）。
3. 補全轉移：next[u][c] = -1 時指向 next[fail[u]][c]，根節點缺失轉移指向自身。

DP 狀態定義

dp[i][state]：長度 i、自動機狀態為 state 的合法字符串數。轉移：
dp[i+1][next[state][c]] += dp[i][state]，前提 !end[next[state][c]]。
初始 dp[0][0]=1，答案 = Σ dp[M][*]。

高精度實現

基數 10000（4 位十進制），實現 +、* 運算。DP 中只需加法與乘小整數（轉移權重 ≤ N），可進一步優化為僅加法。

關鍵代碼結構

struct Trie {
    int next[110][256], fail[110]; bool end[110]; int L, root;
    void insert(char* s) { ... }
    void build() { ... } // BFS 構建 fail 並補全轉移
    Matrix getMatrix() { // 轉移矩陣（可選，本題用 DP 更快）
        Matrix res(L);
        for(i=0;i<L;++i) for(j=0;j<N;++j)
            if(!end[next[i][j]]) res.mat[i][next[i][j]]++;
        return res;
    }
};

struct BigInt { // 基數 10000 高精度
    int a[600], len;
    BigInt operator+(BigInt b) { ... }
    BigInt operator*(int k) { ... } // 乘小整數優化
    void output() { ... }
};

BigInt dp[2][110]; // 滾動數組優化空間

優化要點

• 字符映射 map<char,int> 處理任意字符集
• 滾動數組 dp[2][110] 空間 O(L)
• 避免矩陣快速冪（O(L³ log M)），直接 DP O(M·L·N) 更快

複雜度

構建自動機 O(總模式長 × 字符集)，DP O(M × 狀態數 × N) ≈ 100 × 100 × 100 = 1e6，極快。