KMP 算法：前缀表与文本匹配

KMP 是字符串专题里公认的硬骨头。本文不要求背代码，而是回答三个问题：朴素匹配慢在哪？前缀表到底是什么、怎么手推？失配时为什么那样回退？

朴素匹配为什么慢（28 strStr）

在文本串 haystack 中找模式串 needle 第一次出现的位置，最直接的做法是从文本串每个下标开始逐位对比：

文本：a a b a a b a a f
模式：a a b a a f
              ↑ 前 5 位匹配成功，第 6 位 f ≠ b，失配
文本：a a b a a b a a f
模式：  a a b a a f
        ↑ 模式右移一位，又从头比起——前面比过的信息全部作废

问题在于：每次失配后文本串指针都要往回退，最坏时间复杂度 O(n×m)。

KMP 的思路正好相反：文本串指针永不回退，失配时让模式串"聪明地滑动"——滑动多少，取决于已匹配部分自身携带的信息。

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

先约定两个定义（都是"真"前缀/后缀，不含串本身）：

• 前缀：从下标 0 开始、不包含末尾字符的所有连续子串。
• 后缀：以末尾字符结尾、不包含开头字符的所有连续子串。

前缀表 next[i] 记录：子串 pattern[0..i] 的最长相等前后缀的长度。

手工推导 "aabaaf" 的前缀表

一行一行看"以下标 i 结尾的子串"：

得到 next = [0, 1, 0, 1, 2, 0]。

两个细节：长度为 1 的子串没有真前后缀，next[0] 恒为 0；"aabaa" 的答案是 2 不是 1，因为 "aa" 同时是它的前缀和后缀。

前缀表如何指导回退

用 文本 "aabaabaaf" 匹配 模式 "aabaaf" 演示：

文本：a a b a a b a a f
模式：a a b a a f
              ↑ 下标 5 处，模式[5]='f' 与文本[5]='b' 失配，此时 j=5
              查表：next[j-1] = next[4] = 2

已匹配部分 "aabaa" 的最长相等前后缀是 "aa"。这说明文本串中失配位置之前的 2 个字符，恰好等于模式串开头 2 个字符，于是模式串直接滑到下标 2 继续比，前面的字符不用重比：

文本：a a b a a b a a f
模式：        a a b a a f
              ↑ 从模式[2]='b' 与文本[5]='b' 接着匹配

一句话总结：失配时执行 j = next[j-1]，让 j 跳到"已匹配部分的最长相等前后缀长度"处。j 在匹配全程只增不减，均摊下来文本串每个字符只被看常数次，总复杂度 O(n+m)，而不是 O(n×m)。

Java 实现

构建 next 数组

构造 next 的过程本质是"模式串自己和自己做匹配"：

private int[] buildNext(String pattern) {
    int[] next = new int[pattern.length()];
    next[0] = 0;                      // 长度为 1 的子串没有真前后缀
    int j = 0;                        // j：前缀末尾下标，同时 = 当前最长相等前后缀长度
    for (int i = 1; i < pattern.length(); i++) {  // i：后缀末尾下标
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];          // 失配：j 连续回退，直到能接上或退到 0
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;                      // 对上了：相等前后缀长度加一
        }
        next[i] = j;                  // 记录 pattern[0..i] 的答案
    }
    return next;
}

两个角色要分清：i 负责向后扩展后缀，j 代表"当前已匹配上的前缀长度"。i 从 1 开始只增不减，j 用 while 连续回退。用 "aabaaf" 逐行跑一遍，结果应与上面手推表格完全一致。

strStr 主流程（LeetCode 28）

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0;
        int[] next = buildNext(needle);
        int j = 0;                       // needle 中已匹配的字符数
        for (int i = 0; i < haystack.length(); i++) {  // i：文本串指针，永不回退
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];         // 失配：模式串"滑动"
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {  // 模式串全部匹配完成
                return i - needle.length() + 1;
            }
        }
        return -1;
    }
 
    private int[] buildNext(String pattern) { /* 同上 */ }
}

• 时间复杂度：构建 next O(m) + 匹配 O(n) = O(n+m)。
• 空间复杂度：O(m)，存储 next 数组。

补充一点：不少教材把前缀表整体减一、或右移一位后再填 -1 作为 next 数组，那只是回退公式随之微调的实现习惯，本质都是同一张前缀表。本文直接使用前缀表本身，手推结果和代码可以一一对上。

重复的子字符串（459）：前缀表的另一个用法

判断字符串 s 能否由某个子串重复多次构成："ababab" 可以，"aba" 不行。

关键结论：设 n 为串长，len = next[n-1]（整个串的最长相等前后缀）。若 len > 0 且 n % (n - len) == 0，则 s 由长度为 n - len 的子串重复构成。

直观理解：最长相等前后缀意味着串头和串尾有一段"重叠"，n - len 就是最小重复周期；周期能整除串长，说明整个串恰好被这个周期的子串铺满。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int[] next = buildNext(s);
        int len = next[next.length - 1];    // 最长相等前后缀长度
        int period = s.length() - len;      // 最小重复周期
        return len > 0 && s.length() % period == 0;
    }
}

验证："ababab"，n=6，next[5]=4，period=2，6%2==0 → true；"aba"，n=3，next[2]=1，period=2，3%2≠0 → false。

易错点

• 回退写成 j = next[j]：必须是 next[j-1]。j 指向"下一个待匹配字符"，要查的是它前面已匹配部分的前缀表。
• 构建 next 时用 if 处理失配：必须 while 连续回退，否则 next 数组算错。
• 459 忘记判断 len > 0：len 为 0 时 period 恰好等于 n，n % n == 0 会把 "abc" 这类无重复串误判为 true。
• 主流程返回值：匹配完成时 i 停在模式串末尾对齐的文本位置，起点是 i - m + 1。

题目清单

延伸：214 最短回文串也是前缀表思想的变体（在 s + 分隔符 + reverse(s) 上求最长相等前后缀），学有余力可以做。

参考

• 代码随想录 · 字符串专题