UVA 1401 Remember the Word：Trie + DP 求單詞拆分方案數

問題描述

• 給定長度 ≤ 300,000 的目標字符串 S。
• 字典包含 S ≤ 4000 個單詞，每個長度 ≤ 100，全小寫，無重複。
• 求將 S 拆分為字典單詞序列的方案數，模 20071027。
• 多測試用例，空行分隔，EOF 結束。

算法：Trie 匹配 + 後向 DP

狀態定義

dp[i]：從位置 i（0-indexed）開始到字符串末尾的合法拆分方案數。
答案 = dp[0]。
邊界：dp[n] = 1（空串 1 種拆分）。

轉移

從後向前枚舉 i = n-1 .. 0：

1. 在 Trie 中從根出發，沿 S[i], S[i+1], ... 遍歷。
2. 每走到一個節點 u，若 u 是單詞結尾（val[u] > 0），則 dp[i] += val[u] * dp[j+1]，其中 j 為當前字符索引。
3. 若 Trie 中無對應子節點，中斷內層循環。

Trie 節點結構

struct Node {
    int son[26] = {0};
    int val = 0;  // 以此節點結尾的單詞數（本題無重複單詞，故 0/1）
} nodes[MAX_NODES];  // MAX_NODES ≈ 4000 * 100 = 400,000

完整代碼

#include 
using namespace std;
const int MOD = 20071027;
const int MAXN = 300005;
const int MAXNODE = 400005;

int son[MAXNODE][26], val[MAXNODE], dp[MAXN], nodeCnt;
char S[MAXN], word[105];

void insertWord(const char* s) {
    int u = 0;
    for (int i = 0; s[i]; ++i) {
        int c = s[i] - 'a';
        if (!son[u][c]) {
            son[u][c] = ++nodeCnt;
            memset(son[nodeCnt], 0, sizeof(son[nodeCnt]));
            val[nodeCnt] = 0;
        }
        u = son[u][c];
    }
    val[u] = 1;  // 標記單詞結尾
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int caseNo = 1;
    while (scanf("%s", S) == 1) {
        int n = strlen(S);
        int dictSize; scanf("%d", &dictSize);
        // 重置 Trie
        nodeCnt = 0;
        memset(son[0], 0, sizeof(son[0]));
        val[0] = 0;
        // 讀入字典
        for (int i = 0; i < dictSize; ++i) {
            scanf("%s", word);
            insertWord(word);
        }
        // DP
        dp[n] = 1;
        for (int i = n - 1; i >= 0; --i) {
            int u = 0;
            dp[i] = 0;
            for (int j = i; j < n; ++j) {
                int c = S[j] - 'a';
                if (!son[u][c]) break;
                u = son[u][c];
                if (val[u]) {
                    dp[i] = (dp[i] + 1LL * val[u] * dp[j+1]) % MOD;
                }
            }
        }
        printf("Case %d: %d\n", caseNo++, dp[0]);
    }
    return 0;
}

關鍵優化點

1. 靜態數組 Trie：避免動態分配開銷，son[MAXNODE][26] 直接訪問極快。
2. 後向 DP：只需單維數組 dp[i]，依賴 dp[j+1] (j>i) 已計算。
3. 早期剪枝：Trie 中無路徑即 break，避免無效遍歷。
4. 模運算：每步取模，防止溢出（用 1LL * val * dp）。
5. 快速輸入：scanf 讀字符串，避免 cin 慢。

複雜度分析

• 構建 Trie：O(總字典字符數) ≤ 4×10⁵。
• DP：每個位置 i 向後匹配直到 Trie 斷開，最長 100 步。總 O(n × 最大單詞長) ≤ 3×10⁷。
• 空間：Trie 4×10⁵ × 26 × 4B ≈ 40 MB，DP 3×10⁵ × 4B ≈ 1.2 MB，總 < 64 MB。

總結

UVA 1401 是「Trie 加速字典匹配 + 線性 DP」的經典組合。關鍵在於：

• 用 Trie 將「檢查所有字典單詞是否匹配」降為「沿字符串走 Trie 一次」。
• 後向 DP 自然適配「從位置 i 開始」的子問題結構。
• 靜態數組實現 Trie，配合快速 IO，輕鬆通過大數據限制。