HardRating 2662
3292. Minimum Number of Valid Strings to Form Target II
arraystringbinary-searchdynamic-programmingsegment-treerolling-hashstring-matchinghash-function
解題說明
Minimum Number of Valid Strings to Form Target II
題目描述：與 Part I 相同，但資料規模更大。給定一組字串 words 和目標字串 target，有效字串是 words 中任一字串的前綴，求最少串接數量。
解題思路：Part I 的 Trie + DP 在此規模下可能超時。使用 KMP / Z-function 對每個 word 與 target 做匹配，求出 maxJump[i]：從位置 i 開始能匹配的最長前綴長度（取所有 words 的最大值）。然後問題轉化為經典的「跳躍遊戲」：從位置 0 出發，每步可跳 1 到 maxJump[i] 格，求到達位置 n 的最少跳躍次數。用貪心法解決跳躍遊戲部分。
C++ 解法
複雜度分析
時間複雜度：O(S + n) — 其中 S 為所有 words 的總長度。對每個 word 計算 Z-function 為 O(|word| + n)，總計 O(S + k×n)（k 為 words 數量）。跳躍遊戲貪心為 O(n)。
空間複雜度：O(S + n) — Z-function 字串和 maxJump 陣列。
虛擬碼
1. Initialize maxJump[0..n-1] = 0
2. For each word w in words:
a. Build string s = w + '#' + target
b. Compute Z-function of s
c. For each position j in target:
maxJump[j] = max(maxJump[j], min(z[|w|+1+j], |w|))
3. Greedy jump game:
a. jumps = 0, curEnd = 0, farthest = 0
b. For i = 0 to n-1:
farthest = max(farthest, i + maxJump[i])
If farthest <= i: return -1
If i == curEnd: jumps++, curEnd = farthest
4. Return jumps其他解法
Aho-Corasick 自動機 O(S + n)：建立所有 words 的 Aho-Corasick 自動機，在自動機上跑 target，利用 failure link 高效找出所有匹配前綴。再結合 DP 或貪心求最少分段數。實作較複雜但理論時間最優。
Trie + DP + 跳表優化 O(S + n log n)：在 Part I 的 Trie + DP 基礎上，使用線段樹或跳表加速 DP 的區間最小值查詢。
延伸思考
- Z-function 和 KMP 在此題的效果相同，你更偏好哪個？為什麼？
- 如果 words 動態增加或刪除，如何維護 maxJump 陣列？
- 能否將此問題推廣到多目標字串的同時分割？