KMP 算法详解——从 next 数组的构建到回退的本质

KMP 是字符串匹配的经典算法，但每次背完过一阵就忘。这次我决定把它彻底拆开，用手算模拟的方式搞清楚每一步在干什么，特别是 next 数组构建中回退的逻辑。

一、KMP 解决什么问题

给定文本串 text 和模式串 pattern，在 text 中找到 pattern 第一次出现的位置。

暴力做法每次失配都从头比，时间复杂度 $O(n \times m)$。KMP 的核心思想是：失配时不回头，利用已匹配部分的内部结构直接跳到下一个可能的位置，时间复杂度 $O(n+m)$。

二、核心概念：最长相等前后缀

什么是前缀和后缀

对于字符串 "ABCAB"：

• 前缀（不含自身）：A、AB、ABC、ABCA
• 后缀（不含自身）：B、AB、CAB、BCAB

最长相等前后缀

前缀和后缀中，相等的、最长的那一对的长度。

上面的例子中，前缀 AB = 后缀 AB，所以最长相等前后缀长度为 2。

三、next 数组

定义

next[i] = 模式串 pattern[0..i] 这个子串的最长相等前后缀长度。

手算示例

模式串 "AABAAAB"：

next 数组的作用

匹配过程中，如果 pattern[j] 失配了，next[j-1] 告诉你：已匹配的部分里，有多长的前缀仍然有效，可以直接从那个位置继续比，不需要从头来。

四、next 数组的构建——逐步模拟

这是 KMP 最不好理解的部分。用具体例子一步步走。

两个指针的含义

• j：已匹配的前缀长度（同时也是前缀的末尾指针）
• i：当前正在计算 next[i] 的位置（从 1 开始）

三种情况

简单模拟："AABABC"（单次回退）

模式串：A A B A B C（下标 0~5）

i=1, j=0：A vs A → 相等，j=1，next[1]=1

next = [0, 1, ?, ?, ?, ?]

i=2, j=1：B vs A → 不等，j>0，回退 j=next[0]=0。再试：B vs A → 不等，j=0，next[2]=0

next = [0, 1, 0, ?, ?, ?]

i=3, j=0：A vs A → 相等，j=1，next[3]=1

next = [0, 1, 0, 1, ?, ?]

i=4, j=1：B vs A → 不等，j>0，回退 j=next[0]=0。再试：B vs A → 不等，j=0，next[4]=0

next = [0, 1, 0, 1, 0, ?]

i=5, j=0：C vs A → 不等，j=0，next[5]=0

最终：next = [0, 1, 0, 1, 0, 0]

多次回退模拟："ABABAC"（重点）

模式串：A B A B A C（下标 0~5）

先快速过简单的部分：

到这里：next = [0, 0, 1, 2, 3, ?]，j=3，i=5

重头戏来了：算 next[5]，i=5, j=3

j=3 意味着前面已有长度 3 的前后缀匹配好了。现在要看 C 能不能接在这个前缀后面：

第 1 次尝试：pattern[5]=C vs pattern[3]=B → 不等！

长度 3 的前缀 ABA 续不上。回退 j = next[2] = 1。

这一步的意思是：ABA 自身内部的最长前后缀是 A（长度1），所以还有长度 1 的匹配保着：

第 2 次尝试：pattern[5]=C vs pattern[1]=B → 还是不等！

再回退 j = next[0] = 0，前缀长度缩到 0。

第 3 次尝试：pattern[5]=C vs pattern[0]=A → 还是不等！

j 已经是 0，没法再退了 → next[5] = 0。

最终：next = [0, 0, 1, 2, 3, 0]

回退链：j=3（接不上）→ j=1（接不上）→ j=0（接不上）→ 放弃，记 0。

回退的本质

回退就像谈判：

1. 先拿最长的前缀去试：“3 个字符匹配好了，第 4 个能接上吗？”
2. 接不上 → “退一步，用次长的。1 个字符匹配好了，第 2 个能接上吗？”
3. 还不行 → “再退，0 个匹配。第 1 个能接上吗？”
4. 还不行 → “算了，这个位置就是 0。”

next[j-1] 就是帮你找到"次长匹配"的导航表，而这个表之前已经算好了，所以可以直接查。

为什么 i 不动？ 因为回退的意思是"换一个更短的前缀，在当前位置再试一次"。位置没变，只是候选的前缀变短了。

五、完整代码

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }

        // 构建 next 数组
        vector<int> next(m, 0);
        int j = 0;
        for (int i = 1; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = next[j - 1]; // 回退
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            next[i] = j;
        }

        // 匹配过程（逻辑和构建 next 完全一样）
        j = 0;
        for (int i = 0; i < n; i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
};

匹配过程和构建 next 数组的逻辑几乎一模一样，只是从"pattern自己和自己比"变成了"text和pattern比"：

失配时的回退方式完全相同：j = next[j-1]。

当 j == m（pattern全部匹配完）时，找到了匹配位置：i - m + 1。

六、常见易错点

1. 回退时 i 不动：这是最常见的bug。回退是"换更短的前缀在当前位置再试"，i 必须留在原地。

2. next数组下标：回退时查的是 next[j-1]（不是 next[j]），因为 j 代表的是长度，j-1 才是下标。

3. next[0] 永远是 0：单个字符没有前后缀可言。

4. for写法中 while 可能执行多次：一次 for 循环迭代中，内层 while 可能连续回退多次，但总体时间复杂度仍是 O(m)，因为 j 最多增加 m 次，所以最多也只能减少 m 次。

七、时间复杂度分析

• 构建 next 数组：O(m)
• KMP 匹配：O(n)
• 总计：O(n + m)

关键洞察：虽然有 while 嵌套在 for 里，但 j 每次 while 循环都在减小，而 j 的总增量不超过 m，所以 j 的总减量也不超过 m。因此内层 while 的总执行次数是 O(m)，不是 O(m²)。