UVA 1401 Remember the Word：Trie + DP 統計分割方案數

問題描述

給定 n ≤ 4000 個單詞和一個長度 ≤ 300,000 的字符串 S。求將 S 分割成若干個給定單詞拼接的方案數，答案對 20071027 取模。多組測試數據，以 EOF 結束。

核心思路：Trie + 動態規劃

狀態定義：dp[i] 表示 S[i..len-1] 後綴的合法分割方案數。
目標：dp[0]。
轉移：從位置 i 開始，在 Trie 中匹配所有以 S[i] 開頭的單詞。若匹配到單詞結尾（長度 L），則 dp[i] += dp[i+L]。
邊界：dp[len] = 1（空後綴 1 種方案）。

優化關鍵：避免重複 strlen

在 find 函數中遍歷 Trie 時，絕不可 在循環中調用 strlen(s) 或 s[i] 以外的長度計算。應直接用 for (int i = pos; s[i]; ++i) 利用字符串結尾 \0 判斷。否則每次查找 O(L) 變為 O(L²)，導致 TLE。

代碼實現

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
const int MOD = 20071027;

int ch[MAXN][26];
int val[MAXN];
int sz;
int dp[MAXN];
char S[MAXN];

int idx(char c) { return c - 'a'; }

void insert(const char* s) {
    int u = 0;
    for (int i = 0; s[i]; ++i) {
        int c = idx(s[i]);
        if (!ch[u][c]) {
            memset(ch[sz], 0, sizeof(ch[sz]));
            val[sz] = 0;
            ch[u][c] = sz++;
        }
        u = ch[u][c];
    }
    val[u] = 1;
}

void find(int pos) {
    dp[pos] = 0;
    int u = 0;
    for (int i = pos; S[i]; ++i) {
        int c = idx(S[i]);
        if (!ch[u][c]) return;
        u = ch[u][c];
        if (val[u]) dp[pos] = (dp[pos] + dp[i+1]) % MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, cas = 0;
    char word[105];
    while (cin >> m) {
        // 初始化 Trie
        sz = 1;
        memset(ch[0], 0, sizeof(ch[0]));
        val[0] = 0;
        for (int i = 0; i < m; ++i) {
            cin >> word;
            insert(word);
        }
        cin >> S;
        int len = strlen(S);
        dp[len] = 1;
        for (int i = len - 1; i >= 0; --i) find(i);
        cout << "Case " << ++cas << ": " << dp[0] << '\n';
    }
    return 0;
}

複雜度分析

• 構建 Trie：O(總單詞長度) ≤ 4000 × 平均長度。
• DP：每個位置 i 最多沿 Trie 走 len-i 步，但總步數受限於 Trie 邊數，實際為 O(|S| × 平均匹配深度)。
• 空間：Trie 節點數 ≤ 總單詞字符數 + 1，dp 數組 O(|S|)。

易錯點總結

1. 多測試用例初始化：每組數據必須完全重置 Trie（sz=1、清空根節點）。
2. 模數運算：每次加法後取模，防止溢出。
3. 輸入讀取：單詞與字符串可能包含換行，用 cin >> word 自動跳過空白。
4. 避免 strlen：如前所述，這是 AC 與 TLE 的分水嶺。