第5单元
匹
配
算
法
5.1 知识点定位
青少年编程能力“Python四级”核心知识点4：匹配算法。
5.2 能
力
要
求
能够解释并实现暴力匹配（BF）算法、KMP算法、BM算法，掌握三种
字符串匹配算法的时间复杂度和空间复杂度计算方法。
5.3 建议教学时长
本单元建议6课时。
5.4 教
学
目
标
知识目标
1.
本单元主要学习三种常见字符串匹配算法的运行原理和代码实现，帮助学
习者理解暴力匹配、KMP、BM算法的算法思想，掌握各匹配算法的时间复杂
度和空间复杂度。
能力目标
2.
学习者能够根据应用场景和数据特征选择合适的算法完成字符串匹配
操作。
素养目标
3.
通过对各字符串匹配算法的学习，理解算法中蕴含的工程学思想和求解策
略，感受算法在社会生活和工作中发挥的重要作用，通过对算法从感性到理性
的认知提升过程，获得对计算机科学的探知欲望。
5.5 知
识
结
构
本单元知识结构如图5-1所示。
图5-1 匹配算法知识结构
5.6 补
充
知
识
常见字符串匹配算法
1.
除教材中提及的暴力匹配（BF）算法、KMP算法、BM算法外，常见
的匹配算法还有Rabin-Karp（哈希检索）算法、有限自动机算法（Finite
Automation）、Simon算法、Colussi算法、Galil-Giancarlo算法、Apostolico-
Crochemore算法、Horspool算法和Sunday算法等。
Rabin-Karp（哈希检索）算法
2.
RK算法的全称为Rabin-Karp算法，用两位发明者Rabin和Karp的名字
来命名。RK算法是在BF算法的基础上作了一些改进：通过字符串哈希值比较
代替字符串的遍历比较。该算法的核心思想就是通过比较两个字符串的哈希值
来判断是否包含对方。RK算法也可以进行多模式匹配，在论文查重等实际应
用中一般都是使用此算法。
算法描述：
步骤1：首先计算模式串的哈希值。
步骤2：分别从主串中取与模式串长度相同的多个子串，计算各子串的哈
希值。
步骤3：比较模式串哈希值与子串哈希值两者是否相等，如果哈希值不同，
则两者必定不匹配。如果相同，由于哈希冲突存在，也需要按照BF算法再次
判定。
举例说明：
主串S为“ABCDEFG”，模式串P为
“DEF”，如图5-2所示，使用RK算法进行
匹配的过程如下。
（1）首先计算子串“DEF”哈希值为
Hd，之后从原字符串中依次取长度为3的字
图5-2 计算模式串和各子串哈希值
符串“ABC”“BCD”“CDE”“DEF”计算哈希值，分别为Ha、Hb、Hc、Hd。
（2）依次将各子串哈希值与Hd进行比较，当哈希值相等时，仍然要比较
一次子串“DEF”和原字符串“DEF”是否一致。
算法复杂度：
RK算法相较BF提高了字符串的比较效率，但其算法的时间复杂度仍
与BF算法相同，时间复杂度为O(mn)（实际应用中往往较快，期望时间为
O(m+n)）。这是因为计算每一个连续子串的哈希值也有时间消耗，且跟遍历
比较的时间复杂度一样都是O(m)，所有子串的哈希值的计算时间复杂度为
O(mn)，因此，RK算法的整体时间复杂度还是O(mn)，进一步的优化点可以放
在哈希值的计算上。
算法补充说明如下：
（1）RK算法可以通过优化字符串累加方法来提升运行效率，即从第二个
子串开始，每个子串的哈希值都可以通过计算上一个哈希值的增量得到。
（2）通过使用优化方法，最终RK算法的时间复杂度可以优化为O(n)。
（3）与BF算法相比，免去了很多无谓的字符比较，时间复杂度上有很大
提高。
（4）RK算法的缺点在于哈希冲突，每一次哈希冲突时都要进行子串和模
式串的逐个比较，如果冲突过多，RK算法就会退化成BF算法。
Sunday算法
3.
Sunday算法由Daniel M.Sunday在1990年提出，其思想是从前往后匹配，
匹配失败时关注的不是失配位，而是主串中参加匹配的最末位字符的下一位
字符。
Sunday算法的匹配策略可以归结为以下两点。
（1）如果该字符没有在模式串中出现，则在下一轮比较时直接跳过，即：
移动位数 = 模式串长度 + 1。
（2）如果该字符在模式串中出现过，则移动位数 = 模式串长度–该字符最
右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。
举例说明:
主串S为“abdeababca”，模式串P
为“abc”，如图5-3所示，使用Sunday算
法进行匹配的过程如下。
第一轮比较：S[2]!=P[2],发生失配，那
图5-3 第一轮比较
么就关注主串中参与匹配的最末位字符的下一位，也就是S[3]，因为'e'不存
在于模式串P中，那么就将模式串移动4位(模式串长度+1)。
第二轮比较：S[6]!=P[2]发生失配，关注的字符为S[7]('b'),它存在于模式
串P中，移动模式串使得S[7]与该字符在模式串中最右的位置匹配上，即移
动2位，如图5-4所示。
第三轮比较：匹配成功，如图5-5所示。
图5-4 第二轮比较
图5-5 第三轮比较
算法复杂度：
Sunday算法最优情况的时间复杂度为O(n/m)，最差情况的时间复杂度为
O(mn)。假设主串是“aaabaaabaaabaaab”,模式串是“aaaa”。使用Sunday
算法进行匹配时,在大部分情况下，关注字符都是在模式串中存在的(模式串
只有'a'一个字符),换言之，在大部分情况下模式串都只能移动1位，时间复
杂度变为O(mn)。在实际使用中，Sunday算法比BM算法略优。
5.7 教学组织安排
教 学 环 节
教 学 过 程
建议课时
知识导入
以虚拟人物间的对话为引，抛出有关“字符串匹配算法”
的相关话题，引导学生自主思考字符串匹配实现方法，激
发学习兴趣，为后续知识点引入作铺垫
2课时
暴力匹配（BF）
（原理讲授）
对算法的实现原理进行简要介绍，结合案例对算法的操作
过程进行实例讲解
暴力匹配（BF）
（代码实现）
（1）对暴力匹配算法的代码实现进行讲解。
（2） 布置课堂练习，对学生进行辅导，使其当堂完成代码
编写
暴力匹配（BF）
（算法复杂度分析）
对暴力匹配算法的时间复杂度和空间复杂度分析方法进行
讲解
教 学 环 节
教 学 过 程
建议课时
KMP算法
（原理讲授）
（1）对算法的实现原理进行简要介绍，讲解的要点如下。
① 最长公共前后缀的确定方法。
② Next表的计算方法。
（2） 结合案例对算法的操作过程进行实例讲解，帮助学生
完成算法思想的内化吸收
2课时
KMP算法
（代码实现）
（1）对KMP算法的实现方法进行讲解。
（2） 布置课堂练习，对学生进行辅导，使其当堂完成代码
编写
KMP算法
（算法复杂度分析）
对KMP算法的时间复杂度和空间复杂度分析方法进行讲解
BM算法
（原理讲授）
（1） 对BM算法的实现原理进行简要介绍，BM算法原理讲
解的要点在于：与KMP算法相比，BM算法借助“好
后缀规则”和“坏字符规则”能够更高效地移动模式串。
（2） 结合案例对算法的实现原理和操作过程进行实例讲解，
引导学生自主完成算法操作步骤的总结、凝练，让学
生体会到BM算法的优势所在
2课时
BM算法
（代码实现）
（1）对BM算法的代码实现进行讲解。
（2） 布置课堂练习，对学生进行辅导，使其当堂完成代码
编写
BM算法
（算法复杂度分析）
对BM算法的时间复杂度和空间复杂度分析方法进行讲解
单元总结
对本讲知识进行总结归纳，布置课后作业和拓展阅读内容
5.8 教学实施参考
讨论式知识导入
1.
以老师与小萌、小帅的对话为引，引导学生自主思考字符串匹配的实现方
法，暴力匹配法最符合人类的思维习惯，根据学生回答自然过渡到暴力匹配算
法的讲解。
续表
知识点一：暴力匹配的算法思想
2.
（1）结合示例对暴力匹配的算法思想进行讲解，其核心思想是“主串与模
式串字符逐一比较，不匹配则模式串后移一位，开始新一轮的比较”。
（2）暴力匹配算法原理简单粗暴，但因其与人类思维习惯一般无二，所以
具有易于理解和实现的优点。
知识点二：暴力匹配的代码实现
3.
对暴力匹配算法的核心关键代码进行讲解，配合练习题帮助学生完成知识
内化吸收。
知识点三：暴力匹配的算法复杂度计算
4.
（1）假设主串长度为n，模式串长度为m，主串中的每个字符都可能与模
式串中的字符进行一一比较，所以其时间复杂度为O(nm)。
（2）当n和m值较小时，算法效率尚可，但当m和n值较大时，算法效
率下降明显。
（3）暴力匹配算法的空间复杂度为O(1)。
知识点四：KMP的算法思想
5.
（1）KMP算法的核心思想是“利用匹配失败后的信息，向右移动尽可能
大的距离，避免重复比较”。
（2）KMP算法能在发生不匹配时打破后移一位的限制，利用最长公共前
后缀计算得到Next表，根据Next表动态确定模式串后移的距离，移动到下一
个最可能发生匹配的位置，从而大大提升算法的匹配效率。
知识点五：KMP算法最长公共前后缀的计算方法
6.
（1）对前缀、后缀、公共前后缀的概念进行讲解，结合示例，对不同字符
组合情况下公共前后缀计算过程进行演示，帮助学生理解。
（2）注意强调：在出现多个公共前后缀时，选择最长的那一对。
知识点六：KMP中Next表的计算方法
7.
（1）Next表的计算与主串无关，仅根据“不匹配字符自身”和“最长公
共前后缀”就可以单方面完成计算。
（2）在匹配算法运行前，就可以完成Next表的计算，该阶段又称为预处
理阶段。
（3）为了便于学生理解，讲解应从“发生不匹配时的移动方案”入手，举
例说明如何得到每个字符失配时的移动方案，最终得出规律：如果最长公共前
后缀的长度为n，那么移动方案就是“n+1号位与主串当前位比较”。
（4）在此基础上，利用每个字符的移动方案平滑引出Next表的计算方法。
（5）对Next表的作用进行着重强调，即Next表指明了当特定字符发生不
匹配时，模式串要移动到的位置。
知识点七：KMP的代码实现
8.
对KMP算法的核心关键代码进行讲解，讲解主要分为两部分：Next数组
的构建和KMP字符串匹配主函数。因代码相对比较复杂，可要求学生参照教
材案例完成练习题，在模仿的过程中逐渐完成知识的内化吸收。
知识点八：KMP的算法复杂度计算
9.
（1）设主串长度为n,模式串长度为m。预处理阶段的时间复杂度为
O(m)，空间复杂度为O(m)；匹配过程中主串不回溯，比较次数可记为n，因此
KMP算法的总时间复杂度为O(m+n)，空间复杂度记为O(m)。
（2）相较暴力匹配算法，KMP算法通过一点点的空间消耗换得了极高的
时间提速，这是空间换时间思想的集中体现。
知识点九：BM的算法思想
10.
（1）BM算法的核心思想是“利用坏字符和好后缀规则跳过那些肯定不会
匹配的情况，减少比较次数”。
（2）BM算法在移动模式串的时候是从左到右，而进行比较的时候是从右
到左，即从模式串的尾部开始匹配。
（3）实现跨越式移动的关键在于“坏字符”和“好后缀”规则，两个规则
都会对模式串的移动距离造成影响，BM算法向右移动模式串的距离就是取坏
字符和好后缀算法得到的最大值。
知识点十：BM算法的“坏字符规则”
11.
（1）通过举例对坏字符规则的两种应用场景进行讲解。
（2）帮助学生总结出坏字符规则下的模式串移动距离计算公式。
知识点十一：BM算法的“好后缀规则”
12.
（1）通过举例对好后缀规则的三种应用场景进行讲解。
（2）帮助学生总结出好后缀规则下的模式串移动距离计算公式。
知识点十二：BM算法的代码实现
13.
对BM算法的核心关键代码进行讲解，讲解主要分为三部分：好后缀表的
构建、坏字符表的构建和BM字符串匹配主函数。因代码相对比较复杂，可要
求学生参照教材案例完成练习题，在模仿的过程中逐渐完成知识的内化吸收。
知识点十三：BM的算法复杂度计算
14.
（1）设主串长度为n,模式串长度为m。其预处理阶段的时间复杂度为
O(m+s)，空间复杂度为O(s)，s是与模式串和子串相关的有限字符集长度。
（2）搜索阶段，在最好的情况下，总的比较次数为(n–m)/m,此时的时
间复杂度为O(n/m)；在最坏的情况下，比较次数为(n–m)/2(m–2)，也就是
O(mn)，因此，BM算法的时间复杂度是O(mn)。
（3）从表面上看KMP算法拥有O(m+n)的时间复杂度，BM的时间复杂度
为O(mn)，但多篇学术文献的研究结果表明，在实际运行效率上反而是BM算
法更高，这是由于BM算法在实际运行过程中经常能达到算法的平均效率，甚
至最好情况下达到O(n/m)的时间复杂度。