查看“︁KMP字符串匹配”︁的源代码

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

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

[[File:Gezhi-kmp-alignments.svg|frame|center|alt=文本ABABABABC依次与起点零、二、四的模式ABABC对齐；前两次在文本下标四和六失配，保留共同前后缀AB，最后在起点四完整匹配|失配后的下一行保留已匹配后缀 AB；文本读头只从左向右移动。]]

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

== 前缀函数 ==
令 <math>\pi[j]</math> 表示模式前 <math>j+1</math> 个字符中，'''既是前缀又是后缀的最长真子串'''的长度。“真”表示长度小于整个前缀。对于 <code>ABABC</code>：

{| class="wikitable"
! <math>j</math> !! 0 !! 1 !! 2 !! 3 !! 4
|-
! 模式字符
| A || B || A || B || C
|-
! <math>\pi[j]</math>
| 0 || 0 || 1 || 2 || 0
|}

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

[[File:Gezhi-kmp-prefix.svg|frame|center|alt=模式ABABC的下标零至四和前缀函数零零一二零；ABAB的前两个字符AB与后两个字符AB相同，因此pi三等于二|前缀函数只由模式计算；失配时用它决定能够保留多少个已匹配字符。]]

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

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

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

<math-experiment type="algorithm" demo="kmp" />

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

<div class="math-code-example">
<div class="math-code-language">Python 3</div>
<pre class="math-code-source" data-language="python">
def prefix_function(pattern):
    pi = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i]&#32;!= 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&#32;!= 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") == []
</pre>
</div>

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

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

== 参考资料 ==
* [https://github.com/TheAlgorithms/Python/blob/c27e95123cb7e2fef5b15e64b5e800201cc7665c/strings/knuth_morris_pratt.py TheAlgorithms/Python：knuth_morris_pratt.py]：同题的首个起点实现；本文统一用前缀函数定义并独立编写全部匹配代码。
* [https://algs4.cs.princeton.edu/53substring/ Sedgewick、Wayne，Substring Search]：模式预处理与 KMP 的线性比较界。
* 先修：[[算法与复杂度]]；对照：[[二分查找]]。
[[分类:算法]]