2.2 KMP演算法#

概念說明#

KMP（Knuth-Morris-Pratt）演算法解決樸素比對的核心浪費：失配時把整個對齊位置右移一格、把已比對過的字元全部重比一次。KMP 的洞見是：已比對成功的前綴本身就是樣式的一段，其中蘊含樣式的自比資訊。利用這個資訊，我們可以在失配時根據「已成功比對了多長」直接決定右移多遠，並且文本指標永不後退。

具體做法是預處理樣式，建立失敗函數（failure function），也稱 LPS（Longest Proper Prefix which is also a Suffix）：對每個前綴 P[0..i]，記錄其「最長的既是真前綴又是真後綴」的長度。例如 P = ABCABC，前綴 ABCAB 的答案是 AB（長度 2）。這個函數可用兩指標在 O(m) 內算出。

比對時，兩個指標 i（文本）、j（樣式）各前進不後退：當 T[i] == P[j] 時兩者同時加一；當 j 失配且 j > 0 時，令 j = fail[j-1]——即用「已比對前綴的次長自前後綴」對齊，跳過必然失敗的中間位置；當 j == 0 仍失配，i 加一。J 失配跳轉之後仍有可能繼續匹配，因此每個文本字元最多被比較 O(1) 個樣式位置，總時間 O(n)。j 達到 m 時找到一次完整出現：紀錄位置後令 j = fail[j-1] 繼續找（允許重疊出現）。

KMP 體現了重要的演算法設計思想：預處理樣式，讓每個文本字元只需看一次（我們稱之為「線性時間、重複利用已比對資訊」，這也是自動機式字串比對的原型，第 3 章的 Aho-Corasick 是它的多樣式推廣）。

演算法步驟#

建失敗函數：設 k = 0，i 從 1 到 m-1：
當 P[i] == P[k]：fail[i] = k+1，k、i 同加一。
當失配且 k > 0：k = fail[k-1]。
當失配且 k == 0：fail[i] = 0，i 加一。
比對：i、j 從 0 開始；同字元時雙加；失配且 j > 0 時 j = fail[j-1]；j == 0 時 i 加一。
j == m 時找得到：位置 i - m，然後 j = fail[j-1] 續找可能的重疊出現。

Python 程式碼範例#

def build_failure(pat):
    m = len(pat)
    fail = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pat[i] != pat[k]:
            k = fail[k - 1]          # 縮短為次長自前後綴
        if pat[i] == pat[k]:
            k += 1
        fail[i] = k
    return fail

def kmp_search(text, pat):
    fail = build_failure(pat)
    ans, j = [], 0
    for i, ch in enumerate(text):
        while j > 0 and ch != pat[j]:
            j = fail[j - 1]           # 文本指標不後退，僅樣式跳轉
        if ch == pat[j]:
            j += 1
        if j == len(pat):
            ans.append(i - j + 1)
            j = fail[j - 1]           # 允許重疊出現
    return ans

print(build_failure("ABABC"))       # [0, 0, 1, 2, 0]
print(kmp_search("ABABCABABCD", "ABABC"))

# 自製 str.find：KMP 的簡單應用
def kmp_find(text, pat):
    ans = kmp_search(text, pat)
    return ans[0] if ans else -1

print(kmp_find("hello world", "world"))   # 6

# Illustration of why KMP matters: worst case friendly
T = "A" * 100000
P = "A" * 1000 + "B"
import time
t0 = time.time(); kmp_search(T, P); t1 = time.time()
print(f"KMP worstcase 100k text: {(t1-t0):.4f}s")

執行時可觀察：同樣最壞輸入若使用樸素逐字比對會慢數十倍（尤其在長樣式時），而 KMP 仍維持線性。

複雜度分析#

失敗函數：O(m) 時間、O(m) 空間。單調性論證：k 在每次迭代中最多加 1，且 falleback 只會減 k，縮短總量 ≤ 加總量，故為均攤 O(m)。
比對：O(n) 時間（i 單調遞增，j 每次失配減少，變化總量有限）、O(m) 額外空間。
總計：O(n + m)，與樸素比對最壞 O(nm) 相比，這是理論保證。

練習#

寫一個函數印出 KMP 搜尋過程中「文本指標 i 從未後退」的證據：統計每個文本字元被讀取的次數，輸出最大值。
用 KMP 找樣式在文本中的所有不重疊出現（找到後把 j 歸 0）。
給定樣式 P = "aabaaab"，手工計算失敗函數，與程式輸出比對；再想一個最壞的樣式設計（如大量重疊自前後綴），說明失敗函數如何應付。