彻底理解KMP算法 – wiki基地

作者： /

彻底理解 KMP 算法：字符串匹配的艺术

字符串匹配（String Matching），是计算机科学中的一个经典问题。简单来说，就是在一段较长的文本（Text）中查找是否存在一个较短的模式（Pattern），如果存在，则返回其出现的位置。这个看似简单的问题，在诸如文本编辑器的查找替换功能、DNA 序列分析、网络入侵检测等众多领域都有着广泛的应用。

最直观的字符串匹配算法是朴素匹配算法（Naive String Matching）。它的思路非常简单：将模式串与文本串从头开始逐个字符比较。如果当前字符匹配，则继续比较下一个字符；如果匹配失败，则将模式串向右移动一位，然后重新从模式串的开头与文本串的当前位置开始比较。

让我们用一个例子来看看朴素匹配算法：

文本串 T = “ABABCABAB”
模式串 P = “ABAB”

  1. 比较 T[0…3] 和 P[0…3]:
    • T[0] == P[0] (‘A’ == ‘A’)
    • T[1] == P[1] (‘B’ == ‘B’)
    • T[2] == P[2] (‘A’ == ‘A’)
    • T[3] == P[3] (‘B’ == ‘B’)
    • 完全匹配！在索引 0 处找到一个匹配。

假设我们还要找后续匹配，或者模式更长：

文本串 T = “AAAAAB”
模式串 P = “AAB”

  1. 比较 T[0…2] 和 P[0…2]:

    • T[0] == P[0] (‘A’ == ‘A’)
    • T[1] == P[1] (‘A’ == ‘A’)
    • T[2] != P[2] (‘A’ != ‘B’)
    • 在 T[2] 处失配。将模式串向右移动一位。

  2. 比较 T[1…3] 和 P[0…2]:

    • T[1] == P[0] (‘A’ == ‘A’)
    • T[2] == P[1] (‘A’ == ‘A’)
    • T[3] != P[2] (‘A’ != ‘B’)
    • 在 T[3] 处失配。将模式串向右移动一位。

  3. 比较 T[2…4] 和 P[0…2]:

    • T[2] == P[0] (‘A’ == ‘A’)
    • T[3] == P[1] (‘A’ == ‘A’)
    • T[4] != P[2] (‘A’ != ‘B’)
    • 在 T[4] 处失配。将模式串向右移动一位。

  4. 比较 T[3…5] 和 P[0…2]:

    • T[3] == P[0] (‘A’ == ‘A’)
    • T[4] == P[1] (‘A’ == ‘A’)
    • T[5] == P[2] (‘B’ == ‘B’)
    • 完全匹配！在索引 3 处找到一个匹配。

朴素匹配算法的优点是简单易懂，易于实现。但其效率在某些情况下非常低下。考虑文本串是 n 个 ‘A’ 后面跟一个 ‘B’ (AAAA...AB)，模式串是 m-1 个 ‘A’ 后面跟一个 ‘B’ (AAA...AB)。每次比较都会在模式串的最后一个字符处失配，然后模式串只向右移动一个位置。文本串的每个位置都需要与模式串几乎所有字符进行比较。最坏情况下，朴素匹配算法的时间复杂度为 O(nm)，其中 n 是文本串长度，m 是模式串长度。这对于大规模文本匹配是不可接受的。

仔细观察朴素匹配算法的失配过程，我们可以发现它的主要问题在于：当发生失配时，它完全忽略了已经匹配成功的字符所提供的任何信息。例如，在上面的例子 T = "AAAAAB", P = "AAB" 中，第一次在 T[2] (‘A’) 和 P[2] (‘B’) 处失配时，我们已经知道 T[0..1] 是 “AA” 并且与 P[0..1] “AA” 匹配。但是朴素算法将模式串移动一位后，又重新比较 T[1] 和 P[0]，这显然是多余的，因为我们知道 T[1] 是 ‘A’，而 P[0] 也是 ‘A’。

KMP 算法（Knuth-Morris-Pratt Algorithm），就是为了解决朴素匹配算法的效率问题而诞生的。它的核心思想是：当模式串与文本串发生失配时，模式串不需要回溯（即文本串指针 i 不会减小），而是根据模式串自身的特点，计算出模式串下一次应该移动到的位置。这个“自身的特点”就是模式串中前缀和后缀的重叠部分。

KMP 算法的核心：部分匹配表（Partial Match Table）

KMP 算法之所以能避免不必要的文本串回溯，是因为它在失配发生时，能够利用之前已经匹配成功的模式串前缀的已知信息。这些信息被存储在一个称为部分匹配表（Partial Match Table），或称为失配表（Failure Function），在某些文献中也称作 next 数组的辅助数组中。

为了构建这个表，我们需要理解几个概念：

  • 前缀（Prefix）: 指一个字符串从开头到某个位置的所有字符组成的子串。例如，字符串 “ABCD” 的前缀有 “A”, “AB”, “ABC”, “ABCD”。
  • 后缀（Suffix）: 指一个字符串从某个位置到结尾的所有字符组成的子串。例如，字符串 “ABCD” 的后缀有 “D”, “CD”, “BCD”, “ABCD”。
  • 真前缀（Proper Prefix）: 指除了字符串本身之外的所有前缀。例如，”ABCD” 的真前缀有 “A”, “AB”, “ABC”。
  • 真后缀（Proper Suffix）: 指除了字符串本身之外的所有后缀。例如，”ABCD” 的真后缀有 “D”, “CD”, “BCD”。

部分匹配表（next 数组）的定义：对于模式串 P，next[j] 的值定义为：模式串 P 的前 j 个字符（即子串 P[0...j-1]）中，最长的相等的真前缀和真后缀的长度。

我们通常计算 next 数组的长度为模式串的长度 m。next[j] 对应于模式串中索引 j 的字符发生失配时的信息。也就是说，如果 P[j] 与文本串中的字符失配，那么已经匹配成功的部分是 P[0...j-1]。此时，我们需要知道 P[0...j-1] 这个子串中，最长的相等的真前缀和真后缀的长度是多少。

举例说明 next 数组的计算：

模式串 P = “ABABCABAB”，长度 m = 9。
我们计算 next[0] 到 next[8]。

  • next[0]：对应模式串 P 的前 0 个字符（空串）。空串没有真前缀和真后缀，最长相等真前缀/后缀长度为 0。然而，在实际的 KMP 搜索实现中，next[0] 通常被设为 -1，这是一个哨兵值，表示如果模式串的第一个字符 P[0] 就失配，那么需要移动文本串指针 i 并重新从 P[0] 开始比较。所以我们约定 next[0] = -1。
  • next[1]：对应模式串 P 的前 1 个字符 “A”。真前缀和真后缀都是空串。最长相等真前缀/后缀长度为 0。next[1] = 0。
  • next[2]：对应模式串 P 的前 2 个字符 “AB”。真前缀有 “A”，真后缀有 “B”。没有相等的真前缀和真后缀。最长相等真前缀/后缀长度为 0。next[2] = 0。
  • next[3]：对应模式串 P 的前 3 个字符 “ABA”。真前缀有 “A”, “AB”，真后缀有 “A”, “BA”。最长的相等真前缀和真后缀是 “A”，长度为 1。next[3] = 1。
  • next[4]：对应模式串 P 的前 4 个字符 “ABAB”。真前缀有 “A”, “AB”, “ABA”，真后缀有 “B”, “AB”, “BAB”。最长的相等真前缀和真后缀是 “AB”，长度为 2。next[4] = 2。
  • next[5]：对应模式串 P 的前 5 个字符 “ABABC”。真前缀有 “A”, “AB”, “ABA”, “ABAB”，真后缀有 “C”, “BC”, “ABC”, “BABC”。没有相等的真前缀和真后缀。最长相等真前缀/后缀长度为 0。next[5] = 0。
  • next[6]：对应模式串 P 的前 6 个字符 “ABabca”。真前缀有 “A”, “AB”, “ABA”, “ABAB”, “ABABC”，真后缀有 “A”, “CA”, “BCA”, “ABCA”, “BABCA”。最长的相等真前缀和真后缀是 “A”，长度为 1。next[6] = 1。
  • next[7]：对应模式串 P 的前 7 个字符 “ABABCAB”。真前缀有 “A”, “AB”, “ABA”, “ABAB”, “ABABC”, “ABabca”，真后缀有 “B”, “AB”, “CAB”, “BCAB”, “ABCAB”, “CABCAB”。最长的相等真前缀和真后缀是 “AB”，长度为 2。next[7] = 2。
  • next[8]：对应模式串 P 的前 8 个字符 “ABABCABA”。真前缀有 “A”, “AB”, “ABA”, “ABAB”, “ABABC”, “ABabca”, “ABABCAB”，真后缀有 “A”, “BA”, “ABA”, “CABA”, “BCABA”, “ABCABA”, “BABCABA”。最长的相等真前缀和真后缀是 “ABA”，长度为 3。next[8] = 3。

所以，对于模式串 “ABABCABAB”，其 next 数组为 [-1, 0, 0, 1, 2, 0, 1, 2, 3]。

next 数组的构建算法

如何高效地计算 next 数组？我们可以利用 next 数组自身的性质进行递推计算。计算 next[j] 可以利用 next[j-1] 的信息。

构建 next 数组的过程与 KMP 的搜索过程非常相似，可以看作是模式串与自己进行匹配。

假设我们已经计算出了 next[0] 到 next[j-1]，现在要计算 next[j]。
next[j] 表示模式串 P[0...j-1] 这个子串中，最长相等真前缀和真后缀的长度。

我们可以使用两个指针：
* i：当前正在计算 next 值的模式串的索引，从 1 到 m-1。我们要计算 next[i]。
* k：表示当前比较的前缀的下一个字符的索引，同时也代表了当前匹配到的最长相等真前缀和真后缀的长度。初始时 k=0。

算法步骤：
1. 初始化 next 数组，next[0] = -1。
2. 初始化两个指针 i = 0, k = -1。（这里的 i 用来遍历模式串 P，k 用来指示前缀的当前位置和匹配长度）
3. 循环 i 从 1 到 m-1：
* 设 k = next[i-1]。这是因为 next[i-1] 已经告诉我们 P[0...i-2] 的最长相等真前缀/后缀长度是 k。现在我们看 P[0...i-1]，如果 P[i-1] 等于 P[k]，那么 P[0...k] 就是 P[0...i-1] 的一个新的、更长的相等真前缀/后缀，长度为 k+1。
* 更常见的构建方式（与搜索逻辑更贴合）：
* 初始化 next[0] = -1。
* 初始化 i = 0 (模式串当前字符索引), j = -1 (已匹配前缀的下一个字符索引)。
* 循环 i 从 0 到 m-1：
* 计算 next[i+1] 的值。
* 当 j != -1 且 P[i] != P[j] 时，说明当前字符 P[i] 与前缀的下一个字符 P[j] 不匹配。需要回溯 j 到 next[j]，寻找更短的相等真前缀/后缀。重复此步骤直到 j == -1 或 P[i] == P[j]。
* 如果 P[i] == P[j] (或 j == -1)，说明找到了可以扩展的匹配前缀。j 增加 1 (j++)。
* 将当前的 j 值赋给 next[i+1]。
* 使用刚才的例子 P = "ABABCABAB", m = 9。next 数组大小 10（索引 0 到 9）。
* next[0] = -1。
* i=0, j=-1: j == -1 为真。i++ -> i=1, j++ -> j=0. next[1] = j = 0.
* i=1, j=0: P[1] ('B') != P[j] ('A'). j = next[j] = next[0] = -1.
* i=1, j=-1: j == -1 为真。i++ -> i=2, j++ -> j=0. next[2] = j = 0.
* i=2, j=0: P[2] ('A') == P[j] ('A'). i++ -> i=3, j++ -> j=1. next[3] = j = 1.
* i=3, j=1: P[3] ('B') == P[j] ('B'). i++ -> i=4, j++ -> j=2. next[4] = j = 2.
* i=4, j=2: P[4] ('C') != P[j] ('A'). j = next[j] = next[2] = 0.
* i=4, j=0: P[4] ('C') != P[j] ('A'). j = next[j] = next[0] = -1.
* i=4, j=-1: j == -1 为真. i++ -> i=5, j++ -> j=0. next[5] = j = 0.
* i=5, j=0: P[5] ('A') == P[j] ('A'). i++ -> i=6, j++ -> j=1. next[6] = j = 1.
* i=6, j=1: P[6] ('B') == P[j] ('B'). i++ -> i=7, j++ -> j=2. next[7] = j = 2.
* i=7, j=2: P[7] ('A') == P[j] ('A'). i++ -> i=8, j++ -> j=3. next[8] = j = 3.
* i=8, j=3: P[8] ('B') == P[j] ('B'). i++ -> i=9, j++ -> j=4. next[9] = j = 4.
* 循环结束 (i reaches m).
* 得到的 next 数组（ size m+1，索引 0 到 9）是 [-1, 0, 0, 1, 2, 0, 1, 2, 3, 4]。

这个构建算法的时间复杂度是 O(m)。尽管有内层的 while 循环，但 j 的值在每次 j = next[j] 操作时都会减小，而在匹配成功时 j 只会增加（最多增加 m 次）。因此，j 的总减少量不会超过总增加量，整个构建过程的总操作次数是线性的，与模式串长度 m 成正比。空间复杂度是 O(m) 用于存储 next 数组。

KMP 搜索算法

有了 next 数组，就可以进行高效的字符串搜索了。
使用两个指针：
* i：文本串 T 的当前字符索引，从 0 到 n-1。
* j：模式串 P 的当前字符索引，从 0 到 m-1。

算法步骤：
1. 初始化 i = 0, j = 0。
2. 循环 i 从 0 到 n-1：
* 当 j != -1 且 T[i] != P[j] 时：发生失配。此时 T[i-j...i-1] 已经与 P[0...j-1] 匹配。根据 next 数组的定义，P[0...next[j]-1] 是 P[0...j-1] 最长的相等真前缀和真后缀。我们将模式串向右移动，使得 P[0...next[j]-1] 对齐到文本串中原来与 P[j-next[j]...j-1] 匹配的位置。这意味着模式串的新比较位置应该从 P[next[j]] 开始。所以，更新 j = next[j]。请注意，文本串指针 i 在这个过程中不回溯。
* 如果 j == -1 或者 T[i] == P[j]：当前字符匹配（或者 j 被重置为 -1，表示需要从模式串的第一个字符开始重新比较，此时文本串指针 i 也需要前进）。将两个指针都向前移动一位：i++, j++。
* 如果 j == m：找到了一个完整的匹配！模式串 P 出现在文本串 T 的索引 i - m 处。记录匹配位置。为了寻找下一个可能的匹配，我们需要将模式串向前滑动。已经匹配的部分 P[0...m-1] 与 T[i-m...i-1] 相同。根据 next 数组，P[0...next[m]-1] 是 P[0...m-1] 最长的相等真前缀和真后缀。为了继续搜索，模式串应该滑动到使 P[0...next[m]-1] 对齐到 T[i-next[m]...i-1]。这意味着下一个比较应该从模式串的 P[next[m]] 开始。所以，更新 j = next[m]，并继续外层循环（此时 i 已经增加了，指向匹配结束位置的下一个字符）。

示例搜索过程

文本串 T = “ABABDABACDABABCABAB”， n = 21
模式串 P = “ABABCABAB”， m = 9
next 数组 (size 10) = [-1, 0, 0, 1, 2, 0, 1, 2, 3, 4]

初始：i = 0, j = 0

  1. i=0, j=0: T[0] ('A') == P[0] ('A'). Match. i++ -> 1, j++ -> 1.
  2. i=1, j=1: T[1] ('B') == P[1] ('B'). Match. i++ -> 2, j++ -> 2.
  3. i=2, j=2: T[2] ('A') == P[2] ('A'). Match. i++ -> 3, j++ -> 3.
  4. i=3, j=3: T[3] ('B') == P[3] ('B'). Match. i++ -> 4, j++ -> 4.
  5. i=4, j=4: T[4] ('D') != P[4] ('C'). Mismatch. j becomes next[j] = next[4] = 2. i remains 4.
  6. i=4, j=2: T[4] ('D') != P[2] ('A'). Mismatch. j becomes next[j] = next[2] = 0. i remains 4.
  7. i=4, j=0: T[4] ('D') != P[0] ('A'). Mismatch. j becomes next[j] = next[0] = -1. i remains 4.
  8. i=4, j=-1: j == -1. i++ -> 5, j++ -> 0.
  9. i=5, j=0: T[5] ('A') == P[0] ('A'). Match. i++ -> 6, j++ -> 1.
  10. i=6, j=1: T[6] ('B') == P[1] ('B'). Match. i++ -> 7, j++ -> 2.
  11. i=7, j=2: T[7] ('A') == P[2] ('A'). Match. i++ -> 8, j++ -> 3.
  12. i=8, j=3: T[8] ('C') != P[3] ('B'). Mismatch. j becomes next[j] = next[3] = 1. i remains 8.
  13. i=8, j=1: T[8] ('C') != P[1] ('B'). Mismatch. j becomes next[j] = next[1] = 0. i remains 8.
  14. i=8, j=0: T[8] ('C') != P[0] ('A'). Mismatch. j becomes next[j] = next[0] = -1. i remains 8.
  15. i=8, j=-1: j == -1. i++ -> 9, j++ -> 0.
  16. i=9, j=0: T[9] ('D') != P[0] ('A'). Mismatch. j becomes next[j] = next[0] = -1. i remains 9.
  17. i=9, j=-1: j == -1. i++ -> 10, j++ -> 0.
  18. i=10, j=0: T[10] ('A') == P[0] ('A'). Match. i++ -> 11, j++ -> 1.
  19. i=11, j=1: T[11] ('B') == P[1] ('B'). Match. i++ -> 12, j++ -> 2.
  20. i=12, j=2: T[12] ('A') == P[2] ('A'). Match. i++ -> 13, j++ -> 3.
  21. i=13, j=3: T[13] ('B') == P[3] ('B'). Match. i++ -> 14, j++ -> 4.
  22. i=14, j=4: T[14] ('C') == P[4] ('C'). Match. i++ -> 15, j++ -> 5.
  23. i=15, j=5: T[15] ('A') == P[5] ('A'). Match. i++ -> 16, j++ -> 6.
  24. i=16, j=6: T[16] ('B') == P[6] ('B'). Match. i++ -> 17, j++ -> 7.
  25. i=17, j=7: T[17] ('A') == P[7] ('A'). Match. i++ -> 18, j++ -> 8.
  26. i=18, j=8: T[18] ('B') == P[8] ('B'). Match. i++ -> 19, j++ -> 9.
  27. i=19, j=9: j == m. 发现一个匹配，起始索引是 i - m = 19 - 9 = 10。
    为了继续搜索，更新 j = next[m] = next[9] = 4. i 保持 19 (在循环结束时自然会变成 20).
  28. i=19, j=4. 继续循环。i 变成 20。
  29. i=20, j=4: i < n (20 < 21) 为真。T[20] ('A') == P[4] ('C') – Oh wait, the trace logic was slightly off. Let’s restart the search trace with the correct loop structure.

Corrected Search Algorithm Trace:

Initialize i = 0, j = 0. Loop while i < n.

Text T = “ABABDABACDABABCABAB”, n = 21
Pattern P = “ABABCABAB”, m = 9
Next array (size m=9, indices 0 to 8, next[j] for P[0…j-1], next[0]=-1) = [-1, 0, 0, 1, 2, 0, 1, 2, 3] – Let’s use this smaller next array as it’s common. When mismatch at P[j], new j is next[j].
Ah, no, the m+1 size next array with next[m] is cleaner for the match found case. Let’s stick with the size m+1 [-1, 0, 0, 1, 2, 0, 1, 2, 3, 4] (indices 0 to 9). If mismatch at P[j] (T[i] != P[j]), new pattern index is next[j]. If match found (j==m), new pattern index is next[m].

Initial: i = 0, j = 0. Loop while i < n.

  1. i=0, j=0: T[0] ('A') == P[0] ('A'). Match. i++ -> 1, j++ -> 1.
  2. i=1, j=1: T[1] ('B') == P[1] ('B'). Match. i++ -> 2, j++ -> 2.
  3. i=2, j=2: T[2] ('A') == P[2] ('A'). Match. i++ -> 3, j++ -> 3.
  4. i=3, j=3: T[3] ('B') == P[3] ('B'). Match. i++ -> 4, j++ -> 4.
  5. i=4, j=4: T[4] ('D') != P[4] ('C'). Mismatch. j becomes next[j] = next[4] = 2. i remains 4.
  6. i=4, j=2: T[4] ('D') != P[2] ('A'). Mismatch. j becomes next[j] = next[2] = 0. i remains 4.
  7. i=4, j=0: T[4] ('D') != P[0] ('A'). Mismatch. j becomes next[j] = next[0] = -1. i remains 4.
  8. i=4, j=-1: j == -1. i++ -> 5, j++ -> 0.
  9. i=5, j=0: T[5] ('A') == P[0] ('A'). Match. i++ -> 6, j++ -> 1.
  10. i=6, j=1: T[6] ('B') == P[1] ('B'). Match. i++ -> 7, j++ -> 2.
  11. i=7, j=2: T[7] ('A') == P[2] ('A'). Match. i++ -> 8, j++ -> 3.
  12. i=8, j=3: T[8] ('C') != P[3] ('B'). Mismatch. j becomes next[j] = next[3] = 1. i remains 8.
  13. i=8, j=1: T[8] ('C') != P[1] ('B'). Mismatch. j becomes next[j] = next[1] = 0. i remains 8.
  14. i=8, j=0: T[8] ('C') != P[0] ('A'). Mismatch. j becomes next[j] = next[0] = -1. i remains 8.
  15. i=8, j=-1: j == -1. i++ -> 9, j++ -> 0.
  16. i=9, j=0: T[9] ('D') != P[0] ('A'). Mismatch. j becomes next[j] = next[0] = -1. i remains 9.
  17. i=9, j=-1: j == -1. i++ -> 10, j++ -> 0.
  18. i=10, j=0: T[10] ('A') == P[0] ('A'). Match. i++ -> 11, j++ -> 1.
  19. i=11, j=1: T[11] ('B') == P[1] ('B'). Match. i++ -> 12, j++ -> 2.
  20. i=12, j=2: T[12] ('A') == P[2] ('A'). Match. i++ -> 13, j++ -> 3.
  21. i=13, j=3: T[13] ('B') == P[3] ('B'). Match. i++ -> 14, j++ -> 4.
  22. i=14, j=4: T[14] ('C') == P[4] ('C'). Match. i++ -> 15, j++ -> 5.
  23. i=15, j=5: T[15] ('A') == P[5] ('A'). Match. i++ -> 16, j++ -> 6.
  24. i=16, j=6: T[16] ('B') == P[6] ('B'). Match. i++ -> 17, j++ -> 7.
  25. i=17, j=7: T[17] ('A') == P[7] ('A'). Match. i++ -> 18, j++ -> 8.
  26. i=18, j=8: T[18] ('B') == P[8] ('B'). Match. i++ -> 19, j++ -> 9.
  27. i=19, j=9: j == m (9 == 9). 匹配成功！ 匹配起始索引是 i - m = 19 - 9 = 10。
    为了查找下一个匹配，需要更新 j。新的 j 值是 next[m] = next[9] = 4. (i 将在下次循环迭代时更新).
  28. i=19, j=4: Loop continues. i becomes 20.
  29. i=20, j=4: i < n (20 < 21) is true. T[20] ('A') != P[4] ('C'). Mismatch. j becomes next[j] = next[4] = 2. i remains 20.
  30. i=20, j=2: T[20] ('A') == P[2] ('A'). Match. i++ -> 21, j++ -> 3.
  31. i=21, j=3: i == n (21 == 21). Loop terminates.

搜索结束。在索引 10 处找到一个匹配。

通过这个例子，我们可以看到 KMP 算法的关键在于：当失配发生时 (T[i] != P[j])，它利用 next[j] 的信息，直接将模式串的 P[next[j]] 对齐到文本串的 T[i]，而 T[i] 之前的字符 T[i-j...i-1] 中，已经与 P[0...j-1] 匹配的部分，其长度为 next[j] 的后缀恰好等于模式串长度为 next[j] 的前缀。因此，新的比较可以从 T[i] 与 P[next[j]] 开始，并且可以确定 T[i-next[j]...i-1] 这 next[j] 个字符是肯定能与 P[0...next[j]-1] 匹配的，无需重复比较。文本串指针 i 从未减小，这是 KMP 高效的关键。

KMP 算法的正确性与复杂度分析

正确性：
KMP 算法的正确性基于 next 数组的性质。当 P[j] 与 T[i] 失配时，我们已经知道 T[i-j...i-1] 与 P[0...j-1] 匹配。我们需要找到模式串 P 下一次可能匹配的起始位置。如果将模式串向右移动 k 位，使得新的起始位置在 T[i-j+k]，那么新的比较点是 T[i] 对比 P[j-k]。为了不遗漏任何可能的匹配，新的模式串前缀 P[0...j-k-1] 必须与文本串中已经匹配的后缀 T[i-(j-k)...i-1] 相匹配。也就是说，P[0...j-k-1] 必须是 P[0...j-1] 的一个前缀，并且等于 P[0...j-1] 的一个后缀。为了最大化下次匹配的可能性，我们希望这个相等的长度 j-k 尽可能大。根据 next 数组的定义，next[j] 就是 P[0...j-1] 的最长相等真前缀和真后缀的长度。所以，将模式串移动 j - next[j] 位，可以使得 P[next[j]] 对齐 T[i]，并且保证 P[0...next[j]-1] 与 T[i-next[j]...i-1] 匹配。这种移动是最大的有效移动，保证不会跳过任何潜在的匹配起始位置。文本串指针 i 不回溯，是因为所有在 T[0...i-1] 范围内可能开始并延伸到 T[i] 的模式串匹配，都已经通过 next 数组的跳转检查过了。

时间复杂度：
1. next 数组构建：O(m)。如前所述，j 的总增长量最大为 m，总减少量不会超过总增长量。每次操作（比较或 j 赋值）都与 j 的变化相关，因此总时间是线性的。
2. 搜索阶段：O(n)。文本串指针 i 从 0 遍历到 n-1，最多移动 n 次。模式串指针 j 在匹配成功时增加，在失配时根据 next 数组减小（但不会小于 -1）。j 的总增长量最多为 n (因为每次成功匹配 T[i] 和 P[j]，j 增加，最多达到 m 然后重置，这个过程最多发生 n 次)。j 的总减少量不会超过总增加量。因此，文本串和模式串指针的总移动次数是 O(n + m)。由于 next 数组的计算已在 O(m) 完成，搜索本身的时间复杂度是 O(n + m)。在实际应用中，如果模式串远小于文本串，我们通常说搜索阶段是 O(n)。

总时间复杂度：O(m + n)
空间复杂度：O(m) 用于存储 next 数组。

相比于朴素匹配的 O(nm)，KMP 算法在最坏情况下也能保证线性时间复杂度，这是一个巨大的进步。

KMP 算法的优点与缺点

优点：
* 时间复杂度为 O(n + m)，在最坏情况下也比朴素匹配更高效。
* 搜索过程中文本串指针不回溯，适用于输入流是单向的情况。

缺点：
* 需要额外的空间存储 next 数组，空间复杂度为 O(m)。
* 算法理解和实现相比朴素匹配更复杂。
* 对于某些特定类型的模式串（例如，模式串字符都不同），其他线性时间算法（如 Boyer-Moore）在平均情况下的性能可能更好，尽管 Boyer-Moore 的最坏情况时间复杂度是 O(nm)（但在实际应用中很少达到）。

总结

KMP 算法是字符串匹配领域的一个里程碑式算法，它通过巧妙地利用模式串自身的结构信息（即部分匹配表 next 数组），在失配发生时避免了文本串指针的回溯，从而实现了线性的时间复杂度 O(n + m)。理解 KMP 算法的关键在于理解 next 数组的含义及其构建过程，以及如何在搜索过程中利用 next 数组进行模式串的高效滑动。虽然它在概念上比朴素匹配复杂，但其优秀的性能使其在需要高效字符串匹配的场景中有着重要的地位。彻底理解 KMP 算法，不仅仅是掌握一个特定的算法，更是学习一种利用已知信息优化搜索过程的通用思想，这在算法设计中是十分宝贵的。

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

滚动至顶部