讲解KMP算法

KMP算法（Knuth-Morris-Pratt 算法）是一种高效的字符串匹配算法，用于在一个主串 S 中查找模式串 P 的所有出现位置。相较于暴力匹配算法，KMP通过利用已经部分匹配的信息避免了不必要的回溯操作，因此效率更高。 ### KMP的核心思想： 1. **前缀表 (Partial Match Table)**： 构造一个“前缀表”数组`next[]`，它记录了模式串P的每个位置处最长相等前后缀长度。例如，在模式串 "ABABC" 中，“ABA”的前缀 "A" 和后缀 "A" 相同，所以它的值为 1；而对 “BAB”，没有相同的非空前缀和后缀，则其值为0。 2. **匹配过程**： 使用该前缀表指导主串S与模式串P之间的匹配流程。如果发生失配时，并不需要将指针完全退回到上一次开始的位置加一的地方重新比较，而是基于已知信息移动到更优的位置继续比对，从而减少冗余计算量。 #### 具体步骤说明： ##### 第一步 - 建立 next 数组 ```python def build_next(pattern): n = len(pattern) next_array = [0] * n # 初始化next数组全零 j = 0 # 指向pattern前面字符索引 for i in range(1, n): # 遍历从第1个元素到最后一位构建next[i] while j > 0 and pattern[j] != pattern[i]: j = next_array[j - 1] if pattern[j] == pattern[i]: j += 1 next_array[i] = j # 更新当前i位置对应的最长公共前后缀长度 return next_array ``` ##### 第二步 - 进行KMP搜索 ```python def kmp_search(text, pattern): m = len(text) # 主串长度 n = len(pattern) # 子串长度 if n == 0: # 边界条件处理 return [] next_arr = build_next(pattern) matches = [] # 结果列表存储起始点坐标 q = 0 # 表示模式串现在匹配到了哪位 for p in range(m): while q > 0 and text[p] != pattern[q]: q = next_arr[q - 1] if text[p] == pattern[q]: q += 1 if q == n: # 如果成功找到完整子串则添加结果并重置q matches.append(p - n + 1) q = next_arr[q - 1] return matches ``` 上述代码实现了完整的KMP算法，包括构造`next`数组以及实际进行字符串搜寻的过程。