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 序列和网络数据包流中搜索，这些场景看重线性的最坏时间。