BM 與 KMP 演算法#

KMP 演算法#

核心概念#

當匹配失敗時，利用已匹配的「好前綴」資訊，將模式串多滑動幾位。

主串：    A B A B A B C
模式串：  A B A B C
               ↑ 失敗

傳統：後移 1 位
KMP：後移 2 位（利用 "ABAB" 的前綴 "AB" = 後綴 "AB"）

關鍵：next 陣列（失效函式）#

next[i] = 子串 pattern[0..i] 的最長相等前後綴長度 - 1

模式串：A B A B C
next：  -1 -1 0 1 -1

解釋：
- "A": 無前後綴 → -1
- "AB": 無相等前後綴 → -1
- "ABA": "A" = "A" → 0
- "ABAB": "AB" = "AB" → 1
- "ABABC": 無相等前後綴 → -1

next 陣列計算#

next 陣列程式碼

def get_next(pattern):
    m = len(pattern)
    next_arr = [-1] * m
    k = -1

    for i in range(1, m):
        # 當 pattern[k+1] != pattern[i] 時，回退
        while k != -1 and pattern[k + 1] != pattern[i]:
            k = next_arr[k]

        if pattern[k + 1] == pattern[i]:
            k += 1

        next_arr[i] = k

    return next_arr

理解技巧：這是一個自我匹配的過程，用模式串匹配自己來找重複結構。

KMP 主函式#

def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    next_arr = get_next(pattern)

    j = 0
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = next_arr[j - 1] + 1

        if text[i] == pattern[j]:
            j += 1

        if j == m:
            return i - m + 1

    return -1

複雜度#

預處理：O(m)
匹配：O(n)
總計：O(n + m)

BM 演算法#

核心規則#

壞字元規則：從後往前匹配，遇到不匹配字元時，將模式串滑動到該字元對齊
好後綴規則：利用已匹配的後綴，找模式串中的相同子串對齊

BM 的特點：
從後往前匹配
實務中通常比 KMP 更快
最佳情況 O(n/m)

為什麼 BM 更快？#

主串：    ... X Y Z A B C D E F ...
模式串：        A B C D E F

從後往前：F 匹配，E 匹配，D 匹配，C 匹配，B 匹配，A 匹配 → 成功

若 X 與模式串不匹配且 X 不在模式串中：
→ 直接跳過整個模式串長度！

演算法對比#

特性	KMP	BM
匹配方向	從前往後	從後往前
時間複雜度	O(n)	O(n/m) ~ O(n)
預處理	next 陣列	壞字元表 + 好後綴表
實現難度	中等	較複雜
實務效能	好	更好（統計意義上）

應用場景#

場景	推薦演算法
文字編輯器搜尋	BM（快）
實現簡單優先	KMP
字元集小、模式短	RK
多模式匹配	AC 自動機

面試建議：
理解 KMP 的 next 陣列原理
能手寫 KMP 程式碼
了解 BM 的思想，但不需要背誦細節

最難理解的部分：k = next[k]

當 pattern[k+1] != pattern[i] 時，需要找次長的相等前後綴。

假設 next[i-1] = k-1
即 pattern[0..k-1] = pattern[i-k..i-1]（最長相等前後綴）

若 pattern[k] != pattern[i]：
- 需要找 pattern[0..k-1] 的最長相等前後綴
- 這就是 next[k-1]！
- 所以 k = next[k]

本質上是利用已經計算好的結果，避免重複計算。