高效字符串匹配：KMP 算法原理与推导 – wiki基地

---

高效字符串匹配的艺术：KMP 算法原理与推导

在计算机科学的广阔领域中，字符串匹配是一个基础且频繁出现的问题。无论是文本编辑器的查找替换功能、搜索引擎的关键词匹配、生物信息学中的基因序列分析，还是网络安全中的入侵检测，高效的字符串匹配算法都扮演着至关重要的角色。最直观的暴力（Brute Force）匹配算法在某些场景下效率低下，其重复的比较和回溯操作成为了性能瓶颈。正是在这样的背景下，Donald Knuth、James H. Morris和Vaughan Pratt于1977年提出了著名的KMP（Knuth-Morris-Pratt）算法，它以其卓越的线性时间复杂度，为字符串匹配问题提供了一个优雅而高效的解决方案。

本文将深入探讨KMP算法的核心原理、详细推导过程、以及其在实际应用中的优势。

1. 字符串匹配问题概述与暴力算法的局限

问题定义： 给定一个文本串 T (长度为 n) 和一个模式串 P (长度为 m)，目标是找出 P 在 T 中所有出现的位置。

暴力（Brute Force）算法：
暴力算法的思路非常直观：
1. 从 T 的第一个字符开始，将 P 与 T 的当前子串进行比较。
2. 如果完全匹配，则记录当前匹配位置。
3. 如果不匹配，则将 P 向右移动一位，继续从 T 的下一个字符开始比较。

算法描述：
假设 T = t_0 t_1 ... t_{n-1}，P = p_0 p_1 ... p_{m-1}。
function BruteForceSearch(T, P):
n = length(T)
m = length(P)
for i from 0 to n - m: // i 是 T 的起始匹配位置
j = 0
while j < m and T[i + j] == P[j]:
j = j + 1
if j == m:
print "Pattern found at index", i

示例：
T = "ABABDABACDABABCABAB"
P = "ABABCABAB"

T 索引	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
T 字符	A	B	A	B	D	A	B	A	C	D	A	B	A	B	C	A	B	A	B
P 字符	A	B	A	B	C	A	B	A	B
匹配过程	T[0..8] vs P[0..8]
1. T[0] vs P[0]	A==A
2. T[1] vs P[1]	B==B
3. T[2] vs P[2]	A==A
4. T[3] vs P[3]	B==B
5. T[4] vs P[4]	D!=C (失配)
P右移		A	B	A	B	C	A	B	A	B
T 索引	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
T 字符	A	B	A	B	D	A	B	A	C	D	A	B	A	B	C	A	B	A	B
P 字符		A	B	A	B	C	A	B	A	B
匹配过程	T[1..9] vs P[0..8]
1. T[1] vs P[0]	B!=A (失配)
P右移			A	B	A	B	C	A	B	A	B
…以此类推

暴力算法的局限性：
1. 文本串回溯 (Text Pointer Backtracking): 当发生失配时，暴力算法会简单地将模式串 P 向右移动一位，然后文本串的匹配位置 i 和模式串的匹配位置 j 都将重置。这意味着文本串的指针 i 经常需要回溯到之前的位置，导致重复的比较。
2. 冗余比较： 在 P 向右移动后，它会重新比较一些之前已经比较过并匹配的字符。
3. 最坏时间复杂度： 在极端情况下，例如 T = "AAAAAAAAB"，P = "AAAAB"，每次失配都发生在 P 的最后一个字符，然后 P 只向右移动一位，文本串指针 i 几乎需要从头开始。这会导致 O(nm) 的时间复杂度，当 n 和 m 都很大时，效率非常低下。

KMP算法的诞生正是为了解决这些问题，它通过巧妙地预处理模式串，避免了在文本串中的回溯，从而将时间复杂度优化到线性 O(n+m)。

2. KMP算法的核心思想：不回溯文本指针

KMP算法的核心思想可以概括为：当模式串 P 与文本串 T 在某个位置发生失配时，我们不必像暴力算法那样将 P 完全回溯，而是可以利用已经匹配的信息，将 P 移动到下一个“可能”匹配的位置，从而避免 T 指针的回溯。

关键洞察：
假设在 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] ...
^ 已匹配部分 ^ ^ 失配 ^

我们现在要移动模式串 P。如果 P 移动后，它的一部分能够与 T[i-j...i-1] 的某个后缀重新匹配，那么我们就找到了一个新的匹配起点，可以避免从头开始比较。具体来说，我们希望找到 P 的一个前缀 P[0...k-1]，它既是 P[0...j-1] 的一个后缀，又是我们要尝试匹配的新的起始部分。

也就是说，我们想找到一个最长的 k < j，使得 P[0...k-1] 等于 P[j-k...j-1]。如果这样的 k 存在，那么当 P 移动后，P[0...k-1] 就能对齐到 T[i-k...i-1]，而 T[i-k...i-1] 正是 T[i-j...i-1] 的一个后缀，并且也与 P[j-k...j-1] 相等。这样，我们就可以从 T[i] 和 P[k] 处继续比较，而不是从 P[0] 重新开始。

这个 k 值，正是KMP算法中 “最长公共前后缀” 的长度，也是 next 数组（或称为LPS数组，Longest Proper Prefix which is also Suffix）存储的信息。

3. KMP的核心：next 数组（LPS数组）的构建与推导

next 数组（在某些资料中也称为 pi 数组或 lps 数组）是KMP算法的灵魂。它存储了模式串 P 自身的结构信息，指导着失配发生时模式串的移动。

定义：
next[j]（或 lps[j]）表示模式串 P 的前 j+1 个字符（即子串 P[0...j]）中，最长相等真前缀和真后缀的长度。
这里的“真前缀”是指不包含最后一个字符的任何前缀，“真后缀”是指不包含第一个字符的任何后缀。
例如，对于字符串 S = "ABCBA"：
* 真前缀有：”A”, “AB”, “ABC”, “ABCB”
* 真后缀有：”A”, “BA”, “CBA”, “BCBA”
* 最长相等真前缀和真后缀为空，长度为0。

示例： P = "ABABCABAB"

索引 i	字符 P[i]	子串 P[0...i]	真前缀	真后缀	最长相等真前缀/后缀	长度 next[i]
0	A	“A”	“”	“”	“”	0
1	B	“AB”	“A”	“B”	“”	0
2	A	“ABA”	“A”, “AB”	“A”, “BA”	“A”	1
3	B	“ABAB”	“A”, “AB”, “ABA”	“B”, “AB”, “BAB”	“AB”	2
4	C	“ABABC”	“A”, “AB”, …	“C”, “BC”, …	“”	0
5	A	“ABabca”	“A”, “AB”, …	“A”, “CA”, …	“A”	1
6	B	“ABABCAB”	“A”, “AB”, …	“B”, “AB”, …	“AB”	2
7	A	“ABABCABA”	“A”, “AB”, “ABA”, …	“A”, “BA”, “ABA”, …	“ABA”	3
8	B	“ABABCABAB”	“A”, “AB”, “ABA”, “ABAB”, …	“B”, “AB”, “BAB”, “ABAB”, …	“ABAB”	4

所以，对于 P = "ABABCABAB"，其 next 数组为 [0, 0, 1, 2, 0, 1, 2, 3, 4]。

next 数组的构建算法（KMP预处理）：
next 数组的构建本身就是一个字符串匹配问题，只不过是模式串与自身进行匹配。我们使用两个指针 i 和 j。
* i：用于遍历模式串 P 的当前字符，从1开始（P[0] 的 next 值固定为0）。
* j：表示当前已匹配的最长公共前后缀的长度，也指示了下一个要比较的字符在模式串中的位置 P[j]。

算法描述：
“`
function ComputeNextArray(P):
m = length(P)
next = array of size m
next[0] = 0 // 第一个字符的next值为0

j = 0              // j 表示当前最长公共前后缀的长度
for i from 1 to m - 1: // i 从 1 开始遍历模式串 P
    // 当 P[i] 与 P[j] 不匹配时，根据 next 数组回溯 j
    // 这里的 j 相当于模式串中，当前已匹配前缀的下一个字符的索引
    // next[j-1] 意味着 P[0...j-1] 的最长相等前后缀长度
    while j > 0 and P[i] != P[j]:
        j = next[j-1]

    // 如果 P[i] 与 P[j] 匹配，则 j 增长
    if P[i] == P[j]:
        j = j + 1

    // 记录 next[i] 的值
    next[i] = j
return next

“`

next 数组构建示例：P = "ABABCABAB"
m = 9，next 数组初始化为 [0, 0, 0, 0, 0, 0, 0, 0, 0]，next[0] = 0。

i	P[i]	j (匹配长度)	P[j]	P[i] == P[j]?	j 更新 (回溯)	j 更新 (匹配)	next[i]	备注
0	A	–	–	–	–	–	0	next[0] 约定为 0
1	B	0	P[0]=’A’	No	(j=0, 不回溯)	–	0	P[1]!=’P[0]`
2	A	0	P[0]=’A’	Yes	–	j=1	1	P[2]==’P[0]`
3	B	1	P[1]=’B’	Yes	–	j=2	2	P[3]==’P[1]`
4	C	2	P[2]=’A’	No	j = next[1] = 0	–	0	P[4]!=’P[2],j回溯到next[1]`
5	A	0	P[0]=’A’	Yes	–	j=1	1	P[5]==’P[0]`
6	B	1	P[1]=’B’	Yes	–	j=2	2	P[6]==’P[1]`
7	A	2	P[2]=’A’	Yes	–	j=3	3	P[7]==’P[2]`
8	B	3	P[3]=’B’	Yes	–	j=4	4	P[8]==’P[3]`

最终 next 数组为 [0, 0, 1, 2, 0, 1, 2, 3, 4]，与手工推导结果一致。

next 数组的意义与作用：
当文本串 T 与模式串 P 在 T[i] 和 P[j] 处发生失配时：
* 我们知道 P[0...j-1] 已经成功匹配了 T[i-j...i-1]。
* next[j-1] 的值 k 告诉我们，在已匹配的前缀 P[0...j-1] 中，其最长相等真前缀和真后缀的长度是 k。
* 这意味着 P[0...k-1]（模式串的前缀）与 P[j-k...j-1]（已匹配部分的后缀）是相同的。
* 因为 P[j-k...j-1] 又与 T[i-k...i-1] 相同（它们都是 T[i-j...i-1] 的后缀），所以我们现在可以确定 P[0...k-1] 已经匹配了 T[i-k...i-1]。
* 因此，我们只需要将模式串 P 移动，使得 P[k] 对齐到 T[i]，并继续从 P[k] 和 T[i] 开始比较即可。模式串的指针 j 直接跳到 k。
* 如果 k=0（即 next[j-1]=0），表示没有公共前后缀，那么模式串 P 需要整体右移，从 P[0] 重新开始匹配，并且 T 的指针 i 继续前进。

优化 next 数组 (nextval 数组)：
在某些实现中，会使用 nextval 数组对 next 数组进行优化。当 P[j] 与 P[next[j-1]] 相同的时候，如果发生失配，跳到 next[j-1] 处仍会失配，因此可以直接跳过。
“`
function ComputeNextValArray(P):
m = length(P)
nextval = array of size m
nextval[0] = 0

j = 0
for i from 1 to m - 1:
    while j > 0 and P[i] != P[j]:
        j = nextval[j-1] // 注意这里用的是 nextval 自身

    if P[i] == P[j]:
        j = j + 1

    if P[i] == P[j-1]: // 如果 P[i] 等于 P[next[i]-1] (即 P[j-1])
        nextval[i] = nextval[j-1]
    else:
        nextval[i] = j
return nextval

``
这种优化在模式串中存在大量重复字符时能进一步减少比较次数，但其核心思想与next数组一致，且原始next数组已经能够达到线性时间复杂度，所以通常使用原始next` 数组即可。

4. KMP匹配算法

有了 next 数组作为指引，KMP匹配过程变得简洁高效。它同样使用两个指针：
* i：文本串 T 的当前字符索引。
* j：模式串 P 的当前字符索引，也表示当前已匹配的模式串长度。

算法描述：
“`
function KMPSearch(T, P):
n = length(T)
m = length(P)
next = ComputeNextArray(P) // 或 ComputeNextValArray(P)

i = 0  // 文本串 T 的当前索引
j = 0  // 模式串 P 的当前索引 (也表示已匹配的长度)

while i < n:
    // 如果 T[i] 与 P[j] 匹配，或者 j 已经回溯到 0 且 T[i] 与 P[0] 失配
    // 当 P[j] 与 T[i] 不匹配，并且 j > 0 时，根据 next 数组回溯 j
    while j > 0 and T[i] != P[j]:
        j = next[j-1] // 模式串 P 移动到新的匹配起点

    // 如果 T[i] 与 P[j] 匹配，则同时推进 i 和 j
    if T[i] == P[j]:
        j = j + 1

    // 推进文本串指针 i
    i = i + 1

    // 如果 j 达到模式串长度 m，表示找到一个匹配
    if j == m:
        print "Pattern found at index", i - m
        // 找到一个匹配后，为了继续查找下一个匹配，模式串 P 需要继续移动
        // 移动到下一个可能匹配的位置，即根据 next 数组
        j = next[j-1]

“`

KMP匹配示例：
T = "ABABDABACDABABCABAB"
P = "ABABCABAB"
next = [0, 0, 1, 2, 0, 1, 2, 3, 4]

T 索引 i	P 索引 j	T[i]	P[j]	T[i] == P[j]?	j 更新 (回溯)	j 更新 (匹配)	next[j-1] (供参考)	备注
0	0	A	A	Yes	–	1	–	匹配 T[0] 和 P[0]
1	1	B	B	Yes	–	2	next[0]=0	匹配 T[1] 和 P[1]
2	2	A	A	Yes	–	3	next[1]=0	匹配 T[2] 和 P[2]
3	3	B	B	Yes	–	4	next[2]=1	匹配 T[3] 和 P[3]
4	4	D	C	No	j=next[3]=2	–	next[3]=2	T[4]!=P[4], j回溯到2
4	2	D	A	No	j=next[1]=0	–	next[1]=0	T[4]!=P[2], j回溯到0
4	0	D	A	No	(j=0, 不回溯)	–	–	T[4]!=P[0], j已为0
5	0	A	A	Yes	–	1	–	T[5]==’P[0]`
6	1	B	B	Yes	–	2	next[0]=0
7	2	A	A	Yes	–	3	next[1]=0
8	3	C	B	No	j=next[2]=1	–	next[2]=1	T[8]!=P[3], j回溯到1
8	1	C	B	No	j=next[0]=0	–	next[0]=0	T[8]!=P[1], j回溯到0
8	0	C	A	No	(j=0, 不回溯)	–	–	T[8]!=P[0], j已为0
9	0	D	A	No	(j=0, 不回溯)	–	–	T[9]!=P[0], j已为0
10	0	A	A	Yes	–	1	–
11	1	B	B	Yes	–	2	next[0]=0
12	2	A	A	Yes	–	3	next[1]=0
13	3	B	B	Yes	–	4	next[2]=1
14	4	C	C	Yes	–	5	next[3]=2
15	5	A	A	Yes	–	6	next[4]=0
16	6	B	B	Yes	–	7	next[5]=1
17	7	A	A	Yes	–	8	next[6]=2
18	8	B	B	Yes	–	9	next[7]=3	j达到 m=9，匹配成功！
(下一循环)	9	–	–	–	j=next[8]=4	–	next[8]=4	匹配后，j回溯到4，继续查找
19	4	(T结束)	–	–	–	–	–	i达到 n=19，循环结束

最终在 T 的索引 19 - 9 = 10 处找到模式串 P。

5. KMP算法的复杂度分析

1. 时间复杂度：
* next 数组构建： 在 ComputeNextArray 函数中，i 从 1 循环到 m-1，总共 m-1 次。内部的 while 循环中，j 的值只会增加或者根据 next 数组减少。j 的最大值为 m-1，每次回溯 j = next[j-1] 都意味着 j 至少减少1。在整个构建过程中，j 的增加总和不会超过 m（因为它最多从0到 m-1），j 的减少总和也不会超过 m。因此，next 数组的构建时间复杂度为 O(m)。
* KMP匹配： 在 KMPSearch 函数中，i 从 0 循环到 n-1，总共 n 次。内部的 while 循环和 next 数组构建类似，j 的值同样只会增加或者根据 next 数组减少。j 的增加总和不会超过 n（因为它最多从0到 m-1，并在每次匹配后重置，但 i 始终向前），j 的减少总和也不会超过 n。因此，KMP匹配的时间复杂度为 O(n)。

总时间复杂度：O(m) + O(n) = O(n+m)。这对于字符串匹配问题来说是线性的，达到了理论上的最优效率。

2. 空间复杂度：
* 主要空间消耗在于 next 数组，其大小为 m。
* 因此，空间复杂度为 O(m)。

6. KMP算法的优势与应用

优势：
1. 高效性： 线性时间复杂度 O(n+m)，远优于暴力算法的 O(nm)，尤其在 n 和 m 较大时优势显著。
2. 避免回溯： 文本串指针 i 从不回溯，始终向前移动。这对于处理流式数据（例如网络数据包、文件流）非常有利，因为它不需要重新读取已处理的文本。
3. 模式串预处理： next 数组的计算是独立于文本串的，可以提前完成，并在多次匹配同一个模式串时复用。

应用：
1. 文本编辑器和IDE： 实现查找、查找替换功能。
2. 搜索引擎： 对网页内容进行关键词匹配。
3. 生物信息学： DNA序列、蛋白质序列的模式匹配和比对。
4. 网络安全： 入侵检测系统（IDS/IPS）中，用于识别数据流中的恶意签名模式。
5. 编译器/解释器： 词法分析阶段识别关键字和标识符。
6. 数据压缩： 基于字典的压缩算法（如LZ77/LZ78）中的模式查找。

7. 总结

KMP算法是字符串匹配领域的一个里程碑，它巧妙地利用了模式串自身的结构信息，通过预处理构建 next 数组，从而在发生失配时避免了文本串指针的回溯，实现了线性时间复杂度的匹配。其优雅的原理和高效的性能，使其成为计算机科学中一个经久不衰的经典算法。理解KMP算法，不仅能解决实际问题，更能深入体会算法设计中“利用已知信息，避免重复劳动”的精髓。

通过本文的详细原理阐述和推导过程，相信读者已经对KMP算法有了全面而深刻的理解。从暴力匹配的低效，到KMP的巧妙优化，这不仅是一次算法的演进，更是计算思维方式的一次飞跃。

---