KMP 字符串匹配算法的原理是什么？（实现 strStr，LeetCode 28）

简化版

KMP 用于在主串中查找模式串首次出现的位置，把朴素匹配的 O(nm) 优化到 O(n + m)。核心是：匹配失败时不回退主串指针，而是利用模式串自身的「最长相等前后缀」信息（next/前缀表），让模式串向右滑动一段合适距离，跳过不可能匹配的位置。关键就是预处理出模式串的 next 数组（next[i] = 模式串 [0..i] 的最长相等真前后缀长度），匹配时失配就用它决定模式串指针跳到哪。

详细版

int strStr(String haystack, String needle) {
    if (needle.isEmpty()) return 0;
    int[] next = buildNext(needle);
    int j = 0;                                  // 模式串指针
    for (int i = 0; i < haystack.length(); i++) {   // 主串指针不回退
        while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
            j = next[j - 1];                    // 失配：模式串回退到 next
        }
        if (haystack.charAt(i) == needle.charAt(j)) j++;   // 匹配：j 前进
        if (j == needle.length()) return i - j + 1;        // 完全匹配，返回起点
    }
    return -1;
}

// 构建 next 数组（前缀表）：next[i] = needle[0..i] 的最长相等真前后缀长度
int[] buildNext(String p) {
    int[] next = new int[p.length()];
    int j = 0;                                  // 当前最长相等前后缀长度
    for (int i = 1; i < p.length(); i++) {
        while (j > 0 && p.charAt(i) != p.charAt(j)) {
            j = next[j - 1];                    // 回退
        }
        if (p.charAt(i) == p.charAt(j)) j++;
        next[i] = j;
    }
    return next;
}

朴素匹配 O(nm)：每次失配主串指针回退，重复比较。
KMP O(n+m)：主串指针 i 只增不减，失配时靠 next 让模式串「聪明地」滑动。
next 数组是灵魂：记录模式串每个前缀的「最长相等前后缀」，失配时直接跳到该位置继续比。

完整版教学

一、朴素匹配的浪费在哪

朴素做法：主串每个位置都尝试对齐模式串从头比。一旦某字符失配，主串指针退回到本次起点的下一个，模式串也从头开始——大量重复比较，最坏 O(nm)。

浪费的本质：失配时，我们其实已经知道了「失配前那一段主串字符」的内容（它们等于模式串已匹配的前缀），却把这些信息丢掉、从头再比。KMP 就是要复用这段已知信息，不回退主串。

二、KMP 的核心思想：失配后模式串「滑动」而非归零

假设模式串已经匹配到第 j 位，第 j+1 位失配。此时主串已匹配的那段 = 模式串的前缀 p[0..j-1]。KMP 问：模式串能不能不从头开始，而是滑动到某个位置，让它的一个较短前缀直接对齐上已匹配的这段的后缀？

能——如果模式串的前缀 p[0..j-1] 有一个「最长相等真前后缀」（前缀和后缀相同的最长长度 k），那么滑动后让 p[0..k-1] 对齐主串已匹配段的末尾 k 个字符（它们相等，不用再比），模式串指针直接跳到 k 继续比 —— 主串指针纹丝不动。这个 k 就是 next[j-1]。

三、next 数组（前缀表）到底是什么

next[i]（也叫前缀表 π[i]）定义为：子串 p[0..i] 的「最长相等真前后缀」的长度。

「真前后缀」= 不包含自身的前缀和后缀。
例：p = "aabaa"，next = [0,1,0,1,2]。最后一位 next[4]=2，因为 "aabaa" 的前缀 "aa" 和后缀 "aa" 相等、长度 2。

它的意义：当匹配到位置 i 后失配，模式串可以直接滑到「让长度为 next[i-1] 的前缀对齐」的位置，因为这段前后缀相等，前缀已经天然匹配上了主串对应部分。

四、next 数组怎么构建（自我匹配）

构建 next 本身就是模式串和自己做 KMP 匹配：用两个指针，i 遍历、j 表示当前最长相等前后缀长度。

若 p[i] == p[j]：前后缀能延长，j++，next[i] = j。
若不等且 j > 0：j = next[j-1] 回退（找更短的相等前后缀再试）——和匹配时失配回退是同一套逻辑。
若不等且 j == 0：next[i] = 0。

这段代码和主匹配循环几乎一模一样，理解了一个就理解了另一个。构建是 O(m)。

五、复杂度与为什么是线性

匹配阶段 O(n)：主串指针 i 从头到尾只增不减。虽然内层 while 会让 j 回退，但 j 每次匹配才 +1、回退总量不超过 +1 的总量，均摊 O(n)。
构建 next O(m)：同理均摊线性。
合计 O(n + m)，远优于朴素 O(nm)。

易错点：next 数组的定义和下标偏移（有人用「next 右移一位、首位 -1」的版本，也有「前缀表不右移」的版本，本文用后者）。两种实现都对，但失配回退时的 j = next[j-1] 要和定义匹配一致，混用会错。

六、用模式串 ABABAC 推导前缀表

前缀表 lps[i] 表示模式串 pattern[0..i] 的最长相等真前后缀长度。构建时 j 同时代表候选前缀长度和下一个待比较位置；失配后令 j=lps[j-1]，是在尝试更短但仍可能成立的边界，而不是凭空跳跃。

pattern: A B A B A C
index:   0 1 2 3 4 5
lps:     0 0 1 2 3 0
匹配到 ABABA 后若下一字符失配
j 从 5 回退到 lps[4]=3，再尝试长度 3 的边界
仍失配则继续 j=lps[2]=1，直到匹配或归零
文本指针 i 不后退

校验维度	本题必须保持的结论
循环/递推不变量	搜索时 `pattern[0..j-1]` 已与文本当前位置之前的 j 个字符匹配；回退只缩短这个已知匹配边界。
边界条件	空模式通常定义匹配位置为 0；next 与 lps 有多种下标约定，公式不能混搭。
复杂度与代价	文本指针只前进，模式指针回退总次数受前进次数约束，构建和匹配合计 O(m+n)。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

字符串题首先要固定“处理的是字符、UTF-16 代码单元还是 Unicode 码点”，再讨论下标与窗口。本题应先复述这条不变量：搜索时 pattern[0..j-1] 已与文本当前位置之前的 j 个字符匹配；回退只缩短这个已知匹配边界。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“pattern: A B A B A C”开始手推，最后应得到“文本指针 i 不后退”。
边界复核：空模式通常定义匹配位置为 0；next 与 lps 有多种下标约定，公式不能混搭。
代价复核：文本指针只前进，模式指针回退总次数受前进次数约束，构建和匹配合计 O(m+n)。
用空串、单字符、全相同字符和首尾命中检查下标边界。
涉及窗口或双指针时，明确区间是闭区间还是左闭右开，并在移动后再判断长度。
涉及计数数组时，先确认题目字符集；超出小写英文字母就不能硬套 26 个桶。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“搜索时 pattern[0..j-1] 已与文本当前位置之前的 j 个字符匹配；回退只缩短这个已知匹配边界。”这条正确性主线不能省。

八、常见误区与追问

误区：KMP 失配后文本指针也要回退。 它复用已匹配前后缀，文本指针保持当前位置，只调整模式指针。
误区：lps 记录的是任意重复子串长度。 它必须同时是真前缀和后缀，并且取最大长度。
误区：next[j] 与 lps[j-1] 可以随意互换。 不同教程的数组语义和下标偏移不同，混用会产生越界或漏匹配。
追问：为什么回退不会漏掉可能匹配？ 比最长边界更长的候选已经因当前失配被否定，剩余候选必嵌套在其边界链中。
追问：KMP 的最坏时间为何不是 O(nm)？ 每次回退都缩短 j，且 i 不后退；j 的总增长与总回退均为线性。
追问：如何用 KMP 判断重复子串？ 若 n-lps[n-1] 能整除 n 且 lps 非零，该差值就是最短周期。

九、加强记忆

KMP = 失配时主串指针不回退，靠模式串的 next（前缀表）聪明滑动，把 O(nm) 降到 O(n+m)。next[i] = 子串 p[0..i] 的最长相等真前后缀长度；匹配失配时 j = next[j-1]，让模式串滑到「相等前缀已对齐」的位置继续比。构建 next 就是模式串和自己做 KMP（同一套失配回退逻辑）。核心洞察：已匹配的那段主串等于模式串前缀，其「最长相等前后缀」告诉我们能少比多少。均摊线性因主串指针只增不减。

简化版

详细版