KMP（Knuth-Morris-Pratt）字符串匹配算法详解

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，在 O(n + m) 的时间复杂度内完成模式匹配。本文将详细介绍 KMP 算法的原理、前缀函数（Next 数组）的计算方法，并通过示例演示其工作原理。 1. KMP 算法简介 KMP 算法的主要思想是避免重复比较。当发生不匹配时，不需要回溯主串，而是利用模式串的部分匹配信息来进行跳跃，从而提高匹配效率。 2. 前缀函数（Next 数组） KMP 依赖于 Next 数组 ，用于记录模式串自身的匹配信息，帮助模式串在匹配失败时快速跳转。 2.1 计算 Next 数组 Next 数组的计算逻辑如下： 1. 设 next[i] 表示 pattern[0:i] 的最大相同前后缀长度。 2. 递推计算 next[i]，当 pattern[i] 与前一个最长相同前后缀字符匹配时，next[i] = next[i-1] + 1。 3. 否则，尝试匹配较短的前后缀，直到 next[i] = 0。 3. KMP 匹配过程 1. 遍历主串 text，依次匹配模式串 pattern。 2. 如果 text[i] == pattern[j]，继续匹配下一个字符。 3. 如果 text[i] != pattern[j]，根据 next[j] 进行跳转，而不是回溯。 4. KMP 匹配示例 假设 text = "ABABABABCABABABCABABABC"，pattern = "ABABC"，构造 Next 数组如下： | i | 0 | 1 | 2 | 3 | 4 | | ---- | - | - | - | - | - | | 字符 | A | B | A | B | C | | Next | 0 | 0 | 1 | 2 | 0 | 当匹配到 C 时，不匹配 text 的字符 A，但由于 next[4] = 0，模式串跳转到 pattern[0] 继续匹配。 5. 复杂度分析 计算 Next 数组的时间复杂度为 O(m) 。 匹配过程最多 O(n) 次迭代，因此总时间复杂度为 O(n + m) ，远优于暴力匹配的 O(n × m)。 6. 总结 KMP 算法通过 Next 数组预处理模式串，避免了重复匹配，提高了字符串匹配的效率。在实际应用中，如文本搜索、DNA 序列匹配、日志分析等场景，KMP 都是一个高效的选择。