Rabin-Karp：數位指紋

演算法背後的故事：印章的效率

在古代，如果國王想要驗證一封信的真實性，他不會先讀完整封信。他會先看信封上的 火漆印章。如果印章與他的印戒吻合，他就能瞬間確認信件的真實性。

1987 年，Michael O. Rabin 和 Richard M. Karp 將這一古老的智慧應用到了電腦科學中。她們意識到，逐個字元地比較字串是緩慢的，但比較兩個數字卻是瞬間完成的。

她們設計了一種方法，將任何字串轉換為一個唯一的「數字」（雜湊值）。如果數字匹配，那麼字串很可能匹配。這讓字串搜尋從一個語言學問題變成了數學問題。

為什麼需要它？

Rabin-Karp 在 多模式搜尋 和 剽竊檢測 中大放異彩。

• 論文查重： 如果妳想檢查一個學生是否從 10,000 篇不同的文章中剽竊了一個段落，Rabin-Karp 可以透過比較雜湊值，一次性掃描所有文章。
• 入侵檢測： 在單次掃描網路數據包的過程中，同時尋找數千個已知的病毒特徵。
• 滾動雜湊 (Rolling Hash)： 它是 rsync 的核心，允許她在不發送整個檔案的情況下，快速找出檔案的哪些部分發生了變化。

演算法是如何「思考」的

這個演算法像是一個精通 滾動雜湊 (Rolling Hash) 的數學家。

1. 指紋 (雜湊)： 它將模式串 apple 轉化為一個數字，比如 12345。

2. 滑動窗口： 它在文本上滑動一個長度為 5 的窗口。

   • 「hello」 $\to$ 56789 (不匹配)
   • 「world」 $\to$ 43210 (不匹配)

3. 「滾動」魔術： 這是最核心的秘密。為了計算下一個窗口的雜湊值，它不需要重新讀取所有 5 個字元。它透過數學方法 「滾出」 第一個字元，並 「滾入」 新字元。 新雜湊 = (舊雜湊 - 首字元貢獻) * 基數 + 新字元。 這使得每一步的雜湊計算複雜度都是 $O(1)$。

4. 最終驗證： 如果雜湊值匹配，它會進行一次快速的逐字元檢查，以 100% 確保沒有發生「雜湊衝突」（即兩個不同的字串產生了相同的數字）。

工程決策：並行計算的力量

Rabin-Karp 的精妙之處在於它將字串匹配轉變成了 GPU 或 專用晶片 非常擅長的數學運算。

• 複雜度： 平均情況為 $O(N + M)$，但它允許妳在幾乎相同的时间内搜尋 K 個模式串。
• 權衡： 它對雜湊函式的選擇非常敏感。如果雜湊函式選得不好，會產生太多的「虛警」（衝突），導致速度急劇下降。

實作參考 (Python)

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m > n: return -1
    
    # 一個簡單的滾動雜湊 (多項式滾動雜湊)
    base = 256
    prime = 101 # 使用一個素數來減小衝突並保持雜湊值在合理範圍
    
    p_hash = 0 # 模式串的指紋
    t_hash = 0 # 文本當前窗口的指紋
    h = pow(base, m - 1) % prime # 最高位字元的權重
    
    # 1. 生成初始指紋
    for i in range(m):
        p_hash = (base * p_hash + ord(pattern[i])) % prime
        t_hash = (base * t_hash + ord(text[i])) % prime
        
    # 2. 滑動與滾動
    for i in range(n - m + 1):
        if p_hash == t_hash:
            # 3. 最終驗證（排除雜湊衝突）
            if text[i:i+m] == pattern:
                return i
        
        if i < n - m:
            # 4. 滾動數學：踢出舊字元 text[i]，加入新字元 text[i+m]
            t_hash = (base * (t_hash - ord(text[i]) * h) + ord(text[i+m])) % prime
            if t_hash < 0: t_hash += prime
            
    return -1

# 使用範例
# print(rabin_karp("AABAACAADAABAABA", "AABA")) # 輸出: 0

小結

Rabin-Karp 教會我們：抽象是一種捷徑。透過將複雜的數據轉化為簡單的數字，我們可以以數學的速度處理這個世界。它提醒我們，有時候，了解一張臉最好的方式是查看它的指紋。