KMP算法：最全面的字符串模式匹配解析
引言：字符串匹配的挑战与KMP的诞生
在计算机科学中，字符串模式匹配是一个基础且核心的问题。它的任务是：给定一个主文本字符串 T (Text) 和一个模式字符串 P (Pattern)，查找 P 是否出现在 T 中，如果出现，则返回其所有起始位置。这个问题广泛应用于文本编辑器的查找替换功能、搜索引擎、生物信息学（如DNA序列匹配）、网络入侵检测系统以及编译原理中的词法分析等领域。
最直观、最简单的字符串匹配方法是“暴力算法”（Brute-Force Algorithm）。它的原理是，将模式字符串的第一个字符与主文本字符串的每一个字符依次对齐，然后逐个比较后续字符。如果所有字符都匹配成功，则找到一个匹配；如果遇到不匹配，就将模式字符串向右移动一位，然后从模式的开头重新开始比较。这种方法简单易懂，但在最坏情况下，其时间复杂度可高达O(m*n)，其中n是主文本的长度，m是模式的长度。例如，在文本”AAAAAAAAAB”中查找模式”AAAAB”时，暴力算法会进行大量的重复比较，效率低下。
为了解决暴力算法的低效率问题，多位计算机科学家提出了更高效的算法。其中，由D.E.Knuth、J.H.Morris和V.R.Pratt三人于1977年同时独立发表的KMP（Knuth-Morris-Pratt）算法，就是其中一颗璀璨的明星。KMP算法的核心思想是：在匹配过程中，当发生失配时，不回溯主文本指针，而是利用模式串自身的特性（即已匹配部分的信息）来确定模式串下一次移动的最佳位置。这使得KMP算法能在线性时间复杂度 O(m+n) 内完成匹配，大大提升了效率。
一、暴力算法的局限性：KMP的必要性
在深入KMP算法之前，我们先通过一个例子来直观感受暴力算法的低效。
暴力算法原理：
1. 将模式串 P 的首字符与文本串 T 的首字符对齐。
2. 从左到右逐个比较 P 和 T 中对应的字符。
3. 如果所有字符都匹配，则匹配成功。
4. 如果遇到失配，则将 P 整体向右移动一位，然后从 P 的首字符重新开始比较。
示例：
T = "ABC ABCDAB ABCDABCDABDE"
P = "ABCDABD"
| 步骤 | 文本 T (i) | 模式 P (j) | 比较结果 |
|---|---|---|---|
| 1 | ABC ABCDAB … (0) | ABCDABD (0) | T[0]=P[0]√ |
| ABC ABCDAB … (1) | ABCDABD (1) | T[1]=P[1]√ | |
| ABC ABCDAB … (2) | ABCDABD (2) | T[2]=P[2]√ | |
| ABC ABCDAB … (3) | ABC DABD (3) | T[3]!=P[3]× (失配) | |
| 2 | ABC ABCDAB … (1) | ABCDABD (0) | T[1]!=P[0]× (失配) |
| 3 | ABC ABCDAB … (2) | ABCDABD (0) | T[2]!=P[0]× (失配) |
| 4 | ABC ABCDAB … (3) | ABCDABD (0) | T[3]=P[0]√ |
| ABC ABCDAB … (4) | ABCDABD (1) | T[4]=P[1]√ | |
| ABC ABCDAB … (5) | ABCDABD (2) | T[5]=P[2]√ | |
| ABC ABCDAB … (6) | ABC DABD (3) | T[6]=P[3]√ | |
| ABC ABCDAB … (7) | ABCDABD (4) | T[7]=P[4]√ | |
| ABC ABCD AB … (8) | ABCD ABD (5) | T[8]=P[5]√ | |
| ABC ABCD ABC … (9) | ABCD ABD (6) | T[9]!=P[6]× (失配) | |
| … | （继续移动并重复比较） | （继续移动并重复比较） |
可以看到，当暴力算法在 T[3] 和 P[3] 处失配时，它将模式串 P 向右移动了一位，并重新从 P[0] 开始与 T[1] 进行比较。这种做法导致了主文本指针 i 的频繁回溯（在示例中，虽然没有显式回溯 i，但每次模式串的移动，都相当于对 T 中已经比较过的字符进行了无效的重复比较）。在最坏情况下，暴力算法的时间复杂度为 O(m*n)，这是KMP算法要解决的核心痛点。KMP算法通过预处理模式串，构建一个“部分匹配表”（或称“next数组”），使得在失配发生时，可以直接将模式串移动到下一个可能匹配的位置，从而避免了主文本指针的回溯。
二、KMP算法的核心思想：不走回头路
KMP算法的精髓在于，当模式串与主文本在某个字符处发生失配时，算法并不会简单地将模式串向右移动一位，然后从头开始比较。相反，它会利用已经匹配成功的部分（失配点之前的字符），计算出模式串应该向右移动多少位，以便下一个字符的比较能够从一个“有希望”的位置开始。这个“有希望”的位置，就是模式串中“最长的公共前后缀”的长度所决定的。
我们通过一个例子来理解这个思想：
假设 T = "ABCABD"，P = "ABCAB"。
1. A 匹配 A
2. B 匹配 B
3. C 匹配 C
4. A 匹配 A
5. B 匹配 B
此时，T 的指针指向 D，P 的指针指向末尾（因为 ABCAB 已全部匹配）。假设 P 是 ABCABC，那么当 T 的 D 与 P 的 C 发生失配时：
T: A B C A B D ...
P: A B C A B C
^ 失配
暴力算法会这样处理：
T: A B C A B D ...
P: A B C A B C
然后继续比较 T[1] 和 P[0]。
然而，KMP算法会发现，在已匹配的 ABCAB 中，它的最长公共前后缀是 AB (长度为2)。也就是说，模式串 P 的前两个字符 AB 和它后两个字符 AB 是相同的。
既然 T 中的 ABCAB 部分已经匹配，而 P 的 AB 部分与 P 自身的 AB 后缀是相同的，那么我们可以将模式串直接移动到 P 的 C (索引为2) 与 T 的 C (与 P 之前匹配的 C 对齐) 处，即 P 的 C 对齐到 T 中当前匹配 AB 的 C 后：
T: A B C A B D ...
P: A B C A B C
^ 从这里继续比较
这样，模式串就有效地向右滑动了 5 - 2 = 3 位，避免了 T 的指针回溯，也避免了对 T 中 ABC 部分的重复比较。这种智能的移动，正是通过预处理模式串，生成一个“部分匹配表”（Partial Match Table）或称“next数组”（也有称“LPS数组”，Longest Proper Prefix which is also a Suffix）来实现的。
三、核心：部分匹配表（next数组/LPS数组）的构建
next 数组是KMP算法的灵魂。它记录了模式串 P 中每个前缀的最长公共前后缀的长度。
定义：
next[j] 表示模式串 P 中 P[0...j-1] 这个子串（长度为j）的最长公共前后缀的长度。
– “前缀”是指从字符串开头到某个位置的子串。
– “后缀”是指从某个位置到字符串结尾的子串。
– “真前缀”和“真后缀”是指除了字符串本身之外的前缀和后缀。
示例：P = "ABCDABD"
| j (长度) | P[0…j-1] 子串 | 前缀 | 后缀 | 最长公共前后缀 | 长度 (next[j]) |
|---|---|---|---|---|---|
| 0 | (空串) | – | – | – | -1 (或0) |
| 1 | “A” | “” | “” | “” | 0 |
| 2 | “AB” | A, B | B, A | “” | 0 |
| 3 | “ABC” | A, AB, B, BC, C | C, BC, ABC | “” | 0 |
| 4 | “ABCD” | A, AB, ABC, B, BC, BCD, C, CD, D | D, CD, BCD, ABCD | “” | 0 |
| 5 | “ABCDA” | A, AB, ABC, ABCD, B, BCDA, C, CDA, D, DA | A, DA, CDA, BCDA, ABCDA | “A” | 1 |
| 6 | “ABCDAB” | A, AB, ABC, ABCD, ABCDA, B, BCDB, C, CDB, D, DAB, AB | B, AB, DAB, CDAB, BCDAB, ABCDAB | “AB” | 2 |
| 7 | “ABCDABD” | A, AB, ABC, ABCD, ABCDA, ABCDAB… | D, BD, ABD, DABD, BDABD, CBDABD… | “ABD” | 3 |
根据这种方式计算，P = "ABCDABD" 的 next 数组为 [-1, 0, 0, 0, 0, 1, 2, 3]。
（注：next[0] 通常约定为 -1 或 0。如果约定为 -1，则在匹配算法中处理 j=0 时失配的情况会更简洁，表示模式串的下一个字符没有与文本串的任何字符匹配，需要将文本串指针 i 向前移动一位，模式串指针 j 归零。）
四、构建 next 数组的算法 (自匹配过程)
构建 next 数组的过程实际上就是模式串 P 对自身进行匹配的过程。我们使用两个指针：
– i：模式串的当前字符的下标，也代表当前正在计算 next[i]。
– k：已匹配的公共前后缀的长度，同时也代表 P 中用于比较的前缀的下一个字符的下标。
算法步骤：
1. 初始化 next[0] = -1 (或者 0，取决于约定，这里采用 -1)。
2. k = -1 (表示当前没有公共前后缀，或者说公共前后缀长度为0，P[k+1]是前缀的下一个字符)
3. i = 0 (从 P[0] 开始计算 next[1])
4. 循环直到 i 达到模式串的长度 m：
a. 如果 k == -1 (表示当前没有可用的公共前后缀，或者前缀已回溯到起始点) 或 P[i] == P[k] (当前字符匹配，可以扩展公共前后缀)：
* i++
* k++
* next[i] = k (记录当前公共前后缀的长度)
b. 否则 (P[i] != P[k])：
* k = next[k] (回溯 k，即跳到前一个公共前后缀的末尾的下一个字符，寻找更短的公共前后缀)
示例：P = "ABABCABAB"
| i | P[i] | k | P[k] | 比较 P[i] vs P[k] | next[i] | 说明 |
|---|---|---|---|---|---|---|
| 0 | A | -1 | – | k==-1 | (next[0]=-1) | |
k++->0, i++->1 |
||||||
| 1 | B | 0 | A | P[1]!=P[0] (B!=A) | next[1]=0 | |
k=next[0]->-1 |
k回溯到-1 | |||||
| -1 | – | k==-1 | ||||
k++->0, i++->2 |
next[2]=0 | |||||
| 2 | A | 0 | A | P[2]==P[0] (A==A) | ||
k++->1, i++->3 |
next[3]=1 | |||||
| 3 | B | 1 | B | P[3]==P[1] (B==B) | ||
k++->2, i++->4 |
next[4]=2 | |||||
| 4 | C | 2 | A | P[4]!=P[2] (C!=A) | ||
k=next[2]->0 |
k回溯到0 | |||||
| 0 | A | P[4]!=P[0] (C!=A) | ||||
k=next[0]->-1 |
k回溯到-1 | |||||
| -1 | – | k==-1 | ||||
k++->0, i++->5 |
next[5]=0 | |||||
| 5 | A | 0 | A | P[5]==P[0] (A==A) | ||
k++->1, i++->6 |
next[6]=1 | |||||
| 6 | B | 1 | B | P[6]==P[1] (B==B) | ||
k++->2, i++->7 |
next[7]=2 | |||||
| 7 | A | 2 | A | P[7]==P[2] (A==A) | ||
k++->3, i++->8 |
next[8]=3 | |||||
| 8 | B | 3 | B | P[8]==P[3] (B==B) | ||
k++->4, i++->9 |
next[9]=4 |
最终 P = "ABABCABAB" 的 next 数组为 [-1, 0, 0, 1, 2, 0, 1, 2, 3, 4]。
这个构建过程的时间复杂度是 O(m)，m是模式串的长度。因为 i 只会单调递增到 m，而 k 的回溯 k=next[k] 每次都会使 k 的值减小，但 k 的总增加量不超过 m，因此总操作次数为线性。
五、KMP搜索算法：利用next数组进行高效匹配
有了 next 数组，KMP算法的搜索过程变得非常高效。我们使用两个指针：
– i：主文本字符串 T 的当前字符的下标。
– j：模式字符串 P 的当前字符的下标。
算法步骤：
1. 初始化 i = 0 (文本指针从头开始)，j = 0 (模式指针从头开始)。
2. 循环直到 i 达到主文本的长度 n，或者 j 达到模式串的长度 m (如果只查找第一个匹配)：
a. 如果 j == -1 (表示模式串已回溯到起始点，或者之前没有匹配) 或 T[i] == P[j] (当前字符匹配)：
* i++
* j++
b. 否则 (T[i] != P[j])：
* j = next[j] (模式串发生失配，利用 next 数组将 j 回溯到上一个最长公共前后缀的下一个字符位置，即模式串向右滑动)
- 循环结束后：
a. 如果j == m，表示在T[i-m]处找到了一个匹配。
b. 如果i == n且j != m，表示主文本已遍历完，但没有找到匹配。
示例：T = "ABC ABCDAB ABCDABCDABDE", P = "ABCDABD"
next 数组为 [-1, 0, 0, 0, 0, 1, 2, 3] (长度为 7 的模式串，next 数组有 8 个元素，对应 P[0] 到 P[6] 的前缀，next[0] 对应空前缀，next[j] 对应 P[0…j-1])。
| i (T) | j (P) | T[i] | P[j] | T[i]==P[j]? | j=-1? | j=m? | 操作 | 说明 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | A | A | √ | i++, j++ |
A==A | ||
| 1 | 1 | B | B | √ | i++, j++ |
B==B | ||
| 2 | 2 | C | C | √ | i++, j++ |
C==C | ||
| 3 | 3 | D | × ( |
j=next[3] -> 0 |
T[3]为空格，与P[3]=D失配，模式串滑动 | |||
| 3 | 0 | A | × ( |
j=next[0] -> -1 |
继续失配，j回溯到-1 | |||
| 3 | -1 | √ | i++, j++ -> i=4, j=0 |
j=-1，模式串指针归零，文本指针前进一位 | ||||
| 4 | 0 | A | A | √ | i++, j++ |
A==A | ||
| 5 | 1 | B | B | √ | i++, j++ |
B==B | ||
| 6 | 2 | C | C | √ | i++, j++ |
C==C | ||
| 7 | 3 | D | D | √ | i++, j++ |
D==D | ||
| 8 | 4 | A | A | √ | i++, j++ |
A==A | ||
| 9 | 5 | B | B | √ | i++, j++ |
B==B | ||
| 10 | 6 | D | × ( |
j=next[6] -> 2 |
T[10]为空格，与P[6]=D失配，模式串滑动。下次从P[2]开始比较 | |||
| 10 | 2 | C | × ( |
j=next[2] -> 0 |
继续失配，下次从P[0]开始比较 | |||
| 10 | 0 | A | × ( |
j=next[0] -> -1 |
继续失配，j回溯到-1 | |||
| 10 | -1 | √ | i++, j++ -> i=11, j=0 |
j=-1，模式串指针归零，文本指针前进一位 | ||||
| 11 | 0 | A | A | √ | i++, j++ |
A==A | ||
| 12 | 1 | B | B | √ | i++, j++ |
B==B | ||
| 13 | 2 | C | C | √ | i++, j++ |
C==C | ||
| 14 | 3 | D | D | √ | i++, j++ |
D==D | ||
| 15 | 4 | A | A | √ | i++, j++ |
A==A | ||
| 16 | 5 | B | B | √ | i++, j++ |
B==B | ||
| 17 | 6 | D | D | √ | i++, j++ -> i=18, j=7 |
D==D | ||
| 18 | 7 | √ | 匹配成功！ P在T中起始位置为 i-m = 18-7 = 11 | P整个模式串已匹配完 | ||||
| 找到匹配后，将 j = next[j] = next[7] -> 3 | 继续查找下一个匹配，模式串滑动 | |||||||
| 18 | 3 | D | D | √ | i++, j++ |
继续匹配，因为P的ABD与T中的ABD匹配 | ||
| 19 | 4 | E | A | × (E!=A) | j=next[4] -> 0 |
失配，模式串滑动 | ||
| 19 | 0 | E | A | × (E!=A) | j=next[0] -> -1 |
失配，j回溯到-1 | ||
| 19 | -1 | E | √ | i++, j++ -> i=20, j=0 |
j=-1，模式串指针归零，文本指针前进一位 | |||
| 20 | 0 | A | × (空!=A) | j=next[0] -> -1 |
文本已结束，i达到n，循环终止 |
在上面的示例中，KMP算法成功在 T[11] 处找到了模式串 P 的一个匹配。整个过程中，主文本指针 i 从未回溯，始终向前移动，这正是KMP算法高效的关键。
六、时间与空间复杂度分析
1. 时间复杂度：
– 预处理（构建next数组）： 对模式串 P 进行一遍扫描，每个字符最多被访问两次（一次是 i 指针前进，一次是 k 指针回溯）。因此，时间复杂度为 O(m)，其中 m 是模式串的长度。
– 搜索（匹配过程）： 主文本指针 i 从 0 到 n-1 线性扫描，不会回溯。模式串指针 j 虽然会回溯，但每次回溯都是通过 next 数组跳到更小的位置，且 j 的总增加量不超过 n。因此，时间复杂度为 O(n)，其中 n 是主文本的长度。
– 总时间复杂度： O(m + n)。KMP算法在任何情况下都能保持线性时间复杂度，这是其最大的优势。
2. 空间复杂度：
– 需要一个 next 数组来存储模式串的预处理信息，其大小与模式串的长度 m 成正比。因此，空间复杂度为 O(m)。
七、KMP算法的优点与局限性
优点：
1. 高效性： KMP算法具有线性的时间复杂度 O(m+n)，这在处理大规模文本数据时非常高效。相比之下，暴力算法在最坏情况下为 O(m*n)。
2. 无回溯性： KMP算法在匹配过程中，主文本指针 i 从不回溯，始终向前移动。这对于处理流式数据或无法回溯的输入源非常有利。
3. 确定性： KMP算法的性能是可预测的，不受特定输入数据分布的影响，始终保持线性时间。
局限性：
1. 预处理开销： 需要额外的 O(m) 空间来存储 next 数组，并需要 O(m) 时间进行预处理。对于极短的模式串或者只进行一次匹配的场景，预处理的开销可能显得不那么划算。
2. 概念复杂性： KMP算法的原理（特别是 next 数组的构建）相对于暴力算法而言，理解起来更抽象和复杂。
八、KMP算法的应用场景
KMP算法作为一种经典的字符串匹配算法，在计算机科学的多个领域都有着广泛的应用：
1. 文本编辑器与搜索引擎： 实现“查找”和“替换”功能。KMP的高效性确保了在大文件中也能快速定位文本。
2. 生物信息学： 在基因组学中，KMP算法可用于DNA或蛋白质序列的匹配，查找特定的基因片段或蛋白质序列模式。
3. 网络安全： 在入侵检测系统（IDS）中，KMP算法可用于快速扫描网络数据包，检测已知的攻击模式或恶意代码签名。
4. 编译原理： 词法分析阶段，编译器需要识别程序源代码中的关键字、标识符等词法单元，KMP算法可以辅助实现这一功能。
5. 数据压缩： 某些数据压缩算法（如LZ77族）在查找重复字符串时，可能会借鉴KMP的思想。
6. 文件指纹与重复文件查找： KMP可以用于快速比对文件内容片段，从而识别重复文件或文件改动。
九、与其他字符串匹配算法的比较
除了KMP，还有其他一些著名的字符串匹配算法：
-
Boyer-Moore算法：
- 思想： 从模式串的末尾开始匹配，当发生失配时，利用“坏字符规则”和“好后缀规则”跳过尽可能多的字符，使得模式串的移动距离通常比KMP更大。
- 性能： 在实际应用中，对于较长的模式串，Boyer-Moore算法通常比KMP更快，因为它的平均时间复杂度接近
O(n/m)。但在最坏情况下，其时间复杂度仍为O(m*n)(虽然这种情况很少见)。 - 特点： 通常比KMP更快，但原理更复杂，且在某些极端情况下性能不如KMP稳定。
-
Rabin-Karp算法：
- 思想： 使用哈希函数对文本串的每个可能匹配的子串和模式串进行哈希，然后比较哈希值。如果哈希值匹配，再进行逐字符比较以确认（避免哈希碰撞）。
- 性能： 平均时间复杂度为
O(m+n)，但在最坏情况下（大量哈希碰撞）可能退化到O(m*n)。 - 特点： 适用于多模式匹配（查找多个模式串中的任意一个），因为一次计算可以比较多个哈希值。
-
Suffix Tree/Array（后缀树/后缀数组）：
- 思想： 是一种更高级的数据结构，将文本串的所有后缀组织成一个树形或数组结构。
- 性能： 构建这些数据结构的时间复杂度通常为
O(n)或O(n log n)。一旦构建完成，查询任何模式串的匹配位置可以在O(m)时间内完成。 - 特点： 非常强大，适用于处理大量查询（多次查询同一个文本串），或者更复杂的字符串操作（如查找最长公共子串、重复子串等）。构建开销较大，通常用于预处理阶段。
KMP算法在这些算法中，以其稳定的线性时间复杂度和相对简洁的实现（相对于Boyer-Moore或后缀树），在许多场景下仍是一个非常优秀且实用的选择。它保证了在任何输入下都能达到最佳的渐进时间复杂度，这对于需要稳定性能的系统至关重要。
总结
KMP算法是字符串模式匹配领域的一个里程碑。它通过巧妙地预处理模式串，构建了精妙的 next 数组，从而在模式串和文本串发生失配时，能够高效地利用已匹配信息，避免了主文本指针的回溯。这使得KMP算法在最坏情况下也能保持线性的时间复杂度 O(m+n)，大大超越了暴力算法的 O(m*n)。
KMP算法的优雅之处在于它将“发现问题”（失配）与“解决问题”（智能滑动）有机结合。通过对模式串自身的结构分析，它预知了在各种失配情况下模式串的最佳滑动距离，使得每一次比较都尽可能地有效。尽管其概念理解和 next 数组的构建需要一定的学习曲线，但一旦掌握，它将成为处理字符串匹配问题的强大工具。在计算机科学的诸多应用场景中，KMP算法至今仍然占据着重要地位，证明了其设计思想的卓越性和生命力。