### 关于Knuth-Morris-Pratt (KMP) 算法的Python实现 KMP算法的核心在于构建部分匹配表（也称为`lps`数组），该表记录了模式串的部分匹配前缀和后缀的信息。利用这个表格可以跳过一些不必要的比较操作，从而提高字符串匹配的速度。 以下是基于上述理论的一个完整的Python实现： #### 部分匹配表（LPS Array）计算函数 此函数用于生成模式串的部分匹配表。 ```python def compute_lps_array(pattern): lps = [0] * len(pattern) # 初始化 LPS 数组 length = 0 # 当前最长公共前后缀长度 i = 1 # 从第二个字符开始填充 LPS 数组 while i < len(pattern): # 构建 LPS 表的过程 if pattern[i] == pattern[length]: length += 1 lps[i] = length i += 1 else: if length != 0: length = lps[length - 1] else: lps[i] = 0 i += 1 return lps ``` #### 主匹配函数 此函数实现了在文本中寻找模式串的功能。 ```python def kmp_search(text, pattern): m = len(pattern) n = len(text) lps = compute_lps_array(pattern) # 计算部分匹配表 i = j = 0 # 文本索引i 和 模式串索引j 的初始值均为0 result_indices = [] # 存储找到的所有起始位置 while i < n: # 开始逐字符匹配过程 if text[i] == pattern[j]: i += 1 j += 1 if j == m: # 如果完全匹配，则保存结果并重置状态 result_indices.append(i - j) j = lps[j - 1] elif i < n and text[i] != pattern[j]: # 不匹配的情况 if j != 0: j = lps[j - 1] else: i += 1 return result_indices ``` #### 使用示例 下面是一个简单的例子来展示如何调用这些方法： ```python if __name__ == "__main__": text = "ABABCABABD" pattern = "ABAB" indices = kmp_search(text, pattern) if not indices: print("Pattern not found.") else: print(f"Pattern found at index(es): {indices}") ``` 以上代码展示了如何使用KMP算法高效地完成字符串匹配任务][^[^23]。 ### 性能分析 相比于朴素的暴力搜索方式，KMP算法能够显著减少重复比较的操作数。它的平均时间和最坏情况下的时间复杂度都是线性的 \(O(n)\)[^4]。