EasyRating 1214

3042. Count Prefix and Suffix Pairs I

arraystringtrierolling-hashstring-matchinghash-function

解題說明

Count Prefix and Suffix Pairs I

題目描述：給定一個字串陣列 words，計算有多少對 (i, j)（i < j）使得 words[i] 同時是 words[j] 的前綴與後綴。

解題思路：由於 Easy 版本中陣列長度和字串長度都較小，可以直接暴力枚舉所有 (i, j) 配對，對每一對檢查 words[i] 是否為 words[j] 的前綴且同時是後綴。前綴檢查用 starts_with，後綴檢查用 ends_with（或手動比較）。只要 words[i].size() <= words[j].size() 且兩個條件都成立就計數。

C++ 解法

複雜度分析

時間複雜度：O(n² × L) — 枚舉所有配對 O(n²)，每對檢查前綴和後綴最多 O(L)，L 為字串最大長度。

空間複雜度：O(1) — 僅使用常數額外空間。

虛擬碼

1. Initialize count = 0
2. For each pair (i, j) where i < j:
   a. If words[i].length > words[j].length, skip
   b. Check if words[i] is a prefix of words[j]
   c. Check if words[i] is a suffix of words[j]
   d. If both true, increment count
3. Return count

其他解法

Z-function / KMP O(n² × L)：對每對使用 Z-function 或 KMP 判斷前綴與後綴關係。時間複雜度相同但常數更大，在此題規模下並無優勢。

Trie + 雙鍵 O(n × L)：將字串同時以 (s[i], s[n-1-i]) 作為 Trie 的鍵來建立。可在 O(n × L) 時間內解決，適用於 Part II 的大規模資料。

延伸思考

如果 words 長度達到 10⁵ 且字串長度也很大，暴力法會超時，該如何用 Trie 優化？（參見 Part II）
如果只要求 words[i] 是 words[j] 的前綴（不需要同時是後綴），問題會簡單多少？
如何修改演算法來找出所有滿足條件的配對，而不只是計數？