KMP 演算法：單向舞者

演算法背後的故事：既視感

想像妳正在讀一本書，尋找單詞 “ABABAC”。 妳讀到：「A… B… A… B… A…」 太好了！妳已經匹配了 5 個字元。妳很興奮。 然後妳讀到第 6 個字元……它是 “D”。 “ABABAD”。它不匹配 “ABABAC”。

在樸素演算法中，妳會嘆口氣，回到書的第 2 個字元，從頭再來。 但 KMP 更聰明。它想：「等等。我剛剛匹配了 ‘ABABA’。我知道我看到了什麼。最後一部分 ‘ABA’ 可能是新匹配的開始！我不需要回去。我只需要移動我的模式，讓開頭的 ‘ABA’ 與我剛剛看到的結尾 ‘ABA’ 對齊。」

這就是 KMP (Knuth-Morris-Pratt)。它的文本指標從不後退。它使用一個預先計算的表格來儘可能多地向前滑動模式。

為什麼需要它？

• Ctrl+F: 在海量文檔中查找關鍵字。
• DNA 測序： 在數十億鹼基對的基因組中尋找特定的基因模式。
• 串流數據： KMP 可以即時搜尋數據流（如鍵盤輸入），因為它永遠不需要「倒帶」數據流。

演算法是如何「思考」的

演算法分為兩個階段：

1. 準備 (LPS 表)： 在閱讀這本書之前，KMP 分析模式本身。它構建了一個名為 LPS（最長前綴也是後綴）的陣列。

   • 對於 “ABABAC”：
   • LPS 表會說：「如果妳在索引 5 處失敗了，妳可以安全地跳到索引 3。」

2. 舞蹈 (搜尋)：

   • 它逐個匹配字元。
   • 如果字元匹配：向前移動。
   • 如果不匹配：不要回退文本指標。查看 LPS 表，看看應該將模式指標重置到哪裡。

工程決策：樸素 vs. KMP

• 樸素搜尋： 最壞情況是 $O(N imes M)$。如果妳在 “AAAAAAAAA” 中搜尋 “AAAAA”，它會非常慢。
• KMP： 保證 $O(N + M)$。時間僅取決於文本和模式的長度。

實作參考 (Python)

def compute_lps(pattern):
    # 最長前綴後綴 (Longest Prefix Suffix) 表
    lps = [0] * len(pattern)
    length = 0 # 上一個最長前綴後綴的長度
    i = 1
    
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                # 棘手部分：回退到上一個 LPS
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text, pattern):
    if not pattern: return 0
    lps = compute_lps(pattern)
    i = 0 # 文本索引
    j = 0 # 模式索引
    
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == len(pattern):
            return i - j # 在此索引處找到匹配
            # j = lps[j-1] # 如果要找多個匹配
        
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j-1] # KMP 跳躍！
            else:
                i += 1
    return -1

# 使用範例
print(kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))

小結

KMP 教會我們：失敗包含資訊。與其將不匹配視為徹底的損失，KMP 將其作為跳過不必要工作的線索。它提醒我們，我們不需要總是從零開始；只要我們了解自己（模式），我們就能優雅地從錯誤中恢復。