第5 单元
匹 配 算 法
Gwszw四级1-7.indd 61 2023/9/13 9:53:20

跟我学 Python 四级 
“OK，No problem ！老师，明天见！”
“小萌，小帅，今天给你们留个作业：如果给
你们两个字符串A 和B，判断B 是否是A 的子串，
并返回B 在A 中第一次出现的位置，你们要如何
实现？明天课上告诉我答案啊。”
一夜无话，又到了上课的时间，小萌小帅早已来到了教室，脸上洋溢着自
信的微笑……
“小萌，小帅，昨天的问题你们想到答案了吗?”
“还不错，你们的这个算法有个名字，叫作暴力
匹配算法，今天我们就来讲一讲字符串匹配算法吧。”
“哈哈！我和小萌都想到答案了！只要将字符
串A 和B 对齐，一个一个字符比较，不匹配就让
B 和A 的第二个字符对齐，依次比较……”
5.1　字符串暴力匹配算法（BF算法）
1.算法介绍
字符串暴力匹配算法又称BF（Brute Force ）算法，它是一种最符合人类
Gwszw四级1-7.indd 62 2023/9/13 9:53:24 

第5单元　匹配算法
思维习惯的算法。其算法原理简单暴力，因此得名。具体做法如下。
“为了统一概念，在后文中，我们把字符串A 称为主串，
把字符串B 称为模式串。”
首先将主串和模式串左端对齐，逐一比较；如果第一个字符不能匹配，则
模式串向后移动一位继续比较；如果第一个字符匹配，则继续比较后续字符；
当某个字符发生不匹配时，模式串后移一位，如此往复，直至全部匹配或模式
串移动到超过主串尾部，匹配失败。
图5-1 展示了算法的具体匹配过程。
图5-1　暴力匹配算法演示
2.代码实现
原理比较简单，下面我们就使用代码来实现它。字符串暴力匹配算法实现
如下。
#text为主串，pattern为模式串
def bf(text，pattern): 
i ，j = 0 ，0 
while i < len(text) and j < len(pattern): 
#如果字符匹配，则继续比较后续字符 
if(text[i] == pattern[j]): 
i += 1 
j += 1 
#如果不匹配，模式串索引回溯到起始位置 
#主串回溯位置到比较开始时的下一个字符 
else: 
Gwszw四级1-7.indd 63 2023/9/13 9:53:27 

跟我学Python四级 
i = i - j + 1 
j = 0 
#如果模式串的所有字符都匹配成功，返回第一个匹配字符的位置 
if(j >= len(pattern)): 
return i - len(pattern) 
#匹配失败，返回-1 
else: 
return -1 
练练一
【问题5-1】使用BF 算法实现如下字符串匹配程序：给定一个主串
“abcokabkoh”和一个模式串“abk”，找出模式串在主串中第一次出现的位置，
若不存在则返回–1。
3.算法复杂度
暴力匹配算法的时间复杂度和空间复杂度按照以下方法进行计算。
假设主串长度为n，模式串长度为m。从算法原理可知，主串中的每个
字符都可能与模式串中的字符进行一一比较，因此最坏情况下的比较次数为
n×m，故算法的时间复杂度为O(nm)。当n 和m 值较小时，算法效率尚可，
但当m 和n 值较大时，算法效率下降明显。
暴力匹配算法不需要使用额外的存储空间，其空间复杂度为O(1)。
5.2　字符串匹配KMP算法
1.算法介绍
在暴力匹配算法中，每当发生字符不匹配时，根据算法策略，模式串后移
Gwszw四级1-7.indd 64 2023/9/13 9:53:28 

第5单元　匹配算法
一位开始新一轮的比较，这也正是暴力匹配算法效率较低的原因。如果我们能
在发生不匹配时打破后移一位的限制，动态确定模式串后移的长度，移动到下
一个最可能发生匹配的位置，那么算法的效率将大大提升，可这样的算法真的
存在吗？当然有，那就是著名的KMP 匹配算法。
KMP 算法使用三位发明者Knuth、Morris 和Pratt 名字的首字母命名，是
字符串匹配最经典的算法之一。
KMP 算法的原理较为复杂，我们就先通过案例来理解吧！使用KMP 算法
对如图5-2 所示的字符串进行匹配操作（上面为主串，下面为模式串）。
图5-2　字符串比较
如图5-3 所示，当进行第一轮比较时，与BF 算法类似，将主串与模式串
左端对齐，指针（箭头）所示位置发生了不匹配。在模式串中，发生不匹配的
字符之前，用方框标识两个子串“ABA”，我们分别将其称为“公共前缀”（蓝）
和“公共后缀”（绿）。
图5-3　公共前后缀
接下来，移动模式串，将“公共前缀”移动到“公共后缀”所在的位置，
移动后如图5-4 所示。
图5-4　将“公共前缀”移动到“公共后缀”
通过观察可以发现，因为公共前后缀是相同的，所以将“公共前缀”移动
到“公共后缀”所在的位置后，指针左侧上下的子串依然是匹配的。这样我们
就在确保不跳过可能存在的匹配的情况下，一次性移动了两个字符，打破了暴
力匹配算法中每次后移一个字符的限制。安全移动过程如图5-5 所示。
Gwszw四级1-7.indd 65 2023/9/13 9:53:32 

跟我学Python四级
“当然不会，小萌可以自己尝试下看看。”
“老师，这样移动真的不会遗漏可能存在的匹
配吗？”
图5-5　安全移动
“老师，果然如您所说，没有出现遗漏匹配的
情况，将'公共前缀'移动到'公共后缀'的位
置刚刚好！”
所以，我们可以总结出KMP 算法中模式串的移动规则为：当进行比较时，
模式串中某个字符X 发生不匹配时，只要找到字符X 左侧子串中的“公共前缀”
和“公共后缀”，将“公共前缀”移动到“公共后缀”所在位置，如此就实现
了模式串的跨越式移动。
“小帅问得好！现在我就来介绍下' 公共前
缀'和'公共后缀'的确定方法。”
“老师，上面例子中的'公共前缀'和'公共
后缀'是怎么确定的啊？”
公共前后缀的确定方法如下。
（1）前缀是指除最后一个字符外，一个字符串的全部头部组合。
（2）后缀是指除第一个字符外，一个字符串的全部尾部组合。
Gwszw四级1-7.indd 66 2023/9/13 9:53:34 

（3）“公共前后缀”是指模式串中前缀和后缀所共有的字符元素。
例如，下列各字符串的公共前后缀为：
“A”无前后缀，因为规定前后缀长度需小于子串长度，所以只有一个字符
的字符串公共前后缀的长度为0。

“AB”的前缀为[A]，后缀为[B]，共有元素为空，公共前后缀长度为0。

“ABA”的前缀为[A，AB]，后缀为[BA，A]，共有元素为“A”，公共前后
缀长度为1。

“ABAB”的前缀为[A，AB，ABA]，后缀为[BAB，AB，B]，共有元素为“AB”
， 
公共前后缀长度为2。

“ABABA”的前缀为[A，AB，ABA，ABAB]，后缀为[BABA，ABA，BA，A]
， 
共有元素为“A”“ABA”。出现了两对共有元素，长度分别为1、3，此时我们
选择最长的公共前后缀“ABA”，因此其公共前后缀长度为3。


在刚才的例子中我们找的并不仅仅是“公共前后缀”，准确地讲，应
该是“最长公共前后缀”。因为公共前后缀可能有多个，而我们找的是其
中最长的那一对。
其余的子串也按类似的方法进行处理。

当模式串中某一个字符发生不匹配时，仅根据“不匹配字符自身”和“最
长公共前后缀”就可以单方面确定下一次移动的距离，而这个过程与主串并无
关系。所以，可以在开始匹配操作之前就计算好每个字符发生不匹配时的移动
方案，并形成如表5-1 所示的移动方案表。

表5-1　发生不匹配时的移动方案


字符移动方案
A 最长公共前后缀长度为0，1号位与主串下一位比较
B 最长公共前后缀长度为0，1号位与主串当前位比较
A 最长公共前后缀长度为0，1号位与主串当前位比较
B 最长公共前后缀长度为1，2号位与主串当前位比较
A 最长公共前后缀长度为2，3号位与主串当前位比较
A 最长公共前后缀长度为3，4号位与主串当前位比较
A 最长公共前后缀长度为1，2号位与主串当前位比较
B 最长公共前后缀长度为1，2号位与主串当前位比较
A 最长公共前后缀长度为2，3号位与主串当前位比较
B 最长公共前后缀长度为3，4号位与主串当前位比较
A 最长公共前后缀长度为4，5号位与主串当前位比较
A 最长公共前后缀长度为5，6号位与主串当前位比较

Gwszw四级1-7.indd 67 


2023/9/13 9:53:35 


跟我学Python四级
这个移动方案是怎么得到的呢？我们来解读一下。
为了便于描述，先为模式串中的每个字符进行编号（从1 开始），如图5-6 
所示。
图5-6　为模式串字符编号（从1 开始）
假设发生如图5-7 所示的情况，即模式串中的第4 个字符B 发生不匹配。
图5-7　计算移动方案
为了确定其移动方式，根据算法规则，需要先确定其左侧子串“ABA”中
的最长公共前后缀，子串“ABA”的最长公共前后缀为“A”，随后将公共前缀
移动到公共后缀所在位置，移动后的效果为：模式串的2 号位（即第二个字符B）
与主串当前位对齐。因此，只要当4 号位的字符B 发生不匹配时，我们都按照
同样的方案进行移动即可。对模式串中的每个字符重复以上计算过程，最终就
得到了移动方案表。
通过观察可以发现如下规律：如果最长公共前后缀的长度为n，就可以得
到“将模式串n+1 号位与主串当前位比较”的规则。
接下来，我们将模式串的第一个字符的值标记为0（该字符比较特殊，其
值通常直接赋值为0），其余字符按移动方案中开头数字编号，如模式串中的第
二个字符“B”，其移动方案为“1 号位与主串当前位比较”，所以其值标记为1，
以此类推，我们就可以得到值与字符下标的对应关系表，该表通常称为Next 表，
如表5-2 所示。
表5-2　Next 表
字符A B A B A A A B A B A A 
下标1 2 3 4 5 6 7 8 9 10 11 12 
值0 1 1 2 3 4 2 2 3 4 5 6 
Gwszw四级1-7.indd 68 2023/9/13 9:53:38 

Next 表指明了当特定字符发生不匹配时，模式串要移动到的位置。因此
在算法开始正式的匹配运算前，程序需要先生成Next 表，这个阶段被称为“预
处理阶段”。

2.代码实现
KMP 算法的实现代码如下。

''' 

构造临时next数组
''' 
def getNext(pattern):

 #初始化next数
组 
next_list = [0 for i in range(len(pattern))
] 
#初始化下标，j指向模式
串 
#t记录位置，便于next数组赋
值 
j = 
1 
t = 
0 
while j < len(pattern)
:


 #第一次比较：t等于0，直接进行赋值，初始化1号位移动方案，每次 
#长度自增1 
#后续比较：判断字符是否相等，Python数组下标从0开始，因此均减1 
if t == 0 or pattern[j - 1] == pattern[t - 1]:

 #长度加
1 
next_list[j] = t + 
1 
j += 
1 
t += 
1


 else: 
#字符不相等，t回
溯 
t = next_list[t - 1]


 return next_list 

''' 
KMP字符串匹配的主函数
若匹配成功，返回模式串在主串中开始位置的下标


Gwszw四级1-7.indd 69 


2023/9/13 9:53:38 


跟我学Python四级
若匹配不成功，返回-1 
''' 
def KMP(text，pattern): 
next = getNext(pattern) 
#主串计数 
i = 0 
#模式串计数 
j = 0 
while i < len(text) and j < len(pattern): 
if (text[i] == pattern[j]): 
i += 1 
j += 1 
elif j != 0: 
#调用next数组 
j = next[j - 1] 
else: 
#不匹配主串指针后移 
i += 1 
if j == len(pattern): 
return i - len(pattern) 
else: 
return -1 
if __name__ == "__main__": 
text = 'abcxabcdabcdabcy' 
pattern = 'abcdabcy' 
out = KMP(text，pattern) 
print(out) 
练练一
【问题5-2】使用KMP 算法实现如下字符串匹配程序：给定一个主串
Gwszw四级1-7.indd 70 2023/9/13 9:53:39