KMP 算法：主串不后退，模式串精准跳

字符串匹配里最优雅的指针舞蹈——主串指针永不回头，模式串指针靠"预计算地图"精准回退。

引言

KMP（Knuth-Morris-Pratt）是字符串匹配算法里指针管理艺术的巅峰。

它的核心思想只有一句话：主串指针永不回退，模式串指针按预计算的跳转表做最小幅度回退。

暴力匹配让主串指针在 0~4 之间来回扫无数遍，像在迷宫里走错路非要回到大门口重走；KMP 则让主串指针像冷酷将军只管冲锋，模式串指针像精密参谋快速查地图后退到安全位置。

1. 暴力匹配的低效：指针反复横跳

主串 S = "AAAAAB"，模式串 P = "AAAAB"。

• i=0~3：四个 A 同步前进，i 和 j 一起加。
• i=4：S[4]='A' vs P[4]='B'，失配。
• 暴力做法：i 回退到 1，j 重置为 0，全部重来。

KMP 的使命：让 i 永远只前进，不后退。

2. KMP 的杀手锏：Next 数组

KMP 在匹配前先对模式串做"自我分析"，算出 next 数组。

next[j] 的含义：当 P[j] 与主串失配时，j 应该跳回到哪个位置？答案是 P[0...j-1] 中最长相等前缀后缀的长度。

构建 Next 数组的过程，本质上是模式串自己跟自己玩"双指针"匹配：

• 指针 i（后缀末端）从 1 开始，指针 j（前缀末端）从 0 开始。
• P[i] == P[j] → 前缀等于后缀，j++，next[i] = j，i++。
• 不等 → j 回退到 next[j-1]（利用已算好的跳转表）。

这就是"递归指针跳转"——用历史前缀指导未来后缀的位置。和二叉树递归、图遍历防环的 visited 标记，思想完全一致。

3. 匹配过程：主串 i 永不回头，模式串 j 精准回退

int KMP(char* S, char* P) {
    int i = 0, j = 0;
    while (i < lenS && j < lenP) {
        if (j == -1 || S[i] == P[j]) {
            i++; j++;        // 双指针同步前进
        } else {
            j = next[j];     // 失配！i 不动，j 按 next 跳
        }
    }
    return j == lenP ? i - j : -1;
}

经典案例：S = "BBC ABCDAB ABCDABCDABDE"，P = "ABCDABD"，next = [-1, 0, 0, 0, 0, 1, 2]。

当 i=10, j=6 时失配（空格 vs D）：

• 暴力做法：i 回退到 4，j=0，全重来。
• KMP 做法：i 不动，j = next[6] = 2，直接跳到 P[2]='C'。
• 仍然失配 → j = next[2] = 0 → j = -1 → i++ 推进。

全程 i 没后退过一步。这就是 KMP 优雅的核心。

4. 构建 Next 数组：指针的"自我递归"

void getNext(char* P, int* next) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < strlen(P) - 1) {
        if (j == -1 || P[i] == P[j]) {
            i++; j++;
            next[i] = j;
        } else {
            j = next[j];   // j 递归跳！
        }
    }
}

j = next[j] 这个操作，是不是很眼熟？

• 像哈希表扩容时的指针回退。
• 像图遍历遇到死路时的回溯。
• 像二叉树递归的"剪枝"。

普适真理：当"继承关系"断裂时，不必从头再来，找到当前状态的"次长前缀"继续尝试。这是 KMP 灵魂中的灵魂。

5. 暴力、KMP、Sunday 的指针哲学对比

算法	主串 i	模式串 j	哲学
暴力匹配	回退（后悔）	归零（全部放弃）	犯错就重来，毫无记忆
KMP	永不回退（坚定）	跳转（部分保留）	利用前缀记忆，最小化损失
Sunday	跳跃（看下一字符）	重置（视情况偏移）	预判未来，跳过不可能

KMP 的经典之处在于：用一张预计算的表，把模式串内部的对称性（前缀=后缀）变成指针跳跃的依据。它没把数据存成树或图，而是存成了**“失败时的逃生路线图”**。

6. 总结：指针跳跃的"信息守恒"

整个指针系列的演进：

1. 链表：指针决定节点的生死连接。
2. 二叉树：指针决定递归压栈的深度。
3. 堆：指针是下标的算术。
4. 哈希表：指针是数组槽位到链表的挂载。
5. 图：指针是遍历时的标记与扩散。
6. KMP（字符串）：指针是失败时的"不完全回退"。

KMP 告诉我们：指针的每一次移动，都代表信息的流动和状态的转移。

• i 不后退，是因为之前的比较信息已被 j 和 next 数组完全消化。
• j 的跳跃，是因为 next 数组保证了跳过去之后，前面的字符一定和主串当前位置前的字符匹配。

下次在编辑器里按 Ctrl+F 查找关键词时，请记得——底层的 KMP 正驾驭着两个指针，一个像不知疲倦的飞矢，一个像精密计算的锁芯，在字符的海洋中精准定位。

---