跳轉到

2.1 樸素比對與Rabin-Karp#

概念說明#

字串比對問題定義：給定文本 T（長度 n）與樣式 P（長度 m），找出所有使 T[i..i+m-1] == P 的位置 i。樸素比對（naive matching）是最直覺的解法：嘗試每個對齊位置，逐字元比較。每次比較最壞 O(m)，共有 n-m+1 個位置，最壞時間 O(nm)——例如 T=AAAA...A、P=AAAB 時，每個位置都比到最後一個字元才失配。

樸素比對浪費的原因是：失配後完全拋棄已累積的資訊，從下一個位置重新開始。兩個改良方向是本章的主軸。第一個方向是 Rabin-Karp 演算法：用雜湊函數把「長度 m 的子字串」壓縮成一個數字，先比較雜湊值，只有雜湊相同時才逐字驗證。若雜湊相等但內容不同，稱為雜湊碰撞（collision），因此必須保留驗證步驟以保證正確性。

Rabin-Karp 的關鍵技巧是滾動雜湊（rolling hash）：假設把字串視為以 b 為基底的多項式取值（例如 h = (c0*b^{m-1} + c1*b^{m-2} + ... + c_{m-1}) mod q，q 是質數，b 通常是 256 或常數）。從窗口 [i] 移到 [i+1] 時，不必重新計算整個窗口：先減去最高位字元的貢獻，乘以 b，再加上新的最低位字元。每步只需 O(1)，於是整個文本的雜湊預計算總共 O(n+m)，比對本身也是 O(n)；加上碰撞驗證，最壞仍是 O(nm)，但隨機資料下平均 O(n+m)。Rabin-Karp 的真正強項是多樣式比對：同時偵測 k 個長度皆為 m 的樣式，只需對每個窗口雜湊一次，再查 k 個目標雜湊值，總時間幾乎不變。

演算法步驟（Rabin-Karp）#

  1. 計算 P 的雜湊值 hp，以及 b^{m-1} mod q 存為 lead（用於移除最高位）。
  2. 計算 T 前視窗 T[0..m-1] 的雜湊值 ht。
  3. 對每個對齊位置 i：
  4. 若 ht == hp，逐字元比較驗證，相同則回報位置 i。
  5. 若 i < n - m，滾動更新：ht = ((ht - ord(T[i]) * lead) * b + ord(T[i+m])) mod q。
  6. 注意 Python % 對負數回傳非負值，滾動公式可安全使用。

Python 程式碼範例#

def naive_search(text, pat):
    n, m = len(text), len(pat)
    return [i for i in range(n - m + 1) if text[i:i+m] == pat]

def rabin_karp(text, pat, base=256, mod=1000000007):
    n, m = len(text), len(pat)
    if m > n:
        return []
    def val(ch):
        return ord(ch) % base
    lead = pow(base, m - 1, mod)
    hp = ht = 0
    for i in range(m):
        hp = (hp * base + val(pat[i])) % mod
        ht = (ht * base + val(text[i])) % mod
    ans = []
    for i in range(n - m + 1):
        if ht == hp and text[i:i+m] == pat:   # 雜湊相同才逐字驗證
            ans.append(i)
        if i < n - m:
            ht = ((ht - val(text[i]) * lead) * base + val(text[i+m])) % mod
    return ans

T = "ABABDABABCABABABC"
P = "ABAB"
print("樸素:", naive_search(T, P))          # 使用切片，通常最快
print("RK  :", rabin_karp(T, P))

# 多樣式比對：一次掃描偵測多個等長樣式
def multi_rabin_karp(text, pats):
    m = len(pats[0])
    mod, base = 1000000007, 256
    def hash_str(s):
        h = 0
        for c in s:
            h = (h * base + ord(c) % base) % mod
        return h
    table = {}
    for p in pats:
        table.setdefault(hash_str(p), []).append(p)
    lead = pow(base, m - 1, mod)
    ht = hash_str(text[:m])
    hits = []
    for i in range(len(text) - m + 1):
        window = text[i:i+m]
        for p in table.get(ht, []):
            if p == window:
                hits.append((i, p))
        if i < len(text) - m:
            ht = ((ht - ord(text[i]) * lead) * base + ord(text[i+m])) % mod
    return hits

print(multi_rabin_karp("ABCXYZABC", ["ABC", "XYZ"]))

複雜度分析#

演算法 建置 最壞比對 平均 空間
樸素比對 無 O(nm) 通常接近 O(n) O(1)
Rabin-Karp O(m) O(nm)（大量碰撞時） O(n+m) O(1)
多樣式 RK O(km) O(kn + km)（取決於碰撞） O(n + km) O(k)

實務上 Python 的 in、str.find 已用高度最佳化的混合演算法實作，一般搜尋直接使用內建即可；Rabin-Karp 的價值在多樣式掃描與教學理解「雜湊可把字串問題轉為數字問題」。

練習#

  1. 修改 rabin_karp，加入「比較到第 k 次碰撞就輸出統計」的功能，觀察在純 A 文本與隨機文本上碰撞次數的差異。
  2. 用滾動雜湊實作：判斷文本中最常出現的長度為 m 的子字串（滑動窗口統計雜湊次數）。
  3. 證明：若基底 b 與模數 q 互質且 q 為質數，兩個不同子字串的雜湊相等的機率約為 1/q。並實驗改變 q 的位數，觀察碰撞率變化。