字串匹配基礎#

問題定義#

在主串 (text) 中查找模式串 (pattern) 的位置。

主串：  "ABABDABACDABABCABAB"
模式串："ABABC"
結果：  位置 10

BF 演算法（暴力匹配）#

思路#

逐一比較，失敗時模式串後移一位。

def bf_search(text, pattern):
    n, m = len(text), len(pattern)

    for i in range(n - m + 1):
        if text[i:i+m] == pattern:
            return i

    return -1

複雜度#

最差：O(n × m)
平均：接近 O(n)（實際字串很少連續匹配後失敗）

適用場景：主串和模式串都很短時，BF 夠用且實現簡單。

RK 演算法（Rabin-Karp）#

核心思想#

用雜湊值代替字元逐一比較。

步驟#

計算模式串的雜湊值
滑動視窗計算主串子串的雜湊值
雜湊值相等時再逐字元驗證（避免雜湊碰撞）

滾動雜湊#

假設字串 "abc"，進位制 d = 26

hash("abc") = a×26² + b×26 + c

滑動到 "bcd"：
hash("bcd") = (hash("abc") - a×26²) × 26 + d

RK 演算法程式碼

def rk_search(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return -1

    d = 26  # 字元集大小
    q = 10**9 + 7  # 大質數避免溢出

    # 預計算 d^(m-1)
    h = pow(d, m - 1, q)

    # 計算模式串和第一個視窗的雜湊值
    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

    for i in range(n - m + 1):
        if p_hash == t_hash:
            # 雜湊相等，逐字元驗證
            if text[i:i+m] == pattern:
                return i

        # 滾動計算下一個雜湊值
        if i < n - m:
            t_hash = (d * (t_hash - ord(text[i]) * h) + ord(text[i + m])) % q
            t_hash = (t_hash + q) % q  # 處理負數

    return -1

複雜度#

平均：O(n)
最差：O(n × m)（大量雜湊碰撞時）

注意：
選擇好的雜湊函式減少碰撞
模式串太長時，雜湊值可能溢出

演算法比較#

演算法	預處理	匹配	特點
BF	O(1)	O(n×m)	簡單直觀
RK	O(m)	O(n) 平均	多模式可用
BM	O(m+σ)	O(n/m) 最佳	實務最快
KMP	O(m)	O(n)	理論優美

進階演算法預告：
BM：利用「壞字元」和「好後綴」規則跳過更多字元
KMP：利用模式串自身的重複特性，失敗時跳到最佳位置