KMP算法教程：一步步理解字符串查找优化

在计算机科学中，字符串查找是一个常见的操作。从文本编辑器中的“查找”功能到DNA序列分析，高效地在大段文本中查找特定模式字符串的需求无处不在。最直观的字符串查找方法（我们称之为“朴素算法”或“暴力匹配”）在某些情况下效率低下。为了解决这个问题，Donald Knuth、Vaughan Pratt 和 James Morris 三位计算机科学家在1977年共同提出了KMP (Knuth-Morris-Pratt) 算法，这是一种革命性的字符串匹配算法，它通过避免不必要的字符比较，将时间复杂度优化到线性。

1. 朴素字符串查找的困境

在深入KMP算法之前，让我们先回顾一下朴素匹配算法的工作原理。假设我们要在文本 T (text) 中查找模式 P (pattern)。

朴素算法步骤：

1. 将 P 的第一个字符与 T 的第一个字符对齐。
2. 从左到右逐个比较 P 和 T 中当前对齐位置的字符。
3. 如果所有字符都匹配，则找到模式。
4. 如果遇到不匹配，将 P 向右移动一位，然后从 P 的开头重新开始比较。

问题所在：

考虑以下例子：
文本 T: AAAAAB
模式 P: AAAB

1. AAAAAB
AAAB
   第一次比较：A == A (匹配)
   第二次比较：A == A (匹配)
   第三次比较：A == A (匹配)
   第四次比较：A != B (不匹配)

朴素算法会将模式 P 向右移动一位，然后重新从 P 的开头进行比较：

1. AAAAAB
AAAB
   （又会进行多次比较）

可以看到，在不匹配发生后，我们浪费了之前已经匹配过的信息，重新比较了模式中已经知道的部分。这种重复比较在最坏情况下（例如 T = AAAAA...AB，P = AAAAAB）会导致 O(M*N) 的时间复杂度，其中 N 是文本长度，M 是模式长度。KMP算法正是为了消除这种冗余而设计的。

2. KMP的核心思想：利用已知信息，避免回溯

KMP算法的关键在于，当模式串与文本串发生不匹配时，它不会简单地将模式串向右移动一位然后重新开始比较。相反，它会利用模式串自身的结构信息，计算出模式串应该“跳过”多少位，从而避免文本指针回溯。这种“跳过”的依据来源于一个叫做“最长公共前后缀”的概念，这通常通过一个预处理生成的LPS (Longest Proper Prefix which is also a Suffix) 数组（也常被称为“失效函数”或“前缀函数”）来实现。

2.1 什么是LPS数组 (失效函数)？

LPS数组 lps[] 对于模式 P 中的每一个位置 i，存储的是 P[0...i] 这个子串中，最长的真前缀（Proper Prefix）同时也是真后缀（Proper Suffix）的长度。

• 真前缀： 一个字符串的真前缀是指除了字符串本身之外的所有前缀。例如，对于 “ABC”，真前缀有 “A”, “AB”。
• 真后缀： 一个字符串的真后缀是指除了字符串本身之外的所有后缀。例如，对于 “ABC”，真后缀有 “C”, “BC”。

LPS数组的意义：

当模式 P 的 P[j] 字符与文本 T 的 T[i] 字符不匹配时，lps[j-1] 的值告诉我们，在 P[0...j-1] 中，最长的公共前后缀的长度。这意味着 P 的前 lps[j-1] 个字符已经和 T 的 T[i-lps[j-1]...i-1] 匹配成功。因此，我们可以将模式串移动到新的位置，使得 P 的 lps[j-1] 长度的前缀对齐到 T 中已经匹配过的部分，然后从 P[lps[j-1]] 处继续比较，而无需从 P[0] 重新开始。

例子：模式 P = "ABABCABAB"

我们来手动构建它的LPS数组：

索引 k	字符 P[k]	子串 P[0...k]	真前缀	真后缀	最长公共前后缀 (长度)	lps[k]
0	A	A	–	–	– (0)	0
1	B	AB	A	B	– (0)	0
2	A	ABA	A, AB	A, BA	A (1)	1
3	B	ABAB	A, AB, ABA	B, AB, BAB	AB (2)	2
4	C	ABABC	A, AB, ABA, ABAB	C, BC, ABC, BABC	– (0)	0
5	A	ABABCA	A, AB, ABA, ABAB, ABABC	A, CA, BCA, ABCA, BABCA	A (1)	1
6	B	ABABCAB	A, AB, ABA, ABAB, ABABC, ABABCA	B, AB, CAB, BCAB, ABCAB, BABCAB	AB (2)	2
7	A	ABABCABA	A, AB, ABA, ABAB, ABABC, ABABCA, ABABCAB	A, BA, ABA, CABA, BCABA, ABCABA, BABCABA	ABA (3)	3
8	B	ABABCABAB	A, AB, ABA, ABAB, ABABC, ABABCA, ABABCAB, ABABCABA	B, AB, BAB, ABAB, CABAB, BCABAB, ABCABAB, BABCABAB	ABAB (4)	4

所以，模式 P = "ABABCABAB" 的LPS数组为 [0, 0, 1, 2, 0, 1, 2, 3, 4]。

3. 构建LPS数组（预处理阶段）

构建LPS数组本身也是一个巧妙的匹配过程。我们使用两个指针 length 和 i。
* length 变量用于记录当前已经匹配的最长公共前后缀的长度。
* i 变量用于遍历模式串 P，指示当前正在处理的字符。

算法步骤：

1. 初始化 lps[0] = 0 (模式的单个字符子串没有真前缀或真后缀)。
2. 初始化 length = 0 (表示当前已匹配的最长公共前后缀长度)。
3. 初始化 i = 1 (从模式的第二个字符开始遍历)。
4. 当 i < 模式串长度 时，重复以下步骤：
   • 情况1：P[i] == P[length] (当前字符与 length 指向的字符匹配)
     • 这说明我们可以将公共前后缀的长度增加1。
     • length++
     • lps[i] = length
     • i++
   • 情况2：P[i] != P[length] (当前字符与 length 指向的字符不匹配)
     • 如果 length != 0 (表示之前有匹配的前缀)：
       • 我们需要寻找一个更短的公共前后缀。根据LPS数组的定义，lps[length-1] 存储了 P[0...length-1] 的最长公共前后缀长度。我们将 length 更新为 lps[length-1]，然后再次尝试比较 P[i] 和新的 P[length]。
     • 如果 length == 0 (表示没有匹配的前缀)：
       • 这意味着 P[0...i] 没有公共前后缀（除了空串）。
       • lps[i] = 0
       • i++

示例：构建 P = "ABABCABAB" 的LPS数组

初始：lps = [0, 0, 0, 0, 0, 0, 0, 0, 0] (全部初始化为0)
length = 0, i = 1

1. i = 1, P[1] = 'B', P[length] = P[0] = 'A'. 不匹配。
   length 为 0。
   lps[1] = 0, i = 2
lps = [0, 0, 0, 0, 0, 0, 0, 0, 0]

2. i = 2, P[2] = 'A', P[length] = P[0] = 'A'. 匹配。
   length = 1
lps[2] = 1, i = 3
lps = [0, 0, 1, 0, 0, 0, 0, 0, 0]

3. i = 3, P[3] = 'B', P[length] = P[1] = 'B'. 匹配。
   length = 2
lps[3] = 2, i = 4
lps = [0, 0, 1, 2, 0, 0, 0, 0, 0]

4. i = 4, P[4] = 'C', P[length] = P[2] = 'A'. 不匹配。
   length 不为 0 (length = 2)。
   length 更新为 lps[length-1] = lps[1] = 0。
   (现在 length = 0，我们再次尝试比较 P[4] 和 P[0])

5. i = 4, P[4] = 'C', P[length] = P[0] = 'A'. 不匹配。
   length 为 0。
   lps[4] = 0, i = 5
lps = [0, 0, 1, 2, 0, 0, 0, 0, 0]

6. i = 5, P[5] = 'A', P[length] = P[0] = 'A'. 匹配。
   length = 1
lps[5] = 1, i = 6
lps = [0, 0, 1, 2, 0, 1, 0, 0, 0]

7. i = 6, P[6] = 'B', P[length] = P[1] = 'B'. 匹配。
   length = 2
lps[6] = 2, i = 7
lps = [0, 0, 1, 2, 0, 1, 2, 0, 0]

8. i = 7, P[7] = 'A', P[length] = P[2] = 'A'. 匹配。
   length = 3
lps[7] = 3, i = 8
lps = [0, 0, 1, 2, 0, 1, 2, 3, 0]

9. i = 8, P[8] = 'B', P[length] = P[3] = 'B'. 匹配。
   length = 4
lps[8] = 4, i = 9
lps = [0, 0, 1, 2, 0, 1, 2, 3, 4]

最终得到的LPS数组为 [0, 0, 1, 2, 0, 1, 2, 3, 4]。

4. KMP字符串查找算法（匹配阶段）

LPS数组构建完成后，我们就可以利用它来高效地进行字符串匹配。同样，我们使用两个指针：
* i：文本 T 的当前字符索引。
* j：模式 P 的当前字符索引。

算法步骤：

1. 初始化 i = 0 (文本指针) 和 j = 0 (模式指针)。
2. 当 i < 文本长度 时，重复以下步骤：
   • 情况1：P[j] == T[i] (当前字符匹配)
     • i++ (文本指针前进)
     • j++ (模式指针前进)
   • 情况2：j == 模式串长度 (模式串完全匹配)
     • 这意味着我们找到了一个匹配项！匹配的起始索引是 i - j。
     • 为了寻找下一个可能的匹配（即使它们重叠），我们将 j 更新为 lps[j-1]。这样，模式串会进行“智能”的自我对齐，避免不必要的比较。
   • 情况3：P[j] != T[i] (当前字符不匹配)
     • 如果 j != 0 (模式指针不在模式开头)：
       • 根据LPS数组的指导，将 j 更新为 lps[j-1]。这意味着我们跳过了模式中已知不会匹配的部分，并尝试将模式的下一段最长公共前后缀与文本中当前的位置对齐。
     • 如果 j == 0 (模式指针在模式开头)：
       • 这意味着 P[0] 与 T[i] 不匹配，模式串无法进行任何有意义的自我对齐。
       • i++ (只移动文本指针，模式指针 j 保持 0)。

示例：T = "ABABDABACDABABCABAB"，P = "ABABCABAB"
LPS数组 lps = [0, 0, 1, 2, 0, 1, 2, 3, 4]

初始：i = 0, j = 0

i	T[i]	j	P[j]	比较结果	动作	i (next)	j (next)
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	B	3	B	匹配	i++, j++	4	4
4	D	4	C	不匹配	j != 0 -> j = lps[j-1] = lps[3] = 2	4	2
4	D	2	A	不匹配	j != 0 -> j = lps[j-1] = lps[1] = 0	4	0
4	D	0	A	不匹配	j == 0 -> i++	5	0
5	A	0	A	匹配	i++, j++	6	1
6	B	1	B	匹配	i++, j++	7	2
7	A	2	A	匹配	i++, j++	8	3
8	C	3	B	不匹配	j != 0 -> j = lps[j-1] = lps[2] = 1	8	1
8	C	1	B	不匹配	j != 0 -> j = lps[j-1] = lps[0] = 0	8	0
8	C	0	A	不匹配	j == 0 -> i++	9	0
9	D	0	A	不匹配	j == 0 -> i++	10	0
10	A	0	A	匹配	i++, j++	11	1
11	B	1	B	匹配	i++, j++	12	2
12	A	2	A	匹配	i++, j++	13	3
13	B	3	B	匹配	i++, j++	14	4
14	C	4	C	匹配	i++, j++	15	5
15	A	5	A	匹配	i++, j++	16	6
16	B	6	B	匹配	i++, j++	17	7
17	A	7	A	匹配	i++, j++	18	8
18	B	8	B	匹配	i++, j++	19	9
19	(结束)	9	(结束)	模式匹配	j == 模式串长度 -> 发现匹配，起始索引 i-j = 19-9 = 10。 j = lps[j-1] = lps[8] = 4	19	4
19	(结束)	4	(结束)	文本结束	循环结束	–	–

最终，KMP算法在文本索引 10 处找到了模式 ABABCABAB。

5. KMP算法的时间复杂度

KMP算法的效率体现在其线性时间复杂度：

• 预处理阶段（构建LPS数组）： O(M)，其中 M 是模式串的长度。每个字符至多被 i 和 length 指针访问两次。
• 匹配阶段： O(N)，其中 N 是文本串的长度。文本指针 i 从不回溯，最多遍历文本串一次。
• 总时间复杂度： O(M + N)。这比朴素算法在最坏情况下的 O(M*N) 效率大大提高。

6. KMP算法的优势

• 效率高： 线性时间复杂度，尤其适用于大型文本和模式。
• 无回溯： 文本指针从不回溯，这意味着它非常适合从流数据中匹配模式，因为流数据通常不允许回溯。
• 通用性： 广泛应用于文本处理、生物信息学（如DNA序列匹配）等领域。

7. 总结

KMP算法是一个优美且高效的字符串匹配算法，它通过巧妙地预处理模式串，生成LPS数组，从而在匹配过程中避免了不必要的字符比较和文本指针回溯。理解LPS数组的构建和其在匹配阶段的运用是掌握KMP算法的关键。通过本文的逐步解析和示例，希望能帮助你彻底理解并掌握KMP这一经典的计算机科学算法。