KMP字符串匹配算法详解 – wiki基地

作者： /

KMP字符串匹配算法详解

引言：为什么需要更高效的字符串匹配算法？

在计算机科学中，字符串匹配是一个非常基础且重要的问题。它涉及到在一个较长的文本（Text）中查找一个较短的模式（Pattern）的所有出现位置。例如，在文本编辑器中搜索一个单词，在DNA序列中查找特定的基因片段，或者在网络数据包中匹配协议头部信息等。

最直观的字符串匹配算法是暴力（Naive）匹配算法。它的思路非常简单：将模式串与文本串从头开始逐个字符比较。如果发生不匹配，则将模式串向右移动一个位置，然后重新从模式串的第一个字符与文本串的当前位置开始比较。这个过程一直持续到模式串的末尾或者文本串的末尾。

举个例子：
文本 T = ABABCADABABCABAB
模式 P = ABABCABAB

  1. 第一次比较：
    T: ABABCADABABCABAB
    P: ABABCABAB
    ^ 匹配
    ^ 匹配
    ^ 匹配
    ^ 匹配
    ^ 匹配
    ^ ‘A’ != ‘D’，不匹配。
    模式串右移一位。

  2. 第二次比较：
    T: ABABCADABABCABAB
    P: ABABCABAB
    ^ ‘B’ != ‘A’，不匹配。
    模式串右移一位。

  3. 第三次比较：
    T: ABABCADABABCABAB
    P: ABABCABAB
    ^ ‘A’ != ‘A’，匹配。
    ^ ‘B’ != ‘B’，匹配。
    …
    继续比较…

暴力匹配算法在最好的情况下（例如模式串的第一个字符就不匹配）效率很高，但在最坏的情况下（例如文本串是AAAAA…，模式串是AAAAAB），它会进行大量的重复比较，导致效率低下。其时间复杂度是 O((n-m+1) * m)，其中 n 是文本串的长度，m 是模式串的长度。在 n 和 m 都很大的情况下，这个复杂度是不可接受的。

那么，是否存在一种更高效的算法，能够避免这种重复的比较，从而提高匹配速度呢？答案是肯定的，这就是 Knuth-Morris-Pratt (KMP) 算法。

KMP算法的核心思想

KMP算法的核心在于：当模式串与文本串发生不匹配时，它不会像暴力算法那样简单地将模式串向右移动一位，而是根据已经匹配的部分信息，计算出模式串下一次应该移动到哪个位置，从而跳过一些不可能匹配的位置，避免了文本指针的回溯。

举例来说，当我们在文本串 T 中查找模式串 P 时，如果在 T[i] 和 P[j] 处发生了不匹配（即 T[i] != P[j]），并且我们已经知道 P[0...j-1] 这部分是与 T[i-j...i-1] 匹配的：

T: ...... [T[i-j] ... T[i-1]] T[i] ......
P: ...... [P[0] ... P[j-1]] P[j] ......
<– 已匹配 –> <– 不匹配 –>

暴力算法会简单地将模式串右移一位，从 T[i-j+1] 开始重新与 P[0] 比较。但KMP算法注意到，T[i-j...i-1] 这段文本实际上就是 P[0...j-1]。如果我们将模式串右移后，新的模式串的开头 P[0] 想要与 T[k] 匹配，那么 P[0...l] 必然要与 T[k...k+l] 匹配。

KMP算法的关键在于，当 T[i] 与 P[j] 不匹配时，我们想找到一个最小的右移距离，使得移动后的模式串的某个前缀能够与 T[i-j...i-1] 的某个后缀对齐，并且这个前缀的下一个字符 P[k] (如果存在) 应该与 T[i] 重新进行比较。

为了实现这一点，KMP算法引入了一个重要的概念：最长公共前后缀。

部分匹配表 (Partial Match Table) 或称 Next 数组

KMP算法在匹配过程中，当发生不匹配时，需要知道模式串 P[0...j-1] 的哪一个真前缀（Proper Prefix，指不包括整个字符串本身的前缀）同时也是它的真后缀。并且，我们希望找到的是最长的这样的前后缀。

我们构建一个与模式串长度相等的数组，通常称为 next 数组（或 lps 数组，表示 Longest Proper Prefix which is also a Suffix）。next[j] 的值定义为：模式串 P 中前 j 个字符 P[0...j-1] 的最长的真前缀的长度，这个真前缀同时也是 P[0...j-1] 的真后缀。

例如，模式串 P = "ABABCABAB" (长度 m = 9)

  • P[0] (‘A’)：空字符串。最长公共前后缀长度为 0。next[0] = 0 (或根据定义，next[0] 表示空串的前缀/后缀，长度为0，有的实现会设为 -1 来简化匹配逻辑，这里我们先定义 next[j] 为 P[0...j-1] 的最长公共前后缀长度，所以 next[0] 表示空串，长度为 0)。
  • P[0...0] (“A”)：真前缀只有空串，真后缀只有空串。最长公共前后缀长度为 0。next[1] = 0。
  • P[0...1] (“AB”)：真前缀 [“A”], 真后缀 [“B”]。没有公共前后缀。长度为 0。next[2] = 0。
  • P[0...2] (“ABA”)：真前缀 [“A”, “AB”], 真后缀 [“A”, “BA”]。公共前后缀为 [“A”]。最长长度为 1。next[3] = 1。
  • P[0...3] (“ABAB”)：真前缀 [“A”, “AB”, “ABA”], 真后缀 [“B”, “AB”, “BAB”]。公共前后缀为 [“AB”]。最长长度为 2。next[4] = 2。
  • P[0...4] (“ABABC”)：真前缀 [“A”, “AB”, “ABA”, “ABAB”], 真后缀 [“C”, “BC”, “ABC”, “BABC”]。没有公共前后缀。长度为 0。next[5] = 0。
  • P[0...5] (“ABabca”)：真前缀 [“A”, “AB”, “ABA”, “ABAB”, “ABABC”], 真后缀 [“A”, “CA”, “BCA”, “ABCA”, “BABCA”]。公共前后缀为 [“A”]。最长长度为 1。next[6] = 1。
  • P[0...6] (“ABABCAD”)：真前缀 …, 真后缀 …。没有公共前后缀。长度为 0。next[7] = 0。
  • P[0...7] (“ABABCADA”)：真前缀 …, 真后缀 …。公共前后缀为 [“A”]。最长长度为 1。next[8] = 1。
  • P[0...8] (“ABABCADAB”)：真前缀 …, 真后缀 …。公共前后缀为 [“AB”]。最长长度为 2。next[9] = 2。

所以，对于 P = "ABABCADAB"，其 next 数组（按我们这里的定义，next[j] 表示 P[0...j-1] 的最长公共前后缀长度）：
j: 0 1 2 3 4 5 6 7 8 9
P: A B A B C A D A B
next[j]: 0 0 0 1 2 0 1 0 1 2

注意： next 数组的实际实现中，通常 next[0] 被定义为 -1 或 0，且 next[j] 的定义可能略有不同（例如表示 P[0...j] 的信息）。我们这里使用 next[j] 代表 P[0...j-1] 的信息，并将 next[0] 设为 0，这是一种常见的定义方式。在实际编程中，通常会调整索引，比如让 next[i] 表示模式串中第 i 个字符失配后，下次应该从模式串的 next[i] 位置开始比较。如果采用 next[j] 表示 P[0...j-1] 的信息，当 P[j] 失配时，下一次应该将 P[next[j]] 与当前的文本字符对齐。为了简化边界情况处理（特别是当 j=0 失配时），很多实现会将 next[0] 定义为 -1。我们将在匹配算法中演示这种定义。

如果采用 next[j] 表示当 P[j] 发生失配时，模式串指针应该回溯到的位置，并且 next[0] = -1，则 next 数组的计算方式如下：

定义 next[j] 为当 P[j] 与文本字符不匹配时，模式串的下一个比较位置。
* 如果 P[0...j-1] 的最长公共前后缀长度为 k (即 P[0...k-1] == P[j-k...j-1])，那么当 P[j] 失配时，我们可以将模式串移动到使得 P[k] 与当前文本字符对齐的位置。此时模式串的指针应该移动到 k。所以 next[j] = k。

我们重新计算 P = "ABABCADAB" 的 next 数组，采用 next[j] 表示当 P[j] 失配时模式串指针应回溯到的位置，且 next[0] = -1。

  1. j=0: P[0] (‘A’) 失配。没有前缀，回溯到开始之前的位置。next[0] = -1。
  2. j=1: P[0] (‘A’) 匹配后，P[1] (‘B’) 失配。P[0...0] 是 “A”。没有非空真前缀是其真后缀。回溯到 P[0] 的位置。next[1] = 0。
  3. j=2: P[0...1] (“AB”) 匹配后，P[2] (‘A’) 失配。P[0...1] 的最长公共前后缀长度为 0。回溯到 P[0] 的位置。next[2] = 0。
  4. j=3: P[0...2] (“ABA”) 匹配后，P[3] (‘B’) 失配。P[0...2] 的最长公共前后缀是 “A”，长度为 1。这意味着 P[0] == P[2] (‘A’ == ‘A’)。当 P[3] 失配时，我们知道 T[i-3] 是 ‘A’ (因为它匹配了 P[0])。此时可以将模式串移动到使得 P[1] (‘B’) 与 T[i-2] 对齐，而 P[0] (‘A’) 与 T[i-3] 对齐。由于 P[0] == T[i-3] 已经知道，我们只需要从 P[1] 开始与 T[i-2] 重新比较。所以模式串指针回溯到 P[1] 的位置。next[3] = 1。
  5. j=4: P[0...3] (“ABAB”) 匹配后，P[4] (‘C’) 失配。P[0...3] 的最长公共前后缀是 “AB”，长度为 2。这意味着 P[0...1] == P[2...3] (“AB” == “AB”)。当 P[4] 失配时，我们知道 T[i-4...i-3] 是 “AB” (因为它匹配了 P[0...1])。此时可以将模式串移动到使得 P[2] (‘A’) 与 T[i-2] 对齐，而 P[0...1] (“AB”) 与 T[i-4...i-3] 对齐。由于 P[0...1] == T[i-4...i-3] 已经知道，且 P[0...1] == P[2...3]，所以 P[2...3] 也与 T[i-4...i-3] 匹配。我们只需要从 P[2] 开始与 T[i-2] 重新比较。所以模式串指针回溯到 P[2] 的位置。next[4] = 2。
  6. j=5: P[0...4] (“ABABC”) 匹配后，P[5] (‘A’) 失配。P[0...4] 的最长公共前后缀长度为 0。回溯到 P[0] 的位置。next[5] = 0。
  7. j=6: P[0...5] (“ABabca”) 匹配后，P[6] (‘D’) 失配。P[0...5] 的最长公共前后缀是 “A”，长度为 1。回溯到 P[1] 的位置。next[6] = 1。
  8. j=7: P[0...6] (“ABABCAD”) 匹配后，P[7] (‘A’) 失配。P[0...6] 的最长公共前后缀长度为 0。回溯到 P[0] 的位置. next[7] = 0。
  9. j=8: P[0...7] (“ABABCADA”) 匹配后，P[8] (‘B’) 失配。P[0...7] 的最长公共前后缀是 “A”，长度为 1。回溯到 P[1] 的位置。next[8] = 1。
  10. j=9: P[0...8] (“ABABCADAB”) 匹配后，模式串已经完全匹配。但为了 next 数组的完整性（有时 next 数组长度是 m+1），或者用于匹配后的模式串滑动，我们可以计算 next[9]。P[0...8] 的最长公共前后缀是 “AB”，长度为 2。next[9] = 2。

所以，采用 next[j] 表示失配后模式串指针应回溯到的位置，且 next[0] = -1，对于 P = "ABABCADAB"，其 next 数组为：
j: 0 1 2 3 4 5 6 7 8 9
P: A B A B C A D A B
next[j]: -1 0 0 1 2 0 1 0 1 2

这个 next 数组的计算本身是一个类似于 KMP 匹配的过程，其时间复杂度是 O(m)。

计算 Next 数组的算法

我们使用两个指针，i 和 j。j 用于遍历模式串，计算 next[j]，相当于模式串的后缀。i 用于表示当前比较的真前缀的下一个字符位置，相当于模式串的前缀。

初始化 next 数组，next[0] = -1。
设置两个指针 i = -1, j = 0。
当 j < m 时循环：
* 如果 i == -1 或 P[j] == P[i]：
* 说明当前字符 P[j] 与前缀的下一个字符 P[i] 匹配成功。
* 即将计算的是 next[j+1] 的值，它是基于 P[0...j] 的信息。
* 此时 P[0...i] 的最长公共前后缀长度增加 1，变为 i+1。
* 所以 next[j+1] = i + 1。
* 指针同时向前移动：i++, j++。
* 如果 P[j] != P[i]：
* 说明当前字符 P[j] 与前缀的下一个字符 P[i] 不匹配。
* 我们需要寻找 P[0...i-1] 的更短的公共前后缀。根据 next 数组的定义，这个更短的前缀的下一个字符位置是 next[i]。
* 所以我们将 i 回溯到 next[i] 的位置，继续比较 P[j] 和 P[next[i]]。i = next[i]。
* 注意，这里 j 不变，因为我们还在尝试为 next[j+1] 找到合适的值。

这是一个计算 next 数组 (长度 m) 的伪代码：

“`
next[0] = -1
i = -1
j = 0
m = length(P)

while (j < m – 1): // 注意这里循环到 m-1，计算 next[1] 到 next[m-1]
if (i == -1 or P[j] == P[i]):
i++
j++
next[j] = i // next[j]存储的是P[0…j-1]的最长公共前后缀长度+1，即失配后P[j]应回溯到的位置
else:
i = next[i] // i 回溯

// 最终 next 数组长度为 m，next[0]到next[m-1]
如果我们希望 `next` 数组长度为 m+1，且 `next[j]` 表示 `P[0...j]` 的信息，并且 `next[0]=-1`：
next[0] = -1
i = -1 // i 表示当前已经匹配的前缀/后缀的长度
j = 0 // j 遍历模式串 P

while (j < m):
if (i == -1 or P[j] == P[i]):
i++
j++
// 考虑优化：如果P[j] == P[i]，那么在P[j]失配时，回溯到i位置，P[i]仍然会与文本中的P[j]对应的字符比较，如果P[i]和P[j]相等，这次比较必定再次失配。
// 因此可以直接跳过P[i]的比较，回溯到next[i]的位置。
// next[j] = i; // 原始定义
if (j < m && P[j] == P[i]): // 只有当j+1在模式串范围内且P[j+1]等于P[i+1]时才进行优化
next[j] = next[i]; // 优化后的next数组
else:
next[j] = i; // 未优化或无法优化的部分
else:
i = next[i]; // i 回溯
``
上面是两种next数组的计算方式，它们的定义和用法在匹配阶段略有不同。第一种计算方法next[j]表示P[0…j-1]的信息，用于当P[j]失配时，回溯到P[next[j]]位置重新比较。第二种是优化后的next数组，直接跳过与失配字符相同的前缀字符。这里我们采用第一种相对直观的定义：next[j]是当P[j]` 失配时，模式串指针应该回溯到的位置。

示例：计算 P=”abababca” 的 next 数组 (m=8)
next[0] = -1
i = -1, j = 0

  1. j=0: i=-1. i++, j++. next[1] = i = 0. (i=0, j=1)
  2. j=1: P[1]('b') != P[i]('a'). i = next[i] = next[0] = -1. (i=-1, j=1)
  3. j=1: i=-1. i++, j++. next[2] = i = 0. (i=0, j=2)
  4. j=2: P[2]('a') == P[i]('a'). i++, j++. next[3] = i = 1. (i=1, j=3)
  5. j=3: P[3]('b') == P[i]('b'). i++, j++. next[4] = i = 2. (i=2, j=4)
  6. j=4: P[4]('c') != P[i]('a'). i = next[i] = next[2] = 0. (i=0, j=4)
  7. j=4: P[4]('c') != P[i]('a'). i = next[i] = next[0] = -1. (i=-1, j=4)
  8. j=4: i=-1. i++, j++. next[5] = i = 0. (i=0, j=5)
  9. j=5: P[5]('a') == P[i]('a'). i++, j++. next[6] = i = 1. (i=1, j=6)
  10. j=6: P[6]('b') == P[i]('b'). i++, j++. next[7] = i = 2. (i=2, j=7)
  11. j=7: P[7]('c') != P[i]('a'). i = next[i] = next[2] = 0. (i=0, j=7)
  12. j=7: P[7]('c') != P[i]('a'). i = next[i] = next[0] = -1. (i=-1, j=7)
  13. j=7: i=-1. i++, j++. next[8] = i = 0. (i=0, j=8)

结束循环，因为 j 达到 m-1 (即 7) 并计算了 next[8]。

最终 next 数组 (长度为 m=8):
j: 0 1 2 3 4 5 6 7
P: a b a b c a b c
next[j+1]:-1 0 0 1 2 0 1 2 0 (这里 next[j+1] 表示 P[j] 失配后应回溯到的位置)

如果 next 数组定义为 next[j] 表示 P[0...j-1] 的最长公共前后缀长度，且 next[0]=0，则：
j: 0 1 2 3 4 5 6 7 8
P: a b a b c a b c
next[j]: 0 0 0 1 2 0 1 2 0

我们统一采用 next[j] 表示 P[0...j-1] 的最长公共前后缀长度，next[0]=0。当 P[j] 失配时，模式串指针 j 回溯到 next[j]。

重新计算 P="abababca" (m=8) 的 next 数组（next[j] 表示 P[0...j-1] 的最长公共前后缀长度，next[0]=0）：
next[0] = 0
使用指针 i (已匹配前缀的下一位) 和 j (当前计算 next 的位置，即 P[0...j-1])
初始化 i = 0 (表示空串的下一位), j = 1 (从计算 next[1] 开始)

  1. j=1: P[1-1]('a') vs P[i]('a')? i=0, P[0] 是 ‘a’. P[0] == P[0]. 匹配。
    next[1] = i = 0.
    i++ (i=1), j++ (j=2).
  2. j=2: P[2-1]('b') vs P[i]('a')? i=1, P[1] 是 ‘b’. P[1] != P[1-1]. 不匹配。
    i 回溯到 next[i] = next[1] = 0. (i=0).
    j 不变.
  3. j=2: P[2-1]('b') vs P[i]('a')? i=0, P[0] 是 ‘a’. P[1] != P[0]. 不匹配。
    i 回溯到 next[i] = next[0] = 0. (i=0).
    j 不变. (此时 i 已经到 0，无法继续回溯)
    next[2] = i = 0.
    j++ (j=3).
  4. j=3: P[3-1]('a') vs P[i]('a')? i=0, P[0] 是 ‘a’. P[2] == P[0]. 匹配。
    next[3] = i+1 = 1.
    i++ (i=1), j++ (j=4).
  5. j=4: P[4-1]('b') vs P[i]('b')? i=1, P[1] 是 ‘b’. P[3] == P[1]. 匹配。
    next[4] = i+1 = 2.
    i++ (i=2), j++ (j=5).
  6. j=5: P[5-1]('c') vs P[i]('a')? i=2, P[2] 是 ‘a’. P[4] != P[2]. 不匹配。
    i 回溯到 next[i] = next[2] = 0. (i=0).
    j 不变.
  7. j=5: P[5-1]('c') vs P[i]('a')? i=0, P[0] 是 ‘a’. P[4] != P[0]. 不匹配。
    i 回溯到 next[i] = next[0] = 0. (i=0).
    j 不变. (此时 i 已经到 0，无法继续回溯)
    next[5] = i = 0.
    j++ (j=6).
  8. j=6: P[6-1]('a') vs P[i]('a')? i=0, P[0] 是 ‘a’. P[5] == P[0]. 匹配。
    next[6] = i+1 = 1.
    i++ (i=1), j++ (j=7).
  9. j=7: P[7-1]('b') vs P[i]('b')? i=1, P[1] 是 ‘b’. P[6] == P[1]. 匹配。
    next[7] = i+1 = 2.
    i++ (i=2), j++ (j=8).
  10. j=8: P[8-1]('c') vs P[i]('a')? i=2, P[2] 是 ‘a’. P[7] != P[2]. 不匹配。
    i 回溯到 next[i] = next[2] = 0. (i=0).
    j 不变.
  11. j=8: P[8-1]('c') vs P[i]('a')? i=0, P[0] 是 ‘a’. P[7] != P[0]. 不匹配。
    i 回溯到 next[i] = next[0] = 0. (i=0).
    j 不变. (此时 i 已经到 0，无法继续回溯)
    next[8] = i = 0.
    j++ (j=9).

循环结束，因为 j 达到 m=8.
最终 next 数组 (长度 m=8, next[j] 表示 P[0...j-1] 的最长公共前后缀长度):
j: 0 1 2 3 4 5 6 7
P: a b a b c a b c
next[j]: 0 0 0 1 2 0 1 2

这个 next 数组表示：
* 当 P[0] 失配，下一位置是 P[next[1]=0]。
* 当 P[1] 失配，下一位置是 P[next[2]=0]。
* 当 P[2] 失配，下一位置是 P[next[3]=1]。
* 当 P[3] 失配，下一位置是 P[next[4]=2]。
* 当 P[4] 失配，下一位置是 P[next[5]=0]。
* 当 P[5] 失配，下一位置是 P[next[6]=1]。
* 当 P[6] 失配，下一位置是 P[next[7]=2]。
* 当 P[7] 失配，下一位置是 P[next[8]=0]。

KMP 匹配算法流程

有了 next 数组，KMP 匹配过程就相对简单了。我们使用两个指针：i 指向文本串 T 的当前字符，j 指向模式串 P 的当前字符。

初始化 i = 0, j = 0.

主循环：当 i < n (文本串未结束) 且 j < m (模式串未结束) 时循环：
* 如果 j == 0 或者 T[i] == P[j]：
* 表示当前字符匹配成功，或者 j 已经回溯到模式串开头 (j==0) 需要从文本的下一个字符开始比较。
* 将两个指针同时向前移动：i++, j++.
* 如果 T[i] != P[j]：
* 表示当前字符不匹配。
* 根据 next 数组，模式串指针 j 回溯到 next[j] 的位置：j = next[j].
* 重要： 文本指针 i 不回溯。这是 KMP 效率高的关键。因为 P[0...j-1] 已经与 T[i-j...i-1] 匹配过，而根据 next[j] 的定义，P[0...next[j]-1] 是 P[0...j-1] 的最长公共前后缀，它也与 P[j-next[j]...j-1] 相等。因此，P[0...next[j]-1] 也与 T[i-j...i-1] 的后缀 T[i-next[j]...i-1] 相等。当我们将模式串移动到 P[next[j]] 与 T[i] 对齐的位置时，模式串的 P[0...next[j]-1] 部分实际上已经与文本串中对应的部分（即 T[i-next[j]...i-1]）匹配过了，无需重新比较。我们只需要从 P[next[j]] 开始与 T[i] 重新比较即可。

匹配成功：
* 如果在循环中，j 达到了模式串的长度 m (j == m)，说明找到了一个匹配项，起始位置在文本串的 i - m 处。
* 找到匹配后，如果需要查找所有匹配项，不能停止。模式串需要继续向右滑动，查找下一个可能的匹配。滑动多少呢？根据 next 数组，我们将模式串指针 j 回溯到 next[m] (j = next[m])，继续从文本串的当前位置 i 开始比较。

伪代码 (假设 next 数组长度为 m, next[0]=0, 且 next[j] 表示 P[0…j-1] 的最长公共前后缀长度):

“`
// 假设已经计算好模式串 P 的 next 数组

n = length(T)
m = length(P)
i = 0 // 文本串指针
j = 0 // 模式串指针

// next 数组计算方法 (这里简化，实际需要上面的循环计算)
// next = compute_next(P)

while (i < n):
// 如果当前字符匹配，或者模式串指针已经在开头 (j==0)
if (j == 0 and T[i] != P[j]): // 特殊处理j=0失配的情况，只移动文本指针
i++
elif (T[i] == P[j]): // 匹配成功
i++
j++
else: // T[i] != P[j] 且 j > 0，失配
// 模式串指针回溯到 next[j] 指定的位置
j = next[j]

// 如果模式串指针到达末尾，说明找到一个匹配
if (j == m):
    // 找到匹配，起始位置为 i - m
    print("Pattern found at index", i - m)

    // 继续寻找下一个匹配，模式串根据 next[m] 回溯
    j = next[m] // 或者 j = next[j] (因为此时 j==m)
    // 文本指针 i 不变

``
上面伪代码中的j==0 and T[i] != P[j]特殊处理分支是可以合并到 else 分支的，只要next[0]设置得当。如果next数组采用next[0] = -1的定义，且next[j]表示P[j]` 失配后模式串指针应回溯到的位置：

“`
// 假设已经计算好模式串 P 的 next 数组 (长度 m, next[0]=-1)
// next = compute_next_with_neg1(P)

n = length(T)
m = length(P)
i = 0 // 文本串指针
j = 0 // 模式串指针

while (i < n):
// 如果当前字符匹配，或者模式串指针已经回溯到 -1 (表示P[0]失配，需要移动文本指针)
if (j == -1 or T[i] == P[j]):
i++
j++
else: // T[i] != P[j] 且 j > -1，失配
// 模式串指针回溯
j = next[j]

// 如果模式串指针到达末尾，说明找到一个匹配
if (j == m):
    // 找到匹配，起始位置为 i - m
    print("Pattern found at index", i - m)

    // 继续寻找下一个匹配，模式串根据 next[m] 回溯
    j = next[m] // 注意这里的 next[m] 是需要计算的，如果 next 数组只计算到 m-1，需要特殊处理或补全 next[m]
    // 文本指针 i 不变

``
这种next[0] = -1的定义更加简洁，因为它将j=0失配的情况 (T[i] != P[0]) 统一处理了：当j=0且失配时，j = next[0] = -1。下一次循环进入j == -1分支，i++,j++`，效果就是文本指针前进一位，模式串指针回到 0，这正是我们期望的。

我们采用 next[0] = -1 的版本来走一遍匹配示例。

文本 T = ABABCADABABCABAB (n=16)
模式 P = ABABCABAB (m=9)
next 数组 (m=9, next[0]=-1): [-1, 0, 0, 1, 2, 0, 1, 0, 1, 2] (这里 next 数组长度为 m，索引 0 到 m-1, next[j] 表示 P[j] 失配后回溯到的位置，且 next[0] 设为 -1 辅助处理。当 j 回溯到 -1 后，下次比较 T[i] 和 P[0]。)
为了匹配后的滑动，我们需要 next[m] 的值。根据 next 数组计算方法，next[9] 表示 P[0…8] 的最长公共前后缀长度。P[0…8] = “ABABCADAB”，最长公共前后缀是 “AB”，长度为 2。所以 next[9]=2。完整的 next 数组长度 m+1: [-1, 0, 0, 1, 2, 0, 1, 0, 1, 2] (索引 0 到 9)。

初始化 i = 0, j = 0.

  1. i=0, j=0: T[0]=='A', P[0]=='A'. 匹配. i=1, j=1.
  2. i=1, j=1: T[1]=='B', P[1]=='B'. 匹配. i=2, j=2.
  3. i=2, j=2: T[2]=='A', P[2]=='A'. 匹配. i=3, j=3.
  4. i=3, j=3: T[3]=='B', P[3]=='B'. 匹配. i=4, j=4.
  5. i=4, j=4: T[4]=='C', P[4]=='C'. 匹配. i=5, j=5.
  6. i=5, j=5: T[5]=='A', P[5]=='A'. 匹配. i=6, j=6.
  7. i=6, j=6: T[6]=='D', P[6]=='D'. 匹配. i=7, j=7.
  8. i=7, j=7: T[7]=='A', P[7]=='A'. 匹配. i=8, j=8.
  9. i=8, j=8: T[8]=='B', P[8]=='B'. 匹配. i=9, j=9.

  10. j == m (9). 找到匹配！位置 i-m = 9-9 = 0.
    模式串回溯 j = next[m] = next[9] = 2. i 保持 9.

  11. i=9, j=2: T[9]=='A', P[2]=='A'. 匹配. i=10, j=3.

  12. i=10, j=3: T[10]=='B', P[3]=='B'. 匹配. i=11, j=4.

  13. i=11, j=4: T[11]=='A', P[4]=='C'. 不匹配. j > -1.
    j = next[j] = next[4] = 2. i 保持 11.

  14. i=11, j=2: T[11]=='A', P[2]=='A'. 匹配. i=12, j=3.

  15. i=12, j=3: T[12]=='B', P[3]=='B'. 匹配. i=13, j=4.

  16. i=13, j=4: T[13]=='A', P[4]=='C'. 不匹配. j > -1.
    j = next[j] = next[4] = 2. i 保持 13.

  17. i=13, j=2: T[13]=='A', P[2]=='A'. 匹配. i=14, j=3.

  18. i=14, j=3: T[14]=='B', P[3]=='B'. 匹配. i=15, j=4.

  19. i=15, j=4: T[15]=='B', P[4]=='C'. 不匹配. j > -1.
    j = next[j] = next[4] = 2. i 保持 15.

  20. i=15, j=2: T[15]=='B', P[2]=='A'. 不匹配. j > -1.
    j = next[j] = next[2] = 0. i 保持 15.

  21. i=15, j=0: T[15]=='B', P[0]=='A'. 不匹配. j > -1.
    j = next[j] = next[0] = -1. i 保持 15.

  22. i=15, j=-1: j == -1. i++, j++. i=16, j=0.

  23. i=16. 循环条件 i < n (16 < 16) 不满足。主循环结束。

找到了一个匹配在索引 0 处。上面的示例文本和模式串可能不是最优演示KMP效率的例子。换一个：

文本 T = ABABDABACDABABCABAB (n=19)
模式 P = ABABCABAB (m=9)
next 数组: [-1, 0, 0, 1, 2, 0, 1, 0, 1, 2] (长度 m+1)

初始化 i = 0, j = 0.

  1. i=0, j=0: T[0]=='A', P[0]=='A'. 匹配. i=1, j=1.
  2. i=1, j=1: T[1]=='B', P[1]=='B'. 匹配. i=2, j=2.
  3. i=2, j=2: T[2]=='A', P[2]=='A'. 匹配. i=3, j=3.
  4. i=3, j=3: T[3]=='B', P[3]=='B'. 匹配. i=4, j=4.

  5. i=4, j=4: T[4]=='D', P[4]=='C'. 不匹配. j > -1.
    j = next[j] = next[4] = 2. i 保持 4.

  6. i=4, j=2: T[4]=='D', P[2]=='A'. 不匹配. j > -1.
    j = next[j] = next[2] = 0. i 保持 4.

  7. i=4, j=0: T[4]=='D', P[0]=='A'. 不匹配. j > -1.
    j = next[j] = next[0] = -1. i 保持 4.

  8. i=4, j=-1: j == -1. i++, j++. i=5, j=0.

  9. i=5, j=0: T[5]=='A', P[0]=='A'. 匹配. i=6, j=1.

  10. i=6, j=1: T[6]=='B', P[1]=='B'. 匹配. i=7, j=2.
  11. i=7, j=2: T[7]=='A', P[2]=='A'. 匹配. i=8, j=3.

  12. i=8, j=3: T[8]=='C', P[3]=='B'. 不匹配. j > -1.
    j = next[j] = next[3] = 1. i 保持 8.

  13. i=8, j=1: T[8]=='C', P[1]=='B'. 不匹配. j > -1.
    j = next[j] = next[1] = 0. i 保持 8.

  14. i=8, j=0: T[8]=='C', P[0]=='A'. 不匹配. j > -1.
    j = next[j] = next[0] = -1. i 保持 8.

  15. i=8, j=-1: j == -1. i++, j++. i=9, j=0.

  16. i=9, j=0: T[9]=='D', P[0]=='A'. 不匹配. j > -1.
    j = next[j] = next[0] = -1. i 保持 9.

  17. i=9, j=-1: j == -1. i++, j++. i=10, j=0.

  18. i=10, j=0: T[10]=='A', P[0]=='A'. 匹配. i=11, j=1.
    … (继续匹配，直到 i=19, j=9)

  19. i=19, j=9: j == m (9). 找到匹配！位置 i-m = 19-9 = 10.
    模式串回溯 j = next[m] = next[9] = 2. i 保持 19.

  20. i=19. 循环条件 i < n (19 < 19) 不满足。主循环结束。

找到了一个匹配在索引 10 处。可以看到，在多次不匹配时，文本指针 i 都没有回溯，模式串指针 j 根据 next 数组跳跃式地回溯，这就是 KMP 高效的原因。

KMP 算法的复杂度分析

  1. 预处理 (计算 next 数组)：
    计算 next 数组的过程使用了两个指针 i 和 j。指针 j 从 0 走到 m-1 (或 m)。指针 i 的移动是关键。在 P[j] == P[i] 匹配时，i 增加；在 P[j] != P[i] 不匹配时，i 回溯到 next[i]。每一次 i 的回溯都会使其值减小（除非回溯到 -1），而 i 的最大值不会超过 j (或 m-1)。考虑到 j 总是向前移动，而 i 的向前移动次数 (i++) 不会超过 m 次（因为 i 不会超过 m），i 的回溯次数最多与向前移动次数相当。因此，计算 next 数组的时间复杂度是 O(m)。空间复杂度是 O(m) 用于存储 next 数组。

  2. 匹配过程：
    匹配过程使用了两个指针 i 和 j。指针 i 从 0 走到 n-1。指针 j 从 0 走到 m。

    • 当 T[i] == P[j] 或 j == -1 时，i 增加 1。文本指针 i 总共移动 n 次。
    • 当 T[i] != P[j] 且 j > -1 时，j 回溯到 next[j]。模式串指针 j 的回溯次数。j 的最大值是 m。每次回溯后，j 的值是小于当前的 j 值的（除非 j=0 回溯到 -1）。j 的向前移动的总次数不会超过文本长度 n 加上匹配成功的 m 次（因为找到匹配后 j 会达到 m）。j 的总的回溯次数不会超过其总的向前移动次数。因此，模式串指针 j 的总移动次数（向前和向后）是 O(n + m)。
    • 每次循环至少 i 或 j 中的一个前进。

    总的来说，文本指针 i 最多向前移动 n 步。模式串指针 j 在文本指针 i 的每次移动中，要么随着 i 向前移动，要么回溯，但总的移动次数是有限的。因此，匹配过程的时间复杂度是 O(n)。

  3. 总时间复杂度： O(m) (预处理) + O(n) (匹配) = O(n + m)。
    这相比于暴力匹配的 O(nm) 是一个显著的提升，尤其是在 n 和 m 都很大且模式串具有重复结构的情况下。

KMP 算法的空间复杂度是 O(m)，用于存储 next 数组。

KMP 的优势与应用

优势：
1. 高效性： 时间复杂度为 O(n + m)，远优于暴力匹配的 O(nm)。
2. 文本指针不回溯： KMP 算法在匹配过程中，文本指针 i 只会单向向前移动，从不回溯。这使得 KMP 算法特别适合在无法回溯文本串的情况下使用，例如在网络流或文件流中进行模式匹配，只需要顺序读取文本数据即可。

应用：
* 文本编辑器中的查找/替换功能。
* 搜索引擎中的文本匹配。
* 生物信息学中的 DNA/蛋白质序列匹配。
* 网络入侵检测系统中的数据包头部匹配。
* 编译器和解释器中的词法分析。

总结

KMP 字符串匹配算法是一个经典且高效的算法。它通过预先计算模式串自身的特点（构建 next 数组），在匹配过程中利用这些信息，避免了不必要的重复比较，从而达到了线性的时间复杂度。虽然理解和实现起来比暴力匹配稍复杂，但其在处理大规模字符串匹配问题时的性能优势是不可替代的。理解 KMP 算法的关键在于理解 next 数组的意义以及如何在失配时利用 next 数组进行模式串的滑动。

希望本文能够帮助您详细理解 KMP 算法的原理和流程。

发表评论

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

滚动至顶部