本文共 2347 字，大约阅读时间需要 7 分钟。
KMP（Knuth-Morris-Pratt）算法是由 D.E.Knuth、J.E.Morris 和 V.R.Pratt 三位研 comida 将其共同提出的，广泛应用于字符串匹配问题。相较于暴力算法（Brute-Force），KMP 算法在效果上有了显著提升，通过减少主串指针的回溯操作，提高了效率。尽管其时间复杂度仍为 O(n²)，但通过引入前缀和后缀匹配的优化，使其在长文本匹配中更具实用性。
KMP 算法的核心在于利用目标字符串的前缀和后缀之间的重叠性质，从而减少不必要的对比操作。其关键步骤包括：
求解最大前缀与后缀匹配长度：
对于给定字符串 s，找到最长的前缀和后缀相同的子字符串。例如，对于字符串 "ababab"，最长的前缀和后缀匹配长度为 4（"abab"）。利用前缀和后缀匹配减少计算：
通过预先计算前缀和后缀匹配长度，可以在匹配过程中快速定位下一个可能的匹配点，避免逐字符比较。在 KMP 算法中，需要通过以下步骤计算最大前缀和后缀匹配长度：
定义前缀和后缀：
找到最大前缀后缀匹配：
例如，对于字符串 "bbbabbb"，最大前缀后缀匹配长度为 3（"bbb"）。通过逐字符比较，确定相同前缀和后缀的最长长度。预处理预存匹配长度：
l，其中 l[i] 表示前 i 个字符的最大前缀后缀匹配长度。KMP 算法在这一步骤中采用类似动态规划的思想，通过递归关系计算 \l[i+1]：
l[l[i]]）。通过这种方式，可以快速定位下一个可能的匹配起点。
传统的暴力算法需要逐字符比较，导致时间复杂度为 O(n²)。KMP 算法的改进部分如下：
利用预处理数组 l：
l 快速定位下一个可能的匹配起点。这避免了重复比较字符，减少了时间开销。KMP 算法的核心逻辑：
function KMP(text, pattern): n = len(pattern) lps = [0] * n for i in 1:n-1: k = lps[i-1] while k > 0 and pattern[i] != pattern[k]: k = lps[k-1] if pattern[i] == pattern[k]: lps[i] = k + 1 else: lps[i] = 0 j = 0 # pattern index for i in 0: len(text): if pattern[j] == text[i]: j += 1 if j == n: return i - n + 1 # matched at i - n + 1 elif i < n-1: j = lps[j-1] return -1
以下是 KMP 算法的实现代码，可供参考：
def compute_lps_array(pattern): """计算KMP失败函数(长前缀长后缀)数组""" n = len(pattern) lps = [0] * n for i in range(1, n): j = lps[i-1] while j > 0 and pattern[i] != pattern[j]: j = lps[j-1] if pattern[i] == pattern[j]: lps[i] = j + 1 else: lps[i] = 0 return lpsdef kmp_search(text, pattern): """执行KMP算法，全局匹配""" n = len(pattern) if n == 0: return -1 lps = compute_lps_array(pattern) j = 0 # 指针跟踪匹配位置 for i in range(len(text)): if pattern[j] == text[i]: j += 1 if j == n: return i - n + 1 # 匹配在第i - n + 1位置发现 elif i < n - 1: # 未完全匹配，退回一个位置 j = lps[j-1] return -1 # 未能找到匹配
通过以上分析，我们可以清晰地看出 KMP 算法如何通过预处理和动态规划的思想，将暴力算法的时间复杂度从 O(n²) 降低到 O(n)。在实际应用中，KMP 算法广泛用于文本检索、模式识别等场景，是解决字符串匹配问题的高效解决方案。
转载地址：http://vwcmz.baihongyu.com/