KMP字符串匹配

KMP 字符串匹配在一段文本中寻找模式串的出现位置。朴素匹配遇到失配时，把模式右移一位并可能从头重比；KMP 利用模式自身的前后缀关系，保留已经匹配的信息，使文本下标只向前走。本文返回所有从 0 开始的匹配起点，重叠出现也分别记录。

一次失配留下了什么

取模式 ABABC 和文本 ABABABABC。最初四个字符 ABAB 相同，但文本下标 4 是 A，模式下标 4 是 C，于是失配。此时已经读过的 ABAB 末尾两字符是 AB，恰等于它的开头两字符。模式右移两格后，这个 AB 仍然成立；应让模式下标回到 2，继续拿同一个文本字符与模式下标 2 比较，而不是把文本下标倒退。

文本ABABABABC依次与起点零、二、四的模式ABABC对齐；前两次在文本下标四和六失配，保留共同前后缀AB，最后在起点四完整匹配 — 失配后的下一行保留已匹配后缀 AB；文本读头只从左向右移动。

向后再走两格，文本下标 6 的 A 又与模式末尾的 C 不同；同样保留 AB，最后在文本起点 4 匹配全部五个字符。图中的三次对齐不是“每次只右移一格”的结果，而是由前后缀长度决定的。

前缀函数

令 $π [j]$ 表示模式前 $j + 1$ 个字符中，既是前缀又是后缀的最长真子串的长度。“真”表示长度小于整个前缀。对于 ABABC：

$j$	0	1	2	3	4
模式字符	A	B	A	B	C
$π [j]$	0	0	1	2	0

例如 ABAB 的最长相同真前后缀是 AB，所以 $π [3] = 2$ ；ABABC 没有非空的相同真前后缀，所以 $π [4] = 0$ 。图把表中第 3 列以前的两段 AB 标出。

模式ABABC的下标零至四和前缀函数零零一二零；ABAB的前两个字符AB与后两个字符AB相同，因此pi三等于二 — 前缀函数只由模式计算；失配时用它决定能够保留多少个已匹配字符。

构造表时，设当前已知相同前后缀长度为 $j$ ，再看下一个模式字符。若它等于 $P_{j}$ ，长度加 1；若不同，就把 $j$ 降到 $π [j - 1]$ ，尝试次长的相同前后缀，直到找到可延长者或降到 0。这不是猜一个较短长度：若长度为 $j$ 的候选失败，下一候选必须同时是已匹配后缀的后缀和模式的前缀，最长者正由 $π [j - 1]$ 给出。

扫描文本与完整匹配

扫描文本时， $j$ 表示当前已经连续匹配的模式字符数。失配时用 $π [j - 1]$ 降低 $j$ ，保持文本位置不变；相等才同时向前推进。当 $j = m$ 时找到一个起点 $i - m + 1$ ，随后设 $j = π [m - 1]$ ，保留完整匹配串可能与下一次匹配重叠的后缀。例如模式 AAA 在 AAAAA 中出现在下标 0、1、2。

正确性依赖一个简单事实：已读文本的末尾 $j$ 个字符与模式前 $j$ 个字符相同。失配后，长度大于 $π [j - 1]$ 的候选已经不可能同时是这段文本的后缀与模式的前缀；保留 $π [j - 1]$ 个字符不会漏掉后面的匹配。每次成功比较延长这个关系，每次回退把它缩到仍可能成立的最长长度。

Python 实现

代码先求模式的前缀函数，再返回全部起点。这里约定空模式匹配文本的每个边界，例如空文本的边界是 0，长度为 2 的文本有边界 0、1、2；非空模式在空文本中没有匹配。

def prefix_function(pattern):
    pi = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    return pi


def kmp_find_all(text, pattern):
    if pattern == "":
        return list(range(len(text) + 1))
    pi = prefix_function(pattern)
    starts = []
    j = 0
    for i, character in enumerate(text):
        while j > 0 and character != pattern[j]:
            j = pi[j - 1]
        if character == pattern[j]:
            j += 1
        if j == len(pattern):
            starts.append(i - j + 1)
            j = pi[j - 1]
    return starts


if __name__ == "__main__":
    assert prefix_function("ABABC") == [0, 0, 1, 2, 0]
    assert kmp_find_all("ABABABABC", "ABABC") == [4]
    assert kmp_find_all("AAAAA", "AAA") == [0, 1, 2]
    assert kmp_find_all("ABC", "") == [0, 1, 2, 3]
    assert kmp_find_all("", "A") == []

比较次数与使用范围

模式长 $m$ 、文本长 $n$ 。构造前缀表时，每次字符相等使 $j$ 增加 1；每次失配回退使 $j$ 至少减少 1，所以全部回退次数受总增加次数约束，为 $O (m)$ 。扫描文本时同理，文本下标只前进 $n$ 次，累计回退为 $O (n)$ 。总时间 $O (n + m)$ ；前缀表需 $O (m)$ 空间，返回 $r$ 个起点还需 $O (r)$ 空间。

KMP 判断的是精确字符相等。大小写、Unicode 规范化和编码单位若不同，必须先明确比较规则；它不会自动把近似拼写或语义相近的词看作匹配。若只需第一个起点，可以在找到完整匹配时立即返回，不必存全部结果。

参考资料

TheAlgorithms/Python：knuth_morris_pratt.py：同题的首个起点实现；本文统一用前缀函数定义并独立编写全部匹配代码。
Sedgewick、Wayne，Substring Search：模式预处理与 KMP 的线性比较界。
先修：算法与复杂度；对照：二分查找。