解題說明
Partition String
題目描述：給定一個字串 s 和一組模式字串 pattern，將 s 從左到右劃分為若干段。每一段的劃分規則：從當前位置開始，找到在 pattern 中出現的最長前綴作為一段。若當前字元無法匹配任何模式的起始，則該字元單獨作為一段。回傳劃分後的段數。
解題思路：使用 Trie（前綴樹）來高效匹配模式。首先將所有模式字串插入 Trie。然後從字串 s 的開頭開始，在 Trie 中進行最長匹配：沿著 Trie 向下走，記錄最後一次到達終端節點的位置，即為最長匹配。若沒有任何匹配，跳過一個字元。每次匹配後，從匹配結束的下一個位置繼續。
C++ 解法
複雜度分析
時間複雜度：O(L + n * M) — 建 Trie O(L)（L 為所有模式的總長度），匹配過程中每個位置最多走 M 步（M 為最長模式長度），但攤銷後接近 O(n)。
空間複雜度：O(L * 26) — Trie 節點數最多 O(L)，每個節點 26 個指標。
虛擬碼
1. Build a Trie from all pattern strings 2. Initialize pointer i = 0, parts = 0 3. While i < len(s): a. Walk Trie from root, following s[i], s[i+1], ... b. Record the position of the last complete pattern match (lastMatch) c. Increment parts d. If lastMatch found: set i = lastMatch e. Else: set i = i + 1 (skip one char) 4. Return parts
其他解法
雜湊集合 O(n * M²)：將所有模式存入 HashSet，對每個位置嘗試所有可能長度的子字串查找最長匹配。簡單但慢。
Aho-Corasick 自動機 O(n + L)：建立 AC 自動機可以在 O(n) 時間內找到所有模式的出現位置，然後用貪心選擇最長匹配。適合模式數量非常大的情況。
延伸思考
- 如果要求劃分出的段數最少，貪心（最長匹配）是否一定是最優策略？
- 若模式可以重疊（例如 "ab" 和 "abc" 都在模式中），如何確保正確選擇最長匹配？
- 若字串和模式都很長（10^6），如何在記憶體受限的環境下優化 Trie？