HardRating 2328

3045. Count Prefix and Suffix Pairs II

arraystringtrierolling-hashstring-matchinghash-function

解題說明

Count Prefix and Suffix Pairs II

題目描述：給定一個字串陣列 words，計算有多少對 (i, j)（i < j）使得 words[i] 同時是 words[j] 的前綴與後綴。此版本資料規模大，需要高效解法。

解題思路：建立一個特殊的 Trie，鍵為字元對 (s[k], s[n-1-k])。對於每個字串 s，將 (s[0], s[n-1]), (s[1], s[n-2]), ... 依序插入 Trie。當我們處理 words[j] 時，沿著 Trie 走，途中遇到的每個標記為「某個 words[i] 結尾」的節點，就代表該 words[i] 同時是 words[j] 的前綴和後綴。插入 words[j] 前先查詢累計答案，再將 words[j] 插入 Trie。

C++ 解法

複雜度分析

時間複雜度：O(n × L) — n 為字串數量，L 為平均字串長度。每個字串在 Trie 上走一趟，每步為 O(1)（雜湊表操作均攤）。

空間複雜度：O(n × L) — Trie 最多有 O(n × L) 個節點。

虛擬碼

1. Create empty Trie with paired-character keys
2. Initialize answer = 0
3. For each word w in words (left to right):
   a. Walk the Trie using keys (w[k], w[n-1-k]) for k = 0,1,...,n-1
   b. At each node, add node.count to answer (these are previous words that are both prefix and suffix of w)
   c. After reaching the end, increment the final node's count
4. Return answer

其他解法

Z-function 判定 O(n² × L)：對每對 (i,j) 使用 Z-function 同時判斷前綴和後綴。時間複雜度為 O(n² × L)，在 n 大時會超時。

Rolling Hash O(n × L)：用雙向 rolling hash（前綴 hash + 後綴 hash）判斷前綴後綴匹配，搭配雜湊表統計。需要小心處理碰撞，但空間效率可能較 Trie 好。

延伸思考

如果只需要計算同時是前綴（不要求是後綴）的配對數，Trie 可以如何簡化？
能否用 KMP failure function 來判斷一個字串是否為另一個字串的前綴兼後綴？
如果要回傳所有滿足條件的配對（不只是計數），如何修改 Trie 結構？

Count Prefix and Suffix Pairs II — CaffeCode