字符串匹配算法：KMP入门 – wiki基地

作者： /

字符串匹配算法：KMP入门详解

引言：大海捞针的挑战

在计算机科学中，字符串匹配是一个非常基础且重要的课题。它指的是在一个较长的文本串（通常称为主串或目标串 T）中查找一个较短的模式串（通常称为模式串 P）的所有出现位置。

这个任务在我们日常生活中无处不在：
* 文本编辑器中的“查找”功能 (Ctrl+F)。
* 搜索引擎在网页内容中查找关键词。
* 生物信息学中查找DNA或蛋白质序列中的特定模式。
* 网络安全中的入侵检测，查找恶意代码签名。

想象一下，主串 T 是浩瀚的大海，模式串 P 是一根针。字符串匹配就是要在大海中找到这根针的所有位置。

最直观的字符串匹配方法是暴力匹配（或称朴素匹配）。它很简单：将模式串的开头与主串的开头对齐，然后逐个字符比较。如果遇到不匹配的字符，就将模式串向右移动一个位置，重新从模式串的开头与主串的新位置对齐，再次进行逐个字符比较，直到模式串与主串的某个部分完全匹配，或者主串遍历完毕。

暴力匹配示例：

假设主串 T = "ABCA BCABC"，模式串 P = "ABC"。

  1. 第一次对齐:
    T: A B C A B C A B C
    P: A B C
    比较 T[0] 和 P[0] (A vs A) – 匹配
    比较 T[1] 和 P[1] (B vs B) – 匹配
    比较 T[2] 和 P[2] (C vs C) – 匹配
    模式串 P 完全匹配！在 T 的索引 0 处找到一个匹配。

  2. 第二次对齐: (将模式串向右移动一个位置)
    T: A B C A B C A B C
    P: A B C
    比较 T[1] 和 P[0] (B vs A) – 不匹配。

  3. 第三次对齐: (将模式串向右移动一个位置)
    T: A B C A B C A B C
    P: A B C
    比较 T[2] 和 P[0] (C vs A) – 不匹配。

  4. 第四次对齐: (将模式串向右移动一个位置)
    T: A B C A B C A B C
    P: A B C
    比较 T[3] 和 P[0] (A vs A) – 匹配
    比较 T[4] 和 P[1] (B vs B) – 匹配
    比较 T[5] 和 P[2] (C vs C) – 匹配
    模式串 P 完全匹配！在 T 的索引 3 处找到一个匹配。

…以此类推，直到主串结束。

暴力匹配的问题：

虽然暴力匹配简单易懂，但在某些情况下效率极低。考虑这样一个例子：
主串 T = "AAAAAAA...AAAAAB" (100个A，最后1个B)
模式串 P = "AAAAAB" (5个A，最后1个B)

暴力匹配过程会是这样：
* 第一次对齐：P 对齐 T[0...5]。比较 T[0] 到 T[4] 都匹配 P[0] 到 P[4]。在 T[5] (A) 和 P[5] (B) 处不匹配。模式串向右移动1位。
* 第二次对齐：P 对齐 T[1...6]。比较 T[1] 到 T[5] 都匹配 P[0] 到 P[4]。在 T[6] (A) 和 P[5] (B) 处不匹配。模式串向右移动1位。
* …
* 第九十五次对齐：P 对齐 T[94...99]。比较 T[94] 到 T[98] 都匹配 P[0] 到 P[4]。在 T[99] (A) 和 P[5] (B) 处不匹配。模式串向右移动1位。
* 第九十六次对齐：P 对齐 T[95...100]。T[95...99] (AAAAA) 匹配 P[0...4] (AAAAA)。T[100] (B) 匹配 P[5] (B)。完全匹配。

在这个例子中，模式串长度为 m，主串长度为 n。在大多数对齐中，我们都需要比较 m 个字符（或 m-1 个字符）才能发现不匹配，然后模式串只向右移动 1 个位置。这种情况下，总的比较次数接近 O(m * n)。当 m 和 n 都很大时，这将非常慢。

KMP 算法正是为了解决暴力匹配的低效率问题而诞生的。它的核心思想是：在匹配过程中，当发生不匹配时，我们不回溯主串的指针，而是利用已经匹配的部分信息，巧妙地移动模式串的指针，从而避免了大量的重复比较。

KMP 算法的诞生与核心思想

KMP 算法由 Knuth、Morris 和 Pratt 三位学者同时独立提出，因此得名 KMP。

KMP 算法之所以高效，关键在于它避免了在发生不匹配时主串指针的回溯。当 P[j] 与 T[i] 发生不匹配时，我们知道 P[0...j-1] 这一段已经与 T[i-j...i-1] 匹配成功了。KMP 算法利用了 P[0...j-1] 这一段模式串本身的特性来决定模式串应该向右移动多少距离，以便能够继续匹配。

核心洞察： 当 P[j] 与 T[i] 不匹配时，我们知道主串中 T[i-j...i-1] 这段子串等于模式串的 P[0...j-1] 这段前缀。为了继续查找可能的匹配，我们需要将模式串向右移动。新的对齐位置应该使得模式串的某个前缀恰好与主串中 T[i-j...i-1] 的某个后缀对齐，并且这个前缀应该尽可能长，这样我们可以利用之前已经匹配的信息，从新的对齐位置开始比较。

例如，如果在匹配 T[i] 和 P[j] 时发现不匹配，并且 P[0...j-1] 已经匹配成功：
T: ... X X X X T[i] ...
P: ... P[j-1] P[j] ... (P[0…j-1] 匹配 T[i-j…i-1])

如果我们将模式串向右移动，新的模式串开头应该对齐主串的某个位置 i'。这意味着 P[0] 应该对齐 T[i']。并且为了利用之前的匹配信息，我们希望 P[0...k] （模式串的一个前缀）能够对齐 T[i-k...i-1] （主串已匹配部分的后缀），其中 T[i-k...i-1] 等于 P[j-k...j-1]。也就是说，我们希望找到一个最长的 k < j，使得 P[0...k-1] 等于 P[j-k...j-1]。

这正是 KMP 算法中一个关键预处理步骤所计算的信息：“部分匹配表”，也称为 “前缀函数” 或 next 数组。

部分匹配表 (前缀函数 π 或 next 数组)

部分匹配表记录了模式串本身的特征，具体来说，对于模式串 P 中的每一个位置 q，π[q] 的值表示：模式串 P 的前缀 P[0...q] 中，最长的既是真前缀又是真后缀的子串的长度。

这里的“真前缀”是指不包含最后一个字符的前缀，而“真后缀”是指不包含第一个字符的后缀。例如，字符串 “ABABC” 的真前缀有 “A”, “AB”, “ABA”, “ABAB”，真后缀有 “B”, “BC”, “ABC”, “BABC”。对于 “ABABC”，最长的既是真前缀又是真后缀的子串是 “AB”，长度为 2。所以对于索引 4 (即字符 ‘C’)，π[4] = 2。

π[q] 的含义是：如果 P[q] 与主串中的字符失配，并且 P[0...q-1] 已经匹配成功，那么我们可以知道主串的当前位置之前的 q 个字符（即 T[i-q...i-1]）与 P[0...q-1] 是完全相同的。我们现在需要寻找一个新的对齐方式，使得模式串的某个前缀能够与 T[i-q...i-1] 的某个后缀对齐。根据 π[q-1] 的定义（注意这里是 q-1，因为失配发生在 P[q]，意味着 P[0...q-1] 匹配成功），π[q-1] 就是 P[0...q-1] 这个字符串中，最长的既是真前缀又是真后缀的子串的长度。这段长度为 π[q-1] 的子串，既是 P[0...π[q-1]-1]，也是 P[q-π[q-1]...q-1]。因为它也是 P[0...q-1] 的后缀，所以它一定等于 T[i-q...i-1] 的对应后缀 T[i-π[q-1]...i-1]。

这意味着，我们可以将模式串移动到新的位置，使得 P[0...π[q-1]-1] 与 T[i-π[q-1]...i-1] 对齐。新的模式串需要比较的字符将是 P[π[q-1]] 与 T[i]。如果它们匹配，我们继续比较 P[π[q-1]+1] 与 T[i+1]；如果不匹配，我们根据 π 表继续进行回溯（在模式串内部）。

所以，当 P[j] 与 T[i] 失配时，且 j > 0 (即不是模式串的第一个字符失配)，我们应该将模式串的指针 j 更新为 π[j-1]。这意味着模式串的下一个需要比较的字符是 P[π[j-1]]，它将与主串的 T[i] 进行比较。如果 j 已经为 0 (模式串的第一个字符就失配)，则只能将主串指针 i 向前移动一位。

计算部分匹配表 (π 数组 或 next 数组):

计算 π 数组本身也是一个模式匹配的过程，只不过是模式串与它自身的前缀进行匹配。

设模式串 P 的长度为 m。π 数组的大小为 m。
我们从 π[0] 开始计算。按照定义，长度为 1 的前缀 (P[0]) 没有真前缀和真后缀，所以 π[0] = 0。

我们使用两个指针：i (当前计算 π 值的索引，从 1 到 m-1) 和 length (已知的最长前缀/后缀的长度，也是 π[i-1] 计算完成后可能用到的长度)。
初始化 π[0] = 0，length = 0，i = 1。

遍历 i 从 1 到 m-1:
1. 比较 P[i] 和 P[length]。
2. 如果 P[i] == P[length]: 说明 P[0...length] 的下一个字符 P[length] 与 P[i] 匹配，那么 P[0...length] 是 P[0...i] 的一个前缀，并且 P[i-length...i] 是 P[0...i] 的一个后缀。由于 P[0...length-1] 已经是 P[0...i-1] 最长的公共前后缀，现在 P[length] == P[i], 那么 P[0...length] 就是 P[0...i] 最长的公共前后缀。所以，将 length 增加 1，并设置 π[i] = length。然后继续下一个 i。
3. 如果 P[i] != P[length]: 说明当前的 length 不能继续扩展了。我们需要寻找一个更短的长度 length'，使得 P[0...length'-1] 是 P[0...i-1] 的一个公共前后缀，并且 P[length'] 能够与 P[i] 匹配。根据 π 数组的定义，π[length-1] 就是 P[0...length-1] 这个字符串中，最长的既是真前缀又是真后缀的长度。所以，我们将 length 更新为 π[length-1]，然后继续比较 P[i] 和 P[length]。这个过程是一个循环，直到 length 变为 0。
* 如果在 length > 0 的情况下，我们设置 length = π[length-1]，然后回到步骤 1（比较 P[i] 和新的 P[length]）。
* 如果 length 已经变为 0，并且 P[i] 仍然不等于 P[0]，说明 P[0...i] 没有长度大于 0 的公共前后缀，设置 π[i] = 0。然后将 i 增加 1，继续下一个 i 的计算。
* 如果 length 已经变为 0，并且 P[i] 等于 P[0]，说明 P[0] 是 P[0...i] 最长的长度为 1 的公共前后缀，设置 π[i] = 1，并设置 length = 1。然后将 i 增加 1，继续下一个 i 的计算。

计算 π 数组示例：

设模式串 P = "ABACABABC"，长度 m = 9。
π 数组大小为 9。
π[0] = 0 (约定或根据定义)

i = 1: P[1] = 'B', length = 0, P[length] = P[0] = 'A'. 'B' != 'A'. length 已经是 0。所以 π[1] = 0. length 仍然是 0.

i = 2: P[2] = 'A', length = 0, P[length] = P[0] = 'A'. 'A' == 'A'. 匹配。length 变为 0 + 1 = 1. π[2] = 1.

i = 3: P[3] = 'C', length = 1, P[length] = P[1] = 'B'. 'C' != 'B'. length > 0. length 更新为 π[length-1] = π[1] = 0. 现在 length = 0. P[3] = 'C', P[length] = P[0] = 'A'. 'C' != 'A'. length 仍为 0. 所以 π[3] = 0. length 仍然是 0.

i = 4: P[4] = 'A', length = 0, P[length] = P[0] = 'A'. 'A' == 'A'. 匹配。length 变为 0 + 1 = 1. π[4] = 1.

i = 5: P[5] = 'B', length = 1, P[length] = P[1] = 'B'. 'B' == 'B'. 匹配。length 变为 1 + 1 = 2. π[5] = 2.

i = 6: P[6] = 'A', length = 2, P[length] = P[2] = 'A'. 'A' == 'A'. 匹配。length 变为 2 + 1 = 3. π[6] = 3.

i = 7: P[7] = 'B', length = 3, P[length] = P[3] = 'C'. 'B' != 'C'. length > 0. length 更新为 π[length-1] = π[2] = 1. 现在 length = 1. 继续比较 P[7] 和 P[length] = P[1]. P[7] = 'B', P[1] = 'B'. 'B' == 'B'. 匹配。length 变为 1 + 1 = 2. π[7] = 2.

i = 8: P[8] = 'C', length = 2, P[length] = P[2] = 'A'. 'C' != 'A'. length > 0. length 更新为 π[length-1] = π[1] = 0. 现在 length = 0. 继续比较 P[8] 和 P[length] = P[0]. P[8] = 'C', P[0] = 'A'. 'C' != 'A'. length 仍为 0. 所以 π[8] = 0. length 仍然是 0.

计算完成。π 数组为 [0, 0, 1, 0, 1, 2, 3, 2, 0]。

索引 q 字符 P[q] 前缀 P[0...q] 真前缀 真后缀 最长公共前后缀 长度 π[q]
0 A A (无) (无) (无) 0
1 B AB A B (无) 0
2 A ABA A, AB A, BA A 1
3 C ABAC A, AB, ABA C, AC, BAC (无) 0
4 A ABACA A, AB, ABA, ABAC A, CA, ACA, BACA A 1
5 B ABACAB A, AB, ABA, ABAC, ABACA B, AB, CAB, ACAB, BACAB AB 2
6 A ABACABA A,…ABACAB A,…ACABA ABA 3
7 B ABACABAB A,…ABACABA B,…CABAB AB 2
8 C ABACABABC A,…ABACABAB C,…ABABC (无) 0

这个 π 数组正是 KMP 算法进行高效匹配的关键。它告诉我们在模式串的某个位置失配后，模式串的下一个应该比较的字符是哪一个。

KMP 匹配算法

有了部分匹配表 π，KMP 匹配过程就相对简单了。

使用两个指针：
* i: 主串 T 的当前比较位置（从 0 到 n-1）。
* j: 模式串 P 的当前比较位置（从 0 到 m-1）。

初始化 i = 0, j = 0.

遍历主串 T:
当 i < n:
1. 如果 P[j] == T[i]: 字符匹配。两个指针都向前移动一位：i++, j++.
2. 如果 j == m: 说明模式串 P 已经完全匹配！一个匹配项在主串 T 的 i - m 位置找到。为了寻找下一个可能的匹配，我们不能简单地重置 j = 0 并从 i 开始。我们知道 P[0...m-1] 匹配了 T[i-m...i-1]。我们需要找到 P 的最长公共前后缀，其长度是 π[m-1]。这个长度为 π[m-1] 的前缀 P[0...π[m-1]-1] 也与 T[i-m...i-m+π[m-1]-1] 相等，并且这个子串也等于 P[m-π[m-1]...m-1]。所以，我们可以将模式串移动到新的位置，使得 P[0] 对齐到 T[i-π[m-1]]。在算法实现上，这相当于将模式串的指针 j 直接更新为 π[m-1]，然后继续比较 P[j] 和 T[i] (此时 i 已经指向匹配结束的后一个字符，无需回溯)。
3. 如果 P[j] != T[i] (失配) 且 j > 0: 说明 P[0...j-1] 已经匹配成功，但 P[j] 与 T[i] 不匹配。根据 π 数组的定义，我们需要将模式串的指针 j 更新为 π[j-1]。这个新的 j 值表示模式串中下一个应该与 T[i] 进行比较的字符的位置。主串指针 i 不变。
4. 如果 P[j] != T[i] (失配) 且 j == 0: 说明模式串的第一个字符就与主串当前字符不匹配。这时只能将主串指针 i 向前移动一位：i++. 模式串指针 j 保持 0 不变。

KMP 匹配示例：

设主串 T = "ABACABABCABA"，模式串 P = "ABACABABC"。
模式串 P 的 π 数组之前已经计算出来了：[0, 0, 1, 0, 1, 2, 3, 2, 0]。

初始化 i = 0, j = 0.

T 索引 (i) T[i] P 索引 (j) P[j] 比较结果 动作 i (next) j (next) π[j-1] (if j>0) 备注
0 A 0 A 匹配 i++, j++ 1 1
1 B 1 B 匹配 i++, j++ 2 2
2 A 2 A 匹配 i++, j++ 3 3
3 C 3 C 匹配 i++, j++ 4 4
4 A 4 A 匹配 i++, j++ 5 5
5 B 5 B 匹配 i++, j++ 6 6
6 A 6 A 匹配 i++, j++ 7 7
7 B 7 B 匹配 i++, j++ 8 8
8 C 8 C 匹配 i++, j++ 9 9
9 j == m 匹配成功！位置 9-9=0。 j = π[m-1]=π[8]=0 9 0 π[8]=0 模式串完全匹配！位置 0。j回溯到π[8]=0
9 A 0 A 匹配 i++, j++ 10 1 从新的j位置继续比较 T[9]和P[0]
10 B 1 B 匹配 i++, j++ 11 2
11 A 2 A 匹配 i++, j++ 12 3
12 \0 3 C i == n 主串结束

在这个例子中，我们在主串索引 0 处找到了一个匹配。主串遍历完毕。

注意在 i=8, j=8 匹配后，j 变为 9，等于模式串长度。我们找到了一个匹配。然后我们将 j 更新为 π[m-1] = π[8] = 0，表示找到匹配后模式串的新对齐位置。i 保持在 9。下一次循环开始时，我们会比较 T[9] 和 P[0]。

让我们看一个失配的例子。假设 T = "ABACABAT"，P = "ABACABAB"。
P 的 π 数组：[0, 0, 1, 0, 1, 2, 3, 2] (长度 m=8)。

初始化 i = 0, j = 0.

T 索引 (i) T[i] P 索引 (j) P[j] 比较结果 动作 i (next) j (next) π[j-1] (if j>0) 备注
0 A 0 A 匹配 i++, j++ 1 1
1 B 1 B 匹配 i++, j++ 2 2
2 A 2 A 匹配 i++, j++ 3 3
3 C 3 C 匹配 i++, j++ 4 4
4 A 4 A 匹配 i++, j++ 5 5
5 B 5 B 匹配 i++, j++ 6 6
6 A 6 A 匹配 i++, j++ 7 7
7 T 7 B 不匹配 j > 0， j = π[j-1] 7 2 π[6]=3 -> π[2]=1 P[7] != T[7]。 j回溯到 π[7-1]=π[6]=3? 错了，应该是 j回溯到 π[j-1]=π[6]=3。哦，不对，π[6]是 P[0…6]的 next，失配发生在 P[7]。应该看 P[0…6]的最长前后缀，其长度是 π[6]=3。所以新的j应该是 3。
修正：当 P[j] 与 T[i]失配时，我们知道 P[0…j-1] 匹配了 T[i-j…i-1]。我们需要找到 P[0…j-1]的最长公共前后缀的长度 k = π[j-1]。然后将模式串移动，使得 P[0…k-1] 对齐 T[i-k…i-1]。这时新的匹配点是 P[k] 与 T[i]。所以模式串指针直接更新为 k。
7 T 7 B 不匹配 j > 0， j = π[j-1] 7 3 π[6]=3 P[7] != T[7]。 j回溯到 π[7-1]=π[6]=3。
7 T 3 C 不匹配 j > 0， j = π[j-1] 7 0 π[2]=1 新的 j=3，比较 T[7] 和 P3，不匹配。j回溯到 π[3-1]=π[2]=1。
7 T 0 A 不匹配 j == 0， i++ 8 0 新的 j=1，比较 T[7] 和 P1，不匹配。j回溯到 π[1-1]=π[0]=0。现在 j=0。比较 T[7] 和 P0，不匹配。j==0，i++。
8 \0 0 A i == n 主串结束

这个例子展示了失配时 j 如何根据 π 数组回溯，而 i 保持不变。

KMP 算法实现 (Python 示例)

“`python
def compute_prefix_function(pattern):
“””
计算模式串的部分匹配表（前缀函数 π 或 next 数组）
Args:
pattern: 模式串 P
Returns:
π 数组 (list of int)
“””
m = len(pattern)
pi = [0] * m # 初始化π数组，长度为 m
length = 0 # length 记录当前计算位置 i 的最长公共前后缀的长度
# π[0] 始终为 0，从索引 1 开始计算
i = 1

while i < m:
    # Case 1: 当前字符 pattern[i] 和 pattern[length] 匹配
    if pattern[i] == pattern[length]:
        length += 1
        pi[i] = length
        i += 1
    # Case 2: 不匹配
    else:
        # Case 2.1: length > 0，根据 π 数组回溯到前一个最长公共前后缀的长度
        # pattern[length] 是当前不匹配的字符，我们回到其前一个最长公共前后缀的末尾
        # 也就是将 length 更新为 pi[length-1]
        if length != 0:
            length = pi[length - 1]
            # 注意：这里不增加 i，因为我们需要用新的 length 值（对应 pattern 的新前缀）
            # 再次尝试与 pattern[i] 匹配
        # Case 2.2: length == 0， pattern[i] 和 pattern[0] 不匹配
        # 说明 pattern[0...i] 没有长度大于 0 的公共前后缀
        else:
            pi[i] = 0
            i += 1
return pi

def kmp_search(text, pattern):
“””
使用 KMP 算法在文本串中查找模式串
Args:
text: 主串 T
pattern: 模式串 P
Returns:
匹配成功的起始索引列表
“””
n = len(text)
m = len(pattern)

if m == 0:
    return list(range(n + 1)) # 空模式串匹配所有位置

if m > n:
    return [] # 模式串比主串长，不可能匹配

pi = compute_prefix_function(pattern)

match_positions = [] # 记录匹配成功的起始索引
i = 0 # 主串指针
j = 0 # 模式串指针

while i < n:
    # Case 1: 当前字符 text[i] 和 pattern[j] 匹配
    if text[i] == pattern[j]:
        i += 1
        j += 1

    # Case 2: 模式串指针 j 已经到达模式串末尾，说明找到一个匹配
    if j == m:
        # 找到一个匹配，起始位置在 text 的 i - m
        match_positions.append(i - m)
        # 为了寻找下一个匹配，模式串指针需要根据 pi 数组回溯
        # 回溯到 pi[m-1] 的位置，表示模式串的最长公共前后缀长度
        # pattern[0...pi[m-1]-1] 已经匹配了 text[i-m...i-m+pi[m-1]-1]
        # 下一个需要比较的模式串字符是 pattern[pi[m-1]]
        j = pi[m - 1]

    # Case 3: 当前字符不匹配，且模式串指针 j > 0
    elif i < n and text[i] != pattern[j]:
        # 根据 pi 数组，将模式串指针回溯到 pi[j-1]
        # text[i] 将与 pattern[pi[j-1]] 再次比较
        if j != 0:
            j = pi[j - 1]
        # Case 4: 当前字符不匹配，且模式串指针 j == 0
        # 说明模式串的第一个字符就不匹配，主串指针向前移动一位
        else:
            i += 1

return match_positions

示例使用

text = “ABACABABCABA”
pattern = “ABACABABC”
positions = kmp_search(text, pattern)
print(f”文本串: {text}”)
print(f”模式串: {pattern}”)
print(f”部分匹配表 (π): {compute_prefix_function(pattern)}”)
print(f”匹配位置: {positions}”) # 期望输出: [0]

text2 = “AAAAAAAAB”
pattern2 = “AAAAB”
positions2 = kmp_search(text2, pattern2)
print(f”\n文本串: {text2}”)
print(f”模式串: {pattern2}”)
print(f”部分匹配表 (π): {compute_prefix_function(pattern2)}”)
print(f”匹配位置: {positions2}”) # 期望输出: [4]

text3 = “ABABABAB”
pattern3 = “ABAB”
positions3 = kmp_search(text3, pattern3)
print(f”\n文本串: {text3}”)
print(f”模式串: {pattern3}”)
print(f”部分匹配表 (π): {compute_prefix_function(pattern3)}”)
print(f”匹配位置: {positions3}”) # 期望输出: [0, 2, 4]

text4 = “THIS IS A TEST TEXT”
pattern4 = “TEST”
positions4 = kmp_search(text4, pattern4)
print(f”\n文本串: {text4}”)
print(f”模式串: {pattern4}”)
print(f”部分匹配表 (π): {compute_prefix_function(pattern4)}”)
print(f”匹配位置: {positions4}”) # 期望输出: [10]
“`

关于 j = pi[m-1] 的解释:

当 j == m 时，意味着 pattern[0...m-1] 与 text[i-m...i-1] 匹配成功。我们找到了一个匹配。为了寻找下一个匹配，模式串需要向右移动。新的模式串开头应该对齐 text 中某个位置，使得模式串的某个前缀与 text[i-m...i-1] 的某个后缀对齐。text[i-m...i-1] 正是 pattern[0...m-1]。所以我们是在寻找 pattern[0...m-1] 的最长公共前后缀，其长度为 pi[m-1]。这个长度为 k = pi[m-1] 的前缀 pattern[0...k-1] 等于其后缀 pattern[m-k...m-1]。当我们把模式串移动使得 pattern[0...k-1] 对齐 text[i-k...i-1] (也就是 pattern[m-k...m-1]) 时，模式串的下一个待比较字符是 pattern[k]，它将与 text[i] 对齐（因为 text[i] 是上一个匹配结束的后一个字符）。所以，在找到一个匹配后，将 j 更新为 pi[m-1] 是正确的做法。

关于 j = pi[j-1] 的解释:

当 text[i] != pattern[j] 且 j > 0 时，意味着 pattern[0...j-1] 与 text[i-j...i-1] 已经匹配。我们知道 text[i-j...i-1] 等于 pattern[0...j-1]。现在失配发生在 text[i] 和 pattern[j]。我们需要将模式串向右移动，使得模式串的某个前缀能够与 text[i-j...i-1] 的某个后缀对齐。text[i-j...i-1] 就是 pattern[0...j-1]。所以我们寻找 pattern[0...j-1] 的最长公共前后缀，其长度为 k = pi[j-1]。这段长度为 k 的前缀 pattern[0...k-1] 也是 pattern[0...j-1] 的后缀。新的对齐位置会使得 pattern[0...k-1] 对齐 text[i-k...i-1] (也就是 pattern[j-k...j-1])。此时模式串中应该与 text[i] 比较的字符是 pattern[k]。因此，将模式串指针 j 直接更新为 k = pi[j-1] 是正确的。主串指针 i 不变，因为 text[i] 还没有被参与到有效的匹配中，需要用新的 pattern[j] 来尝试匹配它。

KMP 算法的复杂度分析

KMP 算法分为两个阶段：计算部分匹配表和匹配过程。

  1. 计算部分匹配表 (compute_prefix_function):

    • 模式串长度为 m。
    • 指针 i 从 1 遍历到 m-1，总共进行 m-1 次外层循环。
    • 在每次循环中，如果 pattern[i] 与 pattern[length] 匹配，length 增加 1。i 增加 1。
    • 如果 pattern[i] 与 pattern[length] 不匹配：
      • 如果 length > 0，length 被更新为 pi[length-1]。这个操作会使 length 减小。
      • 如果 length == 0，i 增加 1。
    • 关键在于理解 length 的变化。在整个计算过程中，length 的值单调不减，每次匹配成功时增加 1，总共最多增加 m-1 次。当不匹配时，length 会减小（或保持 0），这个减小操作是基于 pi 数组的，length 的总减小量不会超过它之前的总增加量。因此，虽然有内层的 while length != 0 回溯，但每个字符 pattern[i] 最多导致 length 增加一次，也最多导致 length 减少有限次（因为 length 不能减到负数，总减小量受限于总增加量）。所以，计算 pi 数组的总时间复杂度是 O(m)。

  2. 匹配过程 (kmp_search):

    • 主串长度为 n，模式串长度为 m。
    • 主串指针 i 从 0 遍历到 n-1。i 只会向前移动，从不回溯。i 最多移动 n 次。
    • 模式串指针 j：
      • 匹配时，j 增加 1。j 的值不会超过 m。
      • 失配时，如果 j > 0，j 根据 pi[j-1] 减小。如果 j == 0，i 增加 1。
      • 匹配成功后，j 根据 pi[m-1] 减小。
    • 指针 i 至少移动 n 次 (从 0 到 n-1)。每次移动 i 时，i 增加 1。
    • 指针 j 每次成功匹配时增加 1。总共成功匹配次数加上失配回溯次数构成了总比较次数。
    • 考虑 i + j 的变化。每次成功匹配时 i 和 j 都增加 1，所以 i+j 增加 2。失配且 j > 0 时，j 减小，i 不变，i+j 减小。失配且 j == 0 时，i 增加 1，j 不变，i+j 增加 1。成功匹配后 j 减小，i 不变，i+j 减小。
    • 更直观的分析：主串指针 i 永远不会回溯，它从头走到尾最多 n 步。模式串指针 j 只会在匹配成功时增加，或者在失配时根据 pi 数组减小。j 的最大值是 m。对于主串中的每一个字符 T[i]，它最多与模式串中的某个字符 P[j] 进行一次匹配成功的比较（i++, j++），也最多与模式串中的某个字符 P[j] 进行有限次匹配失败的比较（j 回溯但 i 不变）。因为 j 的回溯总是利用 pi 数组将 j 移动到更小的值，而 j 的值始终非负，所以 j 回溯的总次数是有限的。总的比较次数不会超过 O(n + m)。
    • 因此，匹配过程的总时间复杂度是 O(n)。

总时间复杂度： 计算 π 数组 O(m) + 匹配过程 O(n) = O(n + m)。

空间复杂度： 需要额外 O(m) 的空间来存储 π 数组。

与暴力匹配的 O(m*n) 相比，KMP 算法的时间复杂度是线性的 O(n + m)，这在处理大规模文本时是巨大的优势。

总结与展望

KMP 算法是一个经典的字符串匹配算法，其核心思想是利用模式串本身的结构信息（通过预计算部分匹配表 π）来避免在失配时进行不必要的主串回溯。这使得 KMP 算法能够在 O(n + m) 的时间复杂度内完成字符串匹配，达到了理论最优（因为至少需要读取主串和模式串的所有字符）。

虽然 KMP 算法的 π 数组计算和匹配过程对于初学者来说可能有点抽象和难以理解，特别是 j = pi[j-1] 和 j = pi[m-1] 这两个关键的模式串指针移动步骤。理解其背后的逻辑（利用已匹配部分的公共前后缀信息来确定下一次比较的位置）是掌握 KMP 的关键。多画图，多模拟算法运行过程，是理解 KMP 的有效方法。

KMP 算法是许多更高级字符串算法（如 Rabin-Karp, Boyer-Moore 等）的基础，也是理解算法设计中“预处理”和“利用已知信息”思想的优秀案例。掌握 KMP 算法是学习更复杂文本处理和算法的良好起点。

希望这篇入门文章能帮助你迈出理解 KMP 算法的第一步！

发表评论

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

滚动至顶部