跳到正文
格致开物MATHWIKI
数学百科/知识地图

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，再看下一个模式字符。若它等于 Pj，长度加 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] 个字符不会漏掉后面的匹配。每次成功比较延长这个关系，每次回退把它缩到仍可能成立的最长长度。

KMP 的失配与回退

文本下标只前进；失配时按前缀函数移动模式。

静态配图与完整推导见本节正文；交互演示需浏览器启用 JavaScript。

Python 实现

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

Python 3
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 规范化和编码单位若不同，必须先明确比较规则；它不会自动把近似拼写或语义相近的词看作匹配。若只需第一个起点，可以在找到完整匹配时立即返回，不必存全部结果。

参考资料

检索自“https://gezhi.wiki/index.php?title=KMP字符串匹配&oldid=1849”