第一部分：字串演算法（續）¶
< 上一題：KMP 演算法 | 返回目錄 | 下一題：分治法設計 >
場景：偵測網路上的抄襲內容¶
你發現很多網站**複製貼上**同樣的內容。為了提升搜尋品質，需要偵測重複內容。
問題：給定一篇新文章，判斷它是否「抄襲」了資料庫中的某篇文章。
KMP 適合「一個 Pattern 對一個 Text」。但現在你有**數百萬個 Pattern**（資料庫中的文章），一一比對太慢了。
「有沒有辦法同時比對多個 Pattern？或者更快地判斷『相似』？」
第 2 題：重複內容偵測 - Rabin-Karp¶
Rabin-Karp 演算法用**雜湊**來加速字串匹配，特別適合多模式匹配和「近似匹配」。
(a) 字串雜湊的想法¶
3 分 ・ 大二
你需要知道：如何把字串「壓縮」成一個數字來快速比較？
題目：
-
設計一個簡單的字串雜湊函數
-
說明為什麼兩個字串雜湊值相同，不代表字串相同
-
如果雜湊值不同，可以得出什麼結論？
解答
1. 字串雜湊函數：
把字串視為 \(d\) 進位的數字（\(d\) = 字母表大小）：
為了避免數字太大，通常取模：
範例：\(d = 26\)（小寫字母），\(q = 101\)
2. 雜湊碰撞：
兩個不同的字串可能有相同的雜湊值（碰撞）。
例如：如果 \(q = 10\)，則 "abc"（雜湊 28 mod 10 = 8）可能和其他字串碰撞。
雜湊相同 ≠ 字串相同
3. 雜湊不同的結論：
如果 \(H(S_1) \neq H(S_2)\)，則 \(S_1 \neq S_2\)（必然）。
這是雜湊的核心價值：快速排除不匹配。
(b) Rolling Hash - 滑動窗口的雜湊¶
4 分 ・ 大三
你需要知道：如何在 \(O(1)\) 時間內更新窗口的雜湊值？
題目：
-
說明 Rolling Hash 的原理
-
推導從 \(H(T[i..i+m-1])\) 計算 \(H(T[i+1..i+m])\) 的公式
-
分析使用 Rolling Hash 的 Rabin-Karp 時間複雜度
解答
1. Rolling Hash 原理：
當窗口從 \(T[i..i+m-1]\) 滑動到 \(T[i+1..i+m]\) 時： - 移除最左邊的字元 \(T[i]\) - 加入最右邊的字元 \(T[i+m]\)
不需要重新計算整個雜湊，只需要「更新」。
2. 公式推導：
設 \(H_i = H(T[i..i+m-1])\)
觀察：
Rolling Hash 公式：
預先計算 \(d^{m-1} \mod q\)，每次更新只需要 \(O(1)\)。
3. 時間複雜度：
- 預處理：計算 \(H(P)\) 和 \(d^{m-1}\)，\(O(m)\)
- 滑動：\(n - m + 1\) 個窗口，每個 \(O(1)\) 更新
- 碰撞驗證：每次碰撞需要 \(O(m)\) 逐字比較
期望時間：\(O(n + m)\)（假設碰撞很少）
最壞時間：\(O(nm)\)（所有窗口都碰撞，退化成暴力）
數學小結：Rolling Hash
| 參數 | 選擇建議 |
|---|---|
| \(d\) | 字母表大小（如 256） |
| \(q\) | 大質數（如 \(10^9 + 7\)） |
© Rabin-Karp 完整演算法¶
3 分 ・ 大二
你需要知道：如何實現 Rabin-Karp？
題目：
寫出完整的 Rabin-Karp 演算法。
解答
def rabin_karp(text, pattern, d=256, q=10**9+7):
n, m = len(text), len(pattern)
if m > n:
return []
# 預計算 d^(m-1) mod q
h = pow(d, m - 1, q)
# 計算 Pattern 和第一個窗口的雜湊
p_hash = 0
t_hash = 0
for i in range(m):
p_hash = (d * p_hash + ord(pattern[i])) % q
t_hash = (d * t_hash + ord(text[i])) % q
results = []
# 滑動窗口
for i in range(n - m + 1):
# 雜湊匹配，需要驗證
if p_hash == t_hash:
if text[i:i+m] == pattern: # 逐字驗證
results.append(i)
# 計算下一個窗口的雜湊
if i < n - m:
t_hash = (d * (t_hash - ord(text[i]) * h) + ord(text[i + m])) % q
if t_hash < 0:
t_hash += q
return results
(d) 多模式匹配¶
4 分 ・ 大三
你需要知道：Rabin-Karp 如何同時匹配多個 Pattern？
題目：
假設有 \(k\) 個 Pattern，每個長度都是 \(m\)。如何高效地找出所有匹配？
解答
方法：用 Hash Set 存所有 Pattern 的雜湊值
def rabin_karp_multi(text, patterns, d=256, q=10**9+7):
if not patterns:
return {}
n = len(text)
m = len(patterns[0]) # 假設等長
# 建立 Pattern 雜湊集合
pattern_hashes = {}
for p in patterns:
h = 0
for c in p:
h = (d * h + ord(c)) % q
if h not in pattern_hashes:
pattern_hashes[h] = []
pattern_hashes[h].append(p)
# 計算 d^(m-1)
dm = pow(d, m - 1, q)
# 滑動窗口
t_hash = 0
for i in range(m):
t_hash = (d * t_hash + ord(text[i])) % q
results = {p: [] for p in patterns}
for i in range(n - m + 1):
if t_hash in pattern_hashes:
window = text[i:i+m]
for p in pattern_hashes[t_hash]:
if window == p:
results[p].append(i)
if i < n - m:
t_hash = (d * (t_hash - ord(text[i]) * dm) + ord(text[i + m])) % q
if t_hash < 0:
t_hash += q
return results
時間複雜度：
- 預處理 \(k\) 個 Pattern：\(O(km)\)
- 滑動窗口：\(O(n)\)
- Hash Set 查詢：\(O(1)\) 平均
總時間：\(O(n + km)\)
比起 KMP 的 \(O(k(n + m))\)，當 \(k\) 很大時效率更高。
進階挑戰：抄襲偵測的實際應用¶
3 分 ・ 碩一
在實際的抄襲偵測中，我們不是找「完全相同」，而是找「相似」的文章。
你需要知道：如何用雜湊技術偵測「近似重複」？
解答
Shingling + MinHash + LSH
Step 1：Shingling
把文章切成 \(k\)-grams（\(k\) 個連續詞的組合）。
Step 2：MinHash
用多個雜湊函數，取每個函數下的最小雜湊值。
兩篇文章的 MinHash 「簽名」越相似，原始 shingle 集合的 Jaccard 相似度越高。
Step 3：Locality Sensitive Hashing (LSH)
把相似的文章雜湊到同一個 bucket，減少比較次數。
這是 Google、學術論文查重系統的核心技術。
第 2 題小結：你的字串雜湊工具箱¶
「怎麼快速偵測重複內容？」
│
├─► (a) 字串雜湊
│ → 把字串壓縮成數字
│ → 雜湊不同 ⇒ 字串不同
│
├─► (b) Rolling Hash
│ → O(1) 更新窗口雜湊
│ → H_{i+1} = d(H_i - T[i]·d^{m-1}) + T[i+m]
│
├─► (c) Rabin-Karp
│ → 期望 O(n + m)
│ → 碰撞時逐字驗證
│
└─► (d) 多模式匹配
→ Hash Set 存 Pattern 雜湊
→ O(n + km)
| 演算法 | 時間 | 適用場景 |
|---|---|---|
| KMP | \(O(n + m)\) | 單模式，需要精確 |
| Rabin-Karp | \(O(n + m)\) 期望 | 多模式，可接受碰撞 |