Rabin-Karp滾動雜湊比對

01為什麼需要它

看到這些關鍵字就想到它：在長文字裡找固定長度的片段、同時找很多個等長模式、比對所有長度 k 的子字串、視窗每移一格就要一個指紋、只需要期望線性時間。

02核心概念

暴力比對在每個起點逐字元比，最壞 O(nm)，例如文字是一百萬個 a、模式是 999 個 a 接一個 b，每個起點都要比到最後一個字元才失敗。Rabin-Karp 的想法是先比雜湊：模式 P 的雜湊算一次，文字 T 裡每個長度 m 的視窗也算雜湊，雜湊不同就一定不相等，直接跳過。可是如果每個視窗都從頭算，一個視窗就要 O(m)，總共還是 O(nm)，所以關鍵在於讓雜湊能滾動。

滾動雜湊沿用上一篇的多項式雜湊，視窗是一個 B 進位、m 位的數。往右滑一格時：減掉最高位的 T[i]·B^(m−1)，整體乘 B 往左推一位，再加上新進來的 T[i+m]，也就是 hash(i+1) = (hash(i) − T[i]·B^(m−1))·B + T[i+m]，全部 mod M。十進位的例子：四位數視窗從 1234 滑到 2345，就是 (1234 − 1 × 1000) × 10 + 5。B^(m−1) 事先算好，每一格只剩幾次加減乘，O(1)。

雜湊相同不代表字串相同，所以要逐字元確認，確認失敗的就是碰撞造成的假陽性。複雜度：P 和第一個視窗 O(m)，n − m + 1 次滑動各 O(1)；每次確認 O(m)，但假陽性的機率大約 1/M，模數夠大時幾乎不會發生，所以期望時間是 O(n + m + 命中次數 × m)，只問「有沒有出現」時找到第一個就停，就是期望 O(n + m)。最壞情況仍是 O(nm)：模式在文字裡重疊出現非常多次（T 全是 a、P 也全是 a），或模數和底數被猜到而遭刻意構造碰撞。額外空間只有幾個整數，O(1)。

常見的坑：減掉最高位後可能是負數，C++ 要先加 M；B^(m−1) 在迴圈裡重算會把每格變回 O(m)；忘了逐字元確認，碰撞時就回報錯誤的位置；最後一個視窗滑完不要再讀 T[i+m]，會越界。字母很少、模式很短時，可以把每個字元編成固定位元（DNA 一個鹼基 2 位元），滾動值就是完全不會碰撞的編碼。和鄰近課程的關係：上一篇的前綴雜湊用 get(i, i+m) 也能比對每個視窗，但要 O(n) 空間，滾動版只要 O(1)；需要保證最壞 O(n + m) 的單一模式比對用下一篇 KMP；長度不同的大量模式則交給字典樹上的 Aho–Corasick。

03演算法步驟

1. 1模式比文字長就直接回傳。算出 hash(P)、第一個視窗 hash(T[0, m))，並預先算好 top = B^(m−1) mod M。
2. 2檢查目前視窗 i：雜湊和 hash(P) 不同就跳過，一定不是。
3. 3雜湊相同就逐字元比較 T[i, i+m) 和 P，全部相同才記錄位置 i；不同就是碰撞，略過。
4. 4還沒到最後一個視窗就滾動：hash = ((hash − T[i]·top)·B + T[i+m]) mod M，減完是負數要先加 M。
5. 5重複到 i = n − m。有多個長度相同的模式時，把它們的雜湊放進雜湊表，每個視窗查一次表即可。

04互動示範

在 T = abracadabra 裡找 P = abra，和上一篇一樣取 B = 31、a = 1，模數故意用很小的 M = 101。hash(P) = 53，最高位的權重 31³ mod 101 = 97。黃色是目前的視窗，每次滑動時灰色是剛離開的字元、藍色是剛進來的字元，框裡是 O(1) 的滾動算式。八個視窗的雜湊依序是 53、53、74、86、64、35、15、53：視窗 0 雜湊相同，逐字元確認後變綠色，是真的命中；視窗 1 的 brac 雜湊也是 53，確認時第一個字就不同，藍色標出不相符的字元，這就是碰撞；中間五個雜湊不同，直接跳過；視窗 7 再次命中。最後找到位置 0 和 7。

05程式碼

Python 放單一模式的 Rabin-Karp，以及多個等長模式共用一次掃描的版本，兩者都在雜湊相同後逐字元確認。C++ 放單一模式版，用無號整數時先加 M 再減；另外附上 DNA 片段的 2 位元滾動編碼，這題因為字母只有 4 種，滾動值本身就不會碰撞，不需要模數。

import random

M = 1_000_000_007
B = random.randrange(256, M)            # 底數隨機選，別人無法事先構造大量碰撞


def poly_hash(s):
    x = 0
    for ch in s:
        x = (x * B + ord(ch)) % M
    return x


def rabin_karp(text, pat):
    """pat 在 text 中出現的所有位置。每個視窗 O(1) 更新，期望 O(n + m)"""
    n, m = len(text), len(pat)
    if m == 0 or m > n:
        return []
    top = pow(B, m - 1, M)              # 視窗最高位的權重，滑動時用來減掉離開的字元
    hp, hw = poly_hash(pat), poly_hash(text[:m])
    res = []
    for i in range(n - m + 1):
        if hw == hp and text[i:i + m] == pat:   # 雜湊相同才逐字元確認，碰撞會在這裡被擋掉
            res.append(i)
        if i + m < n:                   # 減掉最高位、整體左移一位、補上新進來的字元
            hw = ((hw - ord(text[i]) * top) * B + ord(text[i + m])) % M
    return res


def find_many(text, patterns):
    """多個「長度相同」的模式一起找：雜湊放進字典，文字只掃一次"""
    m = len(patterns[0])
    if m == 0 or m > len(text):
        return []
    table = {}
    for p in patterns:
        table.setdefault(poly_hash(p), []).append(p)
    top = pow(B, m - 1, M)
    hw, res = poly_hash(text[:m]), []
    for i in range(len(text) - m + 1):
        for p in table.get(hw, []):     # 同一個雜湊值底下可能有好幾個模式，逐一確認
            if text[i:i + m] == p:
                res.append((i, p))
        if i + m < len(text):
            hw = ((hw - ord(text[i]) * top) * B + ord(text[i + m])) % M
    return res


if __name__ == "__main__":
    print(rabin_karp("abracadabra", "abra"))    # [0, 7]
    print(rabin_karp("aaaaa", "aa"))            # [0, 1, 2, 3]
    print(find_many("ACGTTGCAACGTAGGT", ["ACGT", "AGGT", "TTTT"]))
    # [(0, 'ACGT'), (8, 'ACGT'), (12, 'AGGT')]

06練習題

• LeetCode 796Rotate String（在 s + s 裡找 goal）Easy
• LeetCode 1461Check If a String Contains All Binary Codes of Size K（位元視窗滾動）Medium
• LeetCode 187Repeated DNA Sequences（2 位元滾動編碼）Medium
• LeetCode 686Repeated String MatchMedium
• LeetCode 2156Find Substring With Given Hash Value（反過來從右往左滾動）Hard
• LeetCode 1923Longest Common Subpath（二分長度，每條路徑滾動雜湊取交集）Hard