Python3实现KMP字符串匹配算法详解
本文介绍Python3中KMP字符串匹配算法的实现。首先对比暴力匹配法的时间复杂度问题，引出KMP算法的核心优化：通过计算模式串的next数组（基于最大前后缀长度）来避免回溯。文章详细解析next值的计算逻辑，并提供完整的Python代码示例，帮助开发者理解并应用该算法。
首先说明，笔者技术尚浅，撰写博客旨在记录学习历程、梳理个人理解与心得。文中若有疏漏或不当之处，恳请高手批评指正。
问题提出
给定一个主文本串test_str（被匹配对象）和一个模式串pat_str（需要查找的子串），目标是从test_str中找出pat_str首次出现的起始位置；若未找到，则返回-1。
暴力匹配法
在介绍KMP算法之前，我们先回顾最原始的“暴力匹配”方法。
text_str = 'asdabcdace'
pat_str = 'abcdace'
def str_match(text_str,pat_str):
for i in range(0,len(text_str)):
j = 1
while j < len(pat_str):
if text_str[i:i+j] != pat_str[0:j]: #从text_str第i个字符开始，看匹配是否成功
break #匹配失败，直接跳出循环，i+1，继续从第一个字符匹配
j += 1 #匹配成功就继续匹配下一个字符，知道pat_str每个字符都匹配完
if j == len(pat_str):
return i
return -1
print(str_match(text_str,pat_str))
之所以称为暴力解法，是因为每次匹配失败后，模式串仅向后移动一位，并从主串的下一个字符重新开始匹配，如此循环直至结束。这种方法导致时间复杂度较高，而KMP算法正是针对这一低效环节进行优化，其核心在于利用每次匹配失败时计算出的next值来确定下一次移动的距离。
KMP算法
若要完全透彻讲解KMP算法颇具难度，此处仅粗略梳理其实现步骤。我认为理解该算法的关键在于一个核心点：
如何计算模式串中每个字符对应的next值。
由于每次匹配失败时已匹配的字符长度不同，导致下一次移动的距离也各不相同。因此，我们需要一种方法来求解每个字符对应的next值，这引出了另一个重要概念：
最大前缀与最大后缀。
假设最大前缀与最大后缀的长度相等，记为k，那么第i位字符对应的next值即为k+1。通过一次循环遍历，即可求出每个字符对应的next值。
代码实现
#求字符串的next值
text_str = 'asdabcdace'
pat_str = 'abcdace'
#得到字符对应的next值
def str_next(s):
#前两个字符默认等于1
next = [1,1]
for x in range(2,len(s)):
next.append(str_max_prx(s,x,next[x-1]-1) + 1)
return next
#参数 s字符串，匹配进行到的位置，下次开始匹配的位置
def str_max_prx(s,x,last_value):
next = 0
for i in range(last_value,x):
if s[0:i] == s[x-i:x]:
next = i
return next
def str_match(s,m):
next = str_next(s)
i=0
s_len = len(s)
m_len = len(m)
while i <= m_len:
flag = True #标志位，用来判断是否匹配成功
index = 1
while index <= s_len:
if m[i:i + index] != s[0:index]:
i = i + next[index]
flag = False
break
else:
index += 1
if flag:
break
if i >= m_len:
i = -1
return i
res = str_match(pat_str,text_str)
print(res)
具体代码逻辑如上，其中许多细节需要读者自行深入理解。此处仅作笔记以备日后查阅，希望能对各位有所帮助。也欢迎大家支持本站。
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
