BZOJ 1212 HNOI 2004 L語言：Trie 樹動態規劃求最長可翻譯前綴

BZOJ 1212 HNOI 2004 L語言：Trie 樹動態規劃求最長可翻譯前綴

給定詞典單詞和句子，句子可被翻譯當且僅當能分割成詞典單詞。求每個句子最長可翻譯前綴長度。

問題建模

• 詞典：W 個單詞，總長度 ≤ 10⁶
• 句子：C 個，每個長度 ≤ 10⁶
• 目標：對每句子，找最大 k 使前 k 字符可分割為詞典詞

Trie + DP 算法

1. 構建詞典 Trie 樹，標記單詞結尾
2. 對句子 s (1-indexed)，DP 數組 `f[i]` 表示前 i 字符可翻譯
3. `f[0] = true`
4. 對 i = 0..len-1，若 `f[i]` 為真，從 i+1 開始在 Trie 中匹配，每到一個單詞結尾設置 `f[j] = true`
5. 答案 = 最大的 i 使 `f[i] = true`

Trie 節點設計

struct TrieNode {
    TrieNode* child[26];
    bool is_end;
    TrieNode() : is_end(false) { memset(child, 0, sizeof(child)); }
};

完整 C++ 實現

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

struct TrieNode {
    int child[26];
    bool is_end;
    TrieNode() : is_end(false) { memset(child, -1, sizeof(child)); }
};

vector<TrieNode> trie(1); // 0 為根

void insert(const string& s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[u].child[c] == -1) {
            trie[u].child[c] = trie.size();
            trie.emplace_back();
        }
        u = trie[u].child[c];
    }
    trie[u].is_end = true;
}

int solve(const string& s) {
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    int ans = 0;
    
    for (int i = 0; i < n; ++i) {
        if (!dp[i]) continue;
        ans = i; // 更新可達最遠位置
        int u = 0;
        for (int j = i; j < n; ++j) {
            int c = s[j] - 'a';
            if (trie[u].child[c] == -1) break;
            u = trie[u].child[c];
            if (trie[u].is_end) dp[j + 1] = true;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int W, C; cin >> W >> C;
    string word;
    for (int i = 0; i < W; ++i) {
        cin >> word;
        insert(word);
    }
    
    string sentence;
    for (int i = 0; i < C; ++i) {
        cin >> sentence;
        cout << solve(sentence) << "\n";
    }
    return 0;
}

關鍵優化點

複雜度分析

• 構建 Trie：O(總詞典長度) ≈ 10⁶
• 單句處理：O(句子長度 × 平均匹配深度)
• 最壞每位置匹配到單詞最長長度，但實際極快
• 總體線性於輸入規模

為什麼不用 AC 自動機？

AC 自動機適合多模式匹配「找出所有出現位置」。本題只需「從每個可達位置向前匹配」，Trie 直接遍歷更簡單、常數更小。題目註釋說明 Trie 甚至比 AC 更快。

邊界情況

• 空句子：輸出 0
• 無法翻譯任何前綴：輸出 0 (`f[0]=true` 保證)
• 整句可翻譯：輸出句子長度
• 單詞重複：Trie 自然去重

此題是 Trie 樹結合 DP 解決「單詞拆分/可翻譯前綴」問題的教科書級範例，展示了字典樹在字符串分割問題中的核心優勢。