考研数据结构之串的模式匹配算法——KMP算法详解

---

一、KMP算法背景与核心思想

KMP算法（Knuth-Morris-Pratt算法）是字符串匹配领域的经典算法，由三位科学家共同提出。相较于传统的暴力匹配算法（BF算法），KMP通过预处理模式串生成部分匹配表（next数组），在匹配失败时跳过已知不可能匹配的位置，从而将时间复杂度优化至O(n+m)（主串长度n，模式串长度m）。

---

二、KMP算法核心概念

1. 前缀与后缀

• 前缀：除最后一个字符外，字符串的所有头部子串。例如，“ABCD"的前缀包括"A”, “AB”, “ABC”。
• 后缀：除第一个字符外，字符串的所有尾部子串。例如，“ABCD"的后缀包括"BCD”, “CD”, “D”。

2. 最长公共前后缀长度（next数组）

• 定义：对于模式串的每个子串（从首字符到当前位置），其最长相等前缀和后缀的长度。
• 作用：当字符匹配失败时，决定模式串的回退位置，避免主串指针回溯。

---

三、next数组构建步骤（手推过程）

以模式串"ABABAC"为例，演示next数组构建：

索引i	字符	最长公共前后缀长度（next[i]）	推导过程
0	A	0	单字符无前后缀
1	B	0	"AB"无公共前后缀
2	A	1	“ABA"的最长公共前后缀为"A”
3	B	2	“ABAB"的最长公共前后缀为"AB”
4	A	3	“ABABA"的最长公共前后缀为"ABA”
5	C	0	"ABABAC"无公共前后缀

关键公式：
next[i] = max{k | 模式串[0..k-1] == 模式串[i-k..i-1], 0≤k<i}

---

四、KMP算法匹配流程（实例解析）

问题：主串"ABABABACAB"，模式串"ABABAC"，求匹配位置。

1. 初始化：主串指针i=0，模式串指针j=0。
2. 匹配成功：i和j同步后移，直到j=5时，主串[i]=A vs 模式串[j]=C不匹配。
3. 查找next数组：next[5]=0，模式串回退至j=0，主串i保持当前位。
4. 继续匹配：最终在主串索引4处完成匹配。

核心代码逻辑：

def KMP(main_str, pattern):
    next = get_next(pattern)
    i = j = 0
    while i < len(main_str) and j < len(pattern):
        if j == -1 or main_str[i] == pattern[j]:
            i += 1
            j += 1
        else:
            j = next[j]  # 核心：模式串回退
    return j == len(pattern)

---

五、KMP算法优缺点分析

优点

• 时间效率高：主串指针无需回溯，适合处理流式数据。
• 稳定性强：最坏时间复杂度为O(n+m)，优于BF算法的O(n*m)。

缺点

• 空间开销：需额外存储next数组（O(m)空间）。
• 预处理成本：对短模式串或少量匹配场景，性价比低于BF算法。

---

六、KMP算法应用场景

1. 文本编辑器：实现快速查找/替换功能。
2. 搜索引擎：处理海量文本的关键字匹配。
3. 生物信息学：DNA序列比对（如寻找基因片段）。

---

七、考研真题解析

KMP算法是考研数据结构的重点内容之一，尤其在408统考中频繁出现。以下通过几道经典真题，深入解析KMP算法的解题思路和技巧。

---

真题1：2023年408真题

题目描述

已知主串S="ababcababak"，模式串T="ababac"，求：

1. 模式串T的next数组。
2. 主串S与模式串T的匹配过程，并指出首次匹配成功的位置。

解析

第一步：构建next数组

根据KMP算法的核心思想，next数组表示模式串每个位置对应的最长公共前后缀长度。以下是构建next数组的过程：

索引i	字符	最长公共前后缀长度（next[i]）	推导过程
0	a	0	单字符无前后缀
1	b	0	"ab"无公共前后缀
2	a	1	“aba"的最长公共前后缀为"a”
3	b	2	“abab"的最长公共前后缀为"ab”
4	a	3	“ababa"的最长公共前后缀为"aba”
5	c	0	"ababac"无公共前后缀

最终得到模式串T="ababac"的next数组为：
[0, 0, 1, 2, 3, 0]

第二步：匹配过程

初始化主串指针i=0，模式串指针j=0，按照KMP算法逐步匹配：

1. S[0]="a" vs T[0]="a"，匹配成功，i=1, j=1。
2. S[1]="b" vs T[1]="b"，匹配成功，i=2, j=2。
3. S[2]="a" vs T[2]="a"，匹配成功，i=3, j=3。
4. S[3]="b" vs T[3]="b"，匹配成功，i=4, j=4。
5. S[4]="a" vs T[4]="a"，匹配成功，i=5, j=5。
6. S[5]="c" vs T[5]="c"，匹配失败，查next数组得next[5]=0，回退j=0，主串i=5保持不变。
7. S[5]="c" vs T[0]="a"，匹配失败，继续查next数组得next[0]=-1，主串i=6，模式串j=0。
8. S[6]="a" vs T[0]="a"，匹配成功，i=7, j=1。
9. 依次类推，最终在主串索引5处完成匹配。

答案：首次匹配成功的位置为索引5。

---

真题2：2022年408真题

题目描述

已知主串S="abacababcabacabaad"，模式串T="abacab"，求：

1. 模式串T的next数组。
2. 主串S与模式串T的匹配过程，并指出所有匹配成功的位置。

解析

第一步：构建next数组

对模式串T="abacab"逐位计算最长公共前后缀长度：

索引i	字符	最长公共前后缀长度（next[i]）	推导过程
0	a	0	单字符无前后缀
1	b	0	"ab"无公共前后缀
2	a	1	“aba"的最长公共前后缀为"a”
3	c	0	"abac"无公共前后缀
4	a	1	“abaca"的最长公共前后缀为"a”
5	b	2	“abacab"的最长公共前后缀为"ab”

最终得到模式串T="abacab"的next数组为：
[0, 0, 1, 0, 1, 2]

第二步：匹配过程

初始化主串指针i=0，模式串指针j=0，逐步匹配：

1. S[0]="a" vs T[0]="a"，匹配成功，i=1, j=1。
2. S[1]="b" vs T[1]="b"，匹配成功，i=2, j=2。
3. S[2]="a" vs T[2]="a"，匹配成功，i=3, j=3。
4. S[3]="c" vs T[3]="c"，匹配成功，i=4, j=4。
5. S[4]="a" vs T[4]="a"，匹配成功，i=5, j=5。
6. S[5]="b" vs T[5]="b"，匹配成功，找到第一个匹配位置0。
7. 继续匹配剩余部分，最终发现另一个匹配位置为6。

答案：匹配成功的位置为索引0和6。

---

真题3：2021年408真题

题目描述

给定主串S="ababababca"，模式串T="ababc"，求：

1. 模式串T的next数组。
2. 主串S与模式串T的匹配过程，并说明匹配失败的原因。

解析

第一步：构建next数组

对模式串T="ababc"逐位计算最长公共前后缀长度：

索引i	字符	最长公共前后缀长度（next[i]）	推导过程
0	a	0	单字符无前后缀
1	b	0	"ab"无公共前后缀
2	a	1	“aba"的最长公共前后缀为"a”
3	b	2	“abab"的最长公共前后缀为"ab”
4	c	0	"ababc"无公共前后缀

最终得到模式串T="ababc"的next数组为：
[0, 0, 1, 2, 0]

第二步：匹配过程

初始化主串指针i=0，模式串指针j=0，逐步匹配：

1. S[0]="a" vs T[0]="a"，匹配成功，i=1, j=1。
2. S[1]="b" vs T[1]="b"，匹配成功，i=2, j=2。
3. S[2]="a" vs T[2]="a"，匹配成功，i=3, j=3。
4. S[3]="b" vs T[3]="b"，匹配成功，i=4, j=4。
5. S[4]="a" vs T[4]="c"，匹配失败，查next数组得next[4]=0，回退j=0，主串i=4保持不变。
6. 后续匹配过程中，发现无法找到完全匹配的位置。

答案：匹配失败，原因在于主串S中不存在完整的模式串T。

---

八、总结

通过以上真题解析可以看出，KMP算法的解题步骤主要包括以下两部分：

1. 构建next数组：利用最长公共前后缀的思想，逐位计算模式串的next值。
2. 匹配过程：结合next数组优化匹配效率，避免重复扫描主串。

建议考生在备考时，重点掌握手推next数组的方法和匹配逻辑，并结合代码实现加深理解。