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 将其作为跳过不必要工作的线索。它提醒我们，我们不需要总是从零开始；只要我们了解自己（模式），我们就能优雅地从错误中恢复。