KMP 字串搜尋教學：原理、程式碼與時間複雜度

KMP 解決什麼問題

字串搜尋要問的是：一個短的模式在較長的文字中出現在哪裡。樸素的方法會嘗試每一個起始位置，並逐字元比對。在一般文字上它很快，但在重複性高的輸入上就很慢：在 aaaaaaaaaa 中搜尋 aaaab，每個位置幾乎都要比對完整個模式，時間複雜度為 O(n × m)。

KMP 在不匹配之後絕不會重讀文字中的字元。Donald Knuth、James H. Morris 與 Vaughan Pratt 於 1977 年在「Fast Pattern Matching in Strings」中發表了它。

用白話說明原理

假設你正在搜尋模式 ABABC，已經匹配了 ABAB，但下一個文字字元不是 C。剛剛匹配的 ABAB 以 AB 結尾，而 AB 也正好是模式的開頭。所以你已經知道下一次嘗試一開始就有 2 個字元匹配，可以直接從模式的第 2 個位置繼續比對，而不必從頭開始。

前綴函式就是用來儲存這些數字。pi[i] 是 pattern[0..i] 的最長真前綴的長度，且該前綴同時也是它的後綴（真的意思是不等於整個字串）。

例如，pi[4] = 3，因為 ABABA 的開頭與結尾都是 ABA。pi[5] = 0，因為 ABABAC 的任何前綴都不是以 C 結尾。

逐步範例

在文字 ABABABC 中搜尋模式 ABABC（前綴函式為 0, 0, 1, 2, 0）。變數 k 記錄目前已匹配的模式字元數。

文字指標向前移動了 7 次，從未往回走。樸素方法則會從位置 1 重新開始，並重複比對一些字元。

Python 實作

def prefix_function(p):
    pi = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]          # fall back to a shorter border
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

def kmp_search(text, pattern):
    """Return the start index of every occurrence (overlaps included)."""
    if not pattern:
        return []
    pi, k, hits = prefix_function(pattern), 0, []
    for i, ch in enumerate(text):
        while k > 0 and ch != pattern[k]:
            k = pi[k - 1]
        if ch == pattern[k]:
            k += 1
        if k == len(pattern):
            hits.append(i - k + 1)
            k = pi[k - 1]          # keep going to find overlapping matches
    return hits

print(prefix_function("ABABACA"))      # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("ABABABC", "ABABC"))  # [2]
print(kmp_search("AAAAA", "AA"))       # [0, 1, 2, 3]

時間與空間複雜度

樸素演算法的最差情況是 O(n × m)，但在自然語言文字上通常接近 O(n)，所以 KMP 的優勢主要出現在重複性高的資料上。

變化版本與常見錯誤

• 回退時差一：不匹配之後要設定 k = pi[k - 1]，而不是 pi[k]。pi 是以最後一個匹配位置作為索引。
• 回退時用 if 而不是 while：在某個字元匹配之前，可能需要連續回退好幾次。
• 完整匹配後忘了重設 k：要找出重疊的匹配，請設定 k = pi[k - 1]；若只要不重疊的匹配，則設為 k = 0。
• 串接技巧：計算 pattern + separator + text 的前綴函式，分隔字元要選擇兩者都未出現的字元；值等於 m 的每個位置都是一個匹配的結尾。
• Z 演算法計算的是一個密切相關的陣列，同樣能在 O(n + m) 內搜尋。

何時使用與實際應用

• 面試題目：實作 strStr()、最短回文（s + "#" + reversed(s) 的前綴函式）、重複的子字串模式、字串的最小週期（m - pi[m - 1]）。
• 實際應用：在 DNA 序列和網路封包串流中搜尋，這些場合很重視線性的最差情況時間。