KMP 算法是什么算法？

KMP 算法（Knuth-Morris-Pratt 算法）是一种用于 字符串匹配（子串搜索） 的经典算法。它的核心目的是在文本中快速找到模式串（pattern）出现的位置，避免无谓的回溯，提高效率。

1. 算法问题

给定两个字符串：

• 文本串 T（长度为 n）

• 模式串 P（长度为 m）

要求：找出 P 在 T 中的所有出现位置。

2. 传统暴力匹配问题

暴力方法：从文本第一个字符开始，每次尝试匹配模式串，如果不匹配就回溯文本指针，时间复杂度 O(n*m)，效率低。

3. KMP 算法核心思想

• 利用模式串自身信息，在匹配失败时尽量 跳过不必要的比较。

• 构建 部分匹配表（next 数组）：

• next[i] 表示模式串前 i 个字符的最长 相等的真前后缀长度。

• 当匹配失败时，模式串向右移动的步数由 next 决定，而不是回溯文本指针。

• 时间复杂度降为 O(n + m)。

4. 算法步骤

1. 构建 next 数组：

• 对模式串本身进行分析，记录每个位置前缀和后缀的匹配情况。

2. 文本匹配：

• text[i] == pattern[j] → 同时移动 i 和 j

• text[i] != pattern[j] → 模式串跳到 j = next[j-1]，文本指针 i 不回溯

• 使用两个指针 i（文本）、j（模式串）匹配：

3. 找到匹配：

• 当 j == m 时表示模式串完全匹配成功，记录匹配位置 i - m + 1。

5. KMP 优点

• 高效：避免重复比较，时间复杂度 O(n + m)

• 稳定：适合长文本和模式匹配

• 广泛应用：

• 文本搜索（搜索引擎、编辑器）

• DNA 序列匹配

• 字符串压缩或模式检测

• 某些动态规划优化（字符串类问题）

6. 核心公式

如果匹配失败：

j = next[j-1]

而不是把 j 置为 0 或让 i 回溯。

可以用一个小图示理解：

text:    A B A B D A B A C D A B A B C A B A B
pattern:   A B A B C A B A B
匹配失败时，模式串根据 next 数组跳过重复匹配部分