Knuth–Morris–Pratt 算法

克努特–莫里斯–普拉特算法
术语名称	克努特–莫里斯–普拉特算法
英语名称	Knuth–Morris–Pratt algorithm
别名	KMP算法, KMP algorithm

KMP 算法(Knuth–Morris–Pratt algorithm, KMP algorithm)是一种高效的字符串匹配算法，用于在长字符串中匹配短字符串的出现。名称来自发明人姓氏。

暴力搜索中每个位置尝试匹配相对。 KMP 的核心思想是在进行匹配时记录同一段字符串的公共前后缀信息，从而在判断匹配失败时，直接按照当前位置已经匹配到了的前缀长度进行回溯，不需要匹配中间的部分，以减少匹配过程中的回溯次数，显著提升匹配效率。

记号

字符串匹配问题中，目标是在长字符串中寻找一个短字符串的第一次出现。称短字符串为“模式(pattern)”串，长度记为 [math]\displaystyle{ m }[/math] ，长字符串长度记为 [math]\displaystyle{ n }[/math] 。以下用长字符串为 ABABCDABCDABDE ，短字符串为 ABCDABD 举例。

原理

字符串匹配问题的暴力算法要在每个位置尝试从头开始匹配模式，也就是需要最多 [math]\displaystyle{ (n-m)m = O(mn) }[/math] 次将每一个位置开始的字符串和模式串依次逐字符匹配。

AABCDABCDABDE
ABCDABD
 ABCDABD
  ABCDABD
   ABCDABD
    ABCDABD
     ABCDABDE

KMP 算法中，考虑到一个字符串在进行匹配时，即使中途发现不匹配，实际上也已经检查了一部分字符。如果我们提前确认模式串中到每个字符处时一定已经匹配的最大长度，就可以按照这个长度进行继续匹配，而不用回溯到前面的位置。下面讨论以下为什么这个长度是可行的，且不逐字母回溯也不会漏掉中间的可能匹配位置。

如果长字符串中存在一部分匹配模式串，那么匹配部分的前缀也一定匹配模式串的同一个前缀。
现有模式串 ABCDABDE ，若在匹配时在最后一个 D 处失败，可以知道当前已经匹配到了 D 之前的模式串前缀 ABCDAB 。
模式串前缀 ABCDAB 有最长公共真前后缀(longest border) AB ，也就是说模式串前缀同时以 AB 开始和结束。既然当前匹配 ABCDAB ，说明最后匹配 AB ，也就是模式串最开始的 AB ，因此把开始匹配位置改到当前匹配中 D 的位置 - 2 也是一个部分匹配的状态。此处的 2 是 AB 的长度。
对于中间的任何位置，比如第一个 C 所在的位置。根据匹配过程，在 D 处不匹配时，从 C 开始已经匹配了 CDAB ，这一定是模式串前缀 ABCDAB 的一个真后缀。由于这个真后缀长于 ABCDAB 的最长公共真前后缀 AB ，那么 CDAB 就不可能是模式串的一个前缀（否则，同时是真前缀、真后缀，那么也是一个公共真前后缀，还是更长的，与假设的最长矛盾），也就是从 C 开始一定不匹配模式串。

AABCDABCDABDE
ABCDABD
 ABCDABD
     ABCDABDE

因此，对模式串的每一个前缀计算其最长公共真前后缀长度，然后以此为走向，就能得到实际需要跳转的匹配位置。这个“跳转的下一个位置”的列表一般称为“ next 数组”。

ABCDABDE
-000-020

模式串中的 D 下方为 2 ，意味着到此之前的前缀部分 ABCDAB 有长度为 2 的最长公共真前后缀 AB 。如果在此处不匹配，视作已经匹配了 2 个字符，重新匹配当前字符时只需要从模式串下标为 2 的字符开始继续匹配（若字符串下标以 0 开始）。
模式串中的 E 下方为 0 ，意味着到此之前的前缀部分 ABCDABD 的最长公共真前后缀长度为 0 , 是空字符串。如果在此处不匹配，视作已经匹配了 0 个字符，也就是重新匹配当前字符时回到下标为 0 的第一个字符继续匹配。
模式串中的第一个 A 下方为特殊值 - （一般选择 -1 作为特殊值），是因为到此之前的前缀部分是空串，不存在真前缀。如果在此处不匹配，不重新匹配当前字符，而是开始从头匹配下一个字符。
模式串中的第二个 AB 下方为 -0 ，取值是和第一次出现相同。以 B 为例，尽管不包含它的前缀 ABCDA 是 1 ，但是包含这个字符本身的前缀 ABCDAB 却有着相同的前后缀，如果当前不匹配 B 则不需要跳转到已匹配 A 的位置，而是和已匹配 A 后在第一个 B 处不匹配同样处理，因此取值与第一个 B 相同。也就是说当一个前缀 ABCDAB 得到了最长其重复部分的前缀 AB 后，不再单独计算这两个位置，而是重复上一次的取值。

下面列举几个其他的模式串来验证以上规则：

ABACABABC
-0-1-1-32
ABACABABA
-0-1-0-3-

伪代码

过程 KMP构建部分匹配表
别名 kmp_calc_next
参数 pattern : 字符串 // 模式串
返回 : 整数的数组 // next 数组

令 m ← |pattern|
创建数组 nextₘ[0..m-1] // 部分匹配表（next数组）

令 next₀ ← -1 // 特殊值，即上述原理中的 - 标记

令 i ← 0 // 索引变量 0 -> m-1
令 j ← -1 // 参照变量，指向相同内容第一次出现位置
循环 i
当 i < m - 1 时
执行
    如果 j = -1 那么
        令 i ← i+1, j ← j+1
        令 nextᵢ ← j
    否则 如果 patternᵢ = patternⱼ 那么
        令 i ← i+1, j ← j+1
        令 nextᵢ ← nextⱼ
    否则
        令 j ← nextⱼ
继续循环


过程 KMP匹配
别名 kmp_match
参数 text : 字符串 // 主文本
参数 pattern : 字符串 // 模式串
返回 : 整数的可选值 // 首次匹配位置

令 n ← |text|, m ← |pattern|

令 i ← 0, j ← 0
循环 i, j // 主文本和模式串各自的下标循环变量
当 i < n 时
执行
    如果 j = -1 那么 // 读入下一个字符，从 0 开始匹配
        令 i ← i+1, j ← j+1
    否则 如果 textᵢ = patternⱼ 则 // 继续匹配下一个字符
        令 i ← i+1, j ← j+1
        如果 j = m 那么
            返回 i - j // 返回匹配起始位置
    否则 // 重新匹配当前字符，跳转模式串 next 位置
        令 j ← nextⱼ
继续循环

返回 空可选值 // 未找到匹配

时间复杂度

构建部分匹配表遍历一次模式串，时间复杂度为 [math]\displaystyle{ O(m) }[/math] 。

匹配过程中，从左到右遍历一次主字符串，时间复杂度为 [math]\displaystyle{ O(n) }[/math] 。

因此，总计复杂度为 [math]\displaystyle{ O(n+m) }[/math] 级别。

空间复杂度

算法的空间复杂度在于需要额外空间处理 next 数组，因此为 [math]\displaystyle{ O(m) }[/math] 。