kmp算法的优势体现在避免文本串指针回溯，提升匹配效率。1. 与朴素匹配相比，kmp通过预处理模式串构建lps数组，在匹配失败时仅移动模式串指针，利用已知的最长公共前后缀信息实现跳跃式匹配，避免重复比较，时间复杂度由o(m*n)降至o(m+n)；2. lps数组是kmp核心，记录模式串各子串的最长公共前后缀长度，指导模式串指针回溯位置，减少无效操作；3. 在处理长文本及重复结构明显的模式串时，如基因序列或日志分析，kmp效率显著优于朴素算法；4. 然而kmp并非始终最优，模式串极短、无重复结构时，或需多模式匹配等场景下，boyer-moore、rabin-karp等算法可能更优。
KMP算法，全称Knuth-Morris-Pratt算法，是一种在文本串中查找模式串的线性时间复杂度的字符串匹配算法。它通过预处理模式串，构建一个“部分匹配表”（也称LPS数组，最长公共前后缀数组），从而在匹配失败时，避免文本串指针的回溯，只移动模式串指针，显著提升了匹配效率。这与朴素匹配中频繁的文本串回溯形成了鲜明对比，尤其在处理长文本和重复性高的模式串时，其优势更为明显。
实现KMP算法，核心在于两步：构建LPS数组和基于LPS数组进行匹配。我个人觉得，理解LPS数组的构建是整个算法最精妙也最容易让人卡壳的地方，它就像模式串给自己写的一本“自救手册”。
1. 构建LPS（最长公共前后缀）数组
立即学习“Python免费学习笔记（深入）”；
LPS数组的lps[i]表示模式串pattern[0...i]的最长公共前后缀的长度。这个“公共前后缀”指的是既是前缀又是后缀的子串。例如，对于模式串"ABABCABAB"，
[0, 0, 1, 2, 0, 1, 2, 3, 4]。构建LPS数组的过程有点像KMP匹配的简化版，模式串自己跟自己匹配。我们用两个指针，length表示当前已匹配的最长公共前后缀的长度，i遍历模式串的每一个字符。
def compute_lps_array(pattern):
"""
计算模式串的LPS（最长公共前后缀）数组。
LPS数组的lps[i]表示pattern[0...i]的最长公共前后缀的长度。
"""
m = len(pattern)
lps = [0] * m
length = 0 # 当前已匹配的最长公共前后缀的长度
i = 1 # 从模式串的第二个字符开始遍历
while i < m:
if pattern[i] == pattern[length]:
# 如果当前字符与length指向的字符匹配，说明可以延长公共前后缀
length += 1
lps[i] = length
i += 1
else:
# 如果不匹配
if length != 0:
# 如果length不为0，说明之前有匹配，回溯到上一个已知最长公共前后缀的长度
# 这一步是理解的关键：我们不是从头再来，而是利用了LPS数组中记录的信息
length = lps[length - 1]
else:
# 如果length为0，说明没有公共前后缀，当前字符的LPS值为0
lps[i] = 0
i += 1
return lps
2. KMP匹配算法
有了LPS数组，KMP匹配就变得直接了。我们用两个指针，i指向文本串，j指向模式串。
def kmp_search(text, pattern):
"""
使用KMP算法在文本串中查找模式串的所有匹配位置。
"""
n = len(text)
m = len(pattern)
if m == 0:
return [] # 模式串为空，认为在任何地方都匹配
if n == 0:
return [] # 文本串为空，不可能有匹配
lps = compute_lps_array(pattern)
matches = [] # 存储匹配的起始索引
i = 0 # 文本串指针
j = 0 # 模式串指针
while i < n:
if pattern[j] == text[i]:
# 字符匹配，两个指针都向前移动
i += 1
j += 1
if j == m:
# 模式串完全匹配，记录当前匹配的起始位置
# 并根据LPS数组，将模式串指针j回溯，继续查找下一个可能的匹配
matches.append(i - j)
j = lps[j - 1] # 这一步是KMP的精髓，避免了文本串i的回溯
elif i < n and pattern[j] != text[i]:
# 字符不匹配
if j != 0:
# 如果模式串指针j不为0，说明之前有部分匹配
# 根据LPS数组，将模式串指针j回溯到上一个已知最长公共前后缀的长度
# 文本串指针i保持不变
j = lps[j - 1]
else:
# 如果模式串指针j为0，说明第一个字符就不匹配
# 文本串指针i向前移动一位
i += 1
return matches
示例调用：
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
# lps_array = compute_lps_array(pattern)
# print(f"LPS array for '{pattern}': {lps_array}") # 输出: [0, 0, 1, 2, 0, 1, 2, 3, 4]
# matches = kmp_search(text, pattern)
# print(f"Pattern found at indices: {matches}") # 输出: [10]整个过程，从LPS的构建到最终的匹配，都巧妙地利用了模式串自身的结构信息，避免了那些重复且无谓的比较。我常觉得，KMP算法的优雅之处就在于它对“已知信息”的极致利用，一旦发现不匹配，它不是盲目地从头再来，而是“聪明地”跳到下一个可能的匹配点，那种感觉就像在玩一个复杂的跳棋游戏。
谈到KMP算法与朴素匹配的对比，这就像是在讨论是选择蛮力还是智取。朴素匹配（或称暴力匹配）简单粗暴，它从文本串的每个位置开始，尝试将模式串逐个字符地进行比较。一旦发现不匹配，文本串的指针就回溯到下一个可能的起始位置，模式串的指针则回到开头。这种方式在最坏情况下，比如文本串是"AAAAAAB"而模式串是"AAB"时，会导致大量的重复比较，时间复杂度会达到O(m*n)，其中m是模式串长度，n是文本串长度。想想看，每当快要匹配成功时，就差那么一个字符，然后就得从头再来，效率自然低下。
KMP的优势，我认为主要体现在它对“回溯”的处理上。它彻底消除了文本串指针的无谓回溯。当KMP算法发现一个不匹配时，它不会简单地把模式串往右移动一位，然后文本串指针也跟着回溯。相反，它会利用之前计算好的LPS数组，知道模式串当前已匹配的部分中，有哪些前缀也是它的后缀。这样，模式串可以直接“跳跃”到下一个可能匹配的位置，而文本串的指针则保持不动或仅仅向前移动。这种“聪明”的跳跃，使得KMP算法的时间复杂度始终保持在O(m+n)的线性级别。
举个例子，文本串"AAAAAAAAB" 模式串"AAAB"。 朴素匹配：
KMP：
LPS数组，或者说“部分匹配表”，是KMP算法的灵魂。我个人觉得，理解它，KMP就理解了一大半。它不是一个简单的查找表，而是一个模式串“自省”的结果。lps[i]这个值，它告诉我们的是：在模式串的pattern[0...i]这个子串中，最长的一个真前缀（不包括整个字符串本身）同时也是它的真后缀（不包括整个字符串本身）的长度是多少。
我们来用一个具体的例子走一遍构建过程，这比干巴巴的定义要清晰得多。假设模式串是 pattern = "ABABCABAB"。
它的长度 m = 9。我们初始化 lps = [0, 0, 0, 0, 0, 0, 0, 0, 0]。
length = 0 (表示当前已匹配的最长公共前后缀长度)
i = 1 (从模式串的第二个字符开始遍历)
i = 1 (字符 'B'): pattern[1] ('B') 和 pattern[length] (pattern[0]，即 'A') 不匹配。length 是0，所以 lps[1] 设为0，i 递增到2。
lps = [0, 0, 0, 0, 0, 0, 0, 0, 0]
i = 2 (字符 'A'): pattern[2] ('A') 和 pattern[length] (pattern[0]，即 'A') 匹配！
length 递增到1。lps[2] 设为 length (1)。i 递增到3。
lps = [0, 0, 1, 0, 0, 0, 0, 0, 0] (对于"ABA"，最长公共前后缀是"A"，长度为1)
i = 3 (字符 'B'): pattern[3] ('B') 和 pattern[length] (pattern[1]，即 'B') 匹配！
length 递增到2。lps[3] 设为 length (2)。i 递增到4。
lps = [0, 0, 1, 2, 0, 0, 0, 0, 0] (对于"ABAB"，最长公共前后缀是"AB"，长度为2)
i = 4 (字符 'C'): pattern[4] ('C') 和 pattern[length] (pattern[2]，即 'A') 不匹配。
length 不为0 (是2)。所以 length 回溯到 lps[length - 1]，即 lps[1] (0)。
lps = [0, 0, 1, 2, 0, 0, 0, 0, 0] (此时 length 变为0)
i = 4 (字符 'C'): pattern[4] ('C') 和 pattern[length] (pattern[0]，即 'A') 再次不匹配。
length 此时为0。所以 lps[4] 设为0。i 递增到5。
lps = [0, 0, 1, 2, 0, 0, 0, 0, 0]
i = 5 (字符 'A'): pattern[5] ('A') 和 pattern[length] (pattern[0]，即 'A') 匹配！
length 递增到1。lps[5] 设为 length (1)。i 递增到6。
lps = [0, 0, 1, 2, 0, 1, 0, 0, 0]
i = 6 (字符 'B'): pattern[6] ('B') 和 pattern[length] (pattern[1]，即 'B') 匹配！
length 递增到2。lps[6] 设为 length (2)。i 递增到7。
lps = [0, 0, 1, 2, 0, 1, 2, 0, 0]
i = 7 (字符 'A'): pattern[7] ('A') 和 pattern[length] (pattern[2]，即 'A') 匹配！
length 递增到3。lps[7] 设为 length (3)。i 递增到8。
lps = [0, 0, 1, 2, 0, 1, 2, 3, 0]
i = 8 (字符 'B'): pattern[8] ('B') 和 pattern[length] (pattern[3]，即 'B') 匹配！
length 递增到4。lps[8] 设为 length (4)。i 递增到9。
lps = [0, 0, 1, 2, 0, 1, 2, 3, 4]
至此，LPS数组构建完毕：[0, 0, 1, 2, 0, 1, 2, 3, 4]。
LPS数组的意义在于，当模式串的j位置与文本串的i位置不匹配时，我们知道pattern[0...j-1]已经匹配成功了。如果j-1这个前缀有长度为k = lps[j-1]的最长公共前后缀，那么我们就可以直接把模式串向右移动j-k个位置，让pattern[k]对齐文本串的i位置，因为pattern[0...k-1]和pattern[j-k...j-1]是相同的，我们不需要重新比较它们。LPS数组就是这种“聪明跳跃”的依据，它避免了从头开始的无谓检查，这正是KMP高效的秘密。它就像模式串给自己预设的“备用方案”，在遇到挫折时，能迅速找到下一个最有可能成功的起点。
这是一个很好的问题，因为在算法的世界里，很少有“放之四海而皆准”的银弹。KMP算法无疑非常优秀，尤其是在其设计的特定场景下——即文本串和模式串都可能很长，并且模式串内部存在重复结构时，它的线性时间复杂度O(m+n)是巨大的优势。比如，在生物信息学中进行基因序列比对，或者在大型文本编辑器中实现“查找替换”功能，KMP确实能大放异彩。
然而，KMP并非总是最优解。它的“最优”是针对特定约束条件而言的。
所以，在选择字符串匹配算法时，我通常会考虑以下几点：
没有哪个算法是万能的，KMP在它擅长的领域表现卓越，但在其他场景，了解并选择Boyer-Moore、Rabin-Karp甚至更高级的数据结构，才是真正体现“优化”思维的地方。
以上就是Python如何实现KMP算法？字符串匹配优化的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
广告Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
725
收藏
