跳至主要內容

字符串匹配：KMP的next数组完整推导

老张2026/4/30大约 10 分钟

字符串匹配：KMP的next数组完整推导

适读人群：Java 开发者、深耕字符串算法的工程师 | 阅读时长：约25分钟 | 难度：Medium

开篇故事

我有一个习惯：每次在项目里看到 String.indexOf()，都会想一下底层用的是什么算法。JDK 的 indexOf 实现其实比较朴素，基本上是暴力匹配（有些场景下有简单优化），在短字符串上没问题，但如果主串很长、模式串有很多重复前缀，性能就不那么好看了。

KMP（Knuth-Morris-Pratt）是字符串匹配里最经典的 O(n+m) 算法，n 是主串长度，m 是模式串长度。我第一次在大学课堂上学到它，完全没看懂——不是因为代码复杂，而是讲解方式实在不好，上来就给你一张 next 数组，完全不解释为什么这样算。

后来我自己花了两天时间把它从头推导了一遍，终于搞懂了。KMP 的精妙不在于代码，在于 next 数组背后的"最长公共前后缀"思想。一旦搞懂这个，代码写起来反而很自然。

今天我就把我当年推导的完整过程写出来，力求让你真正理解，而不只是会默写代码。

一、题目解析

LeetCode 28. 找出字符串中第一个匹配项的下标（Find the Index of the First Occurrence in a String）

给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1。

输入输出示例：

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释：第一个匹配项在下标 0 处，第二个在下标 6 处，返回第一个

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1

边界情况 3（模式串是空串）：

输入：haystack = "hello", needle = ""
输出：0

边界情况 4（模式串等于主串）：

输入：haystack = "abc", needle = "abc"
输出：0

边界情况 5（模式串比主串长）：

输入：haystack = "a", needle = "ab"
输出：-1

考察的核心知识点：

  • 暴力匹配的回退机制
  • KMP 的核心优化：匹配失败时不回退主串指针
  • next 数组（最长公共前后缀数组）的构造与含义
  • KMP 的两阶段：构建 next 数组 + 利用 next 数组匹配

二、解法一：暴力匹配

思路分析

对主串中每个起始位置 i，尝试从 i 开始匹配模式串，一旦失配就回退 i，从 i+1 重新开始。

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m == 0) return 0;
        
        for (int i = 0; i <= n - m; i++) {
            // 尝试从 i 开始匹配
            int j = 0;
            while (j < m && haystack.charAt(i + j) == needle.charAt(j)) {
                j++;
            }
            if (j == m) return i;  // 完全匹配
        }
        return -1;
    }
}

时间复杂度：O(n×m)。最坏情况：haystack = "aaaaaab", needle = "aaab"，每次都要匹配到接近末尾才失配，回退重来。

空间复杂度：O(1)。

三、解法二：KMP 算法——next 数组完整推导

为什么暴力慢

暴力匹配失败时，主串指针 i 回退到 i+1，模式串指针 j 回退到 0。问题在于：我们已经知道 haystack[i..i+j-1] == needle[0..j-1]（这段是匹配成功的部分），当 haystack[i+j] != needle[j] 时，是否真的需要从 i+1 重新开始？

不需要！ 如果模式串 needle[0..j-1] 有最长的公共前后缀（即某个前缀等于某个后缀），那么失配时，不需要把 j 退回 0，而是退回到这个公共前后缀的长度位置，主串指针 i 根本不动。

举例：needle = "aabaabaac"，当匹配到第 7 位（'b'）时发生失配。此时已经匹配了 "aabaab"，注意 "aabaab" 有最长公共前后缀 "aab"（长度 3）。所以 j 可以退到 3，而不是 0，继续从 needle[3] 开始比较，主串指针不动。

这就是 KMP 的核心：利用已匹配部分的信息，减少回退距离。

next 数组（也叫 failure function）

next[j] 定义为：needle[0..j-1]（前 j 个字符）的最长公共前后缀的长度。

公共前后缀：字符串的某个前缀同时也是某个后缀（但不是整个字符串本身）。

例：needle = "aabaabaac"

jneedle[0..j-1]最长公共前后缀next[j]
0""无0
1"a"无0
2"aa""a"1
3"aab"无0
4"aaba""a"1
5"aabaa""aa"2
6"aabaab""aab"3
7"aabaaba""aab"a" → "a"4
8"aabaabaa""aa"2

next 数组的构建（自身匹配法）

构建 next 数组：用 needle 自己匹配自己（pattern 既当主串又当模式串）。

int[] buildNext(String pattern) {
    int m = pattern.length();
    int[] next = new int[m + 1];  // next[0] = 0，next[j] 对应前 j 个字符
    next[0] = 0;
    int k = 0;  // 当前前缀长度（也是"匹配指针"）
    
    for (int j = 1; j < m; j++) {
        // j 是"后缀指针"，k 是"前缀指针"
        // 如果不匹配，k 回退到 next[k]
        while (k > 0 && pattern.charAt(k) != pattern.charAt(j)) {
            k = next[k];  // 这就是 KMP 思想的自我应用！
        }
        // 如果匹配，k 前进
        if (pattern.charAt(k) == pattern.charAt(j)) {
            k++;
        }
        next[j + 1] = k;  // next[j+1] = 前 j+1 个字符的最长公共前后缀长度
    }
    return next;
}

注意：这里构建 next 数组的代码，本身就是一个 KMP 匹配过程（用 pattern 匹配 pattern）！理解了这个，next 数组的构建就不再神秘。

完整 KMP 代码

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m == 0) return 0;
        if (n < m) return -1;
        
        // 第一步：构建 next 数组
        int[] next = buildNext(needle);
        
        // 第二步：KMP 匹配
        int j = 0;  // 模式串指针
        for (int i = 0; i < n; i++) {
            // 不匹配时，j 利用 next 回退（主串指针 i 不动）
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j];  // 退回到最长公共前后缀的长度
            }
            // 匹配时，j 前进
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            // 整个模式串都匹配了
            if (j == m) {
                return i - m + 1;  // 匹配起始位置
            }
        }
        return -1;
    }
    
    // 构建 next 数组（最长公共前后缀数组）
    private int[] buildNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m + 1];
        // next[0] = 0（空串的公共前后缀长度为0）
        // next[1] = 0（单字符无公共前后缀）
        
        int k = 0;
        for (int j = 1; j < m; j++) {
            // k 不匹配时，利用已有 next 值回退（KMP 的核心递推）
            while (k > 0 && pattern.charAt(k) != pattern.charAt(j)) {
                k = next[k];
            }
            if (pattern.charAt(k) == pattern.charAt(j)) {
                k++;
            }
            next[j + 1] = k;
        }
        return next;
    }
}

复杂度分析

时间复杂度：O(n + m)

推导：构建 next 数组：j 从 0 到 m-1，k 只会通过 next 回退减小，但每次匹配成功 k 最多增加 1，所以 k 增加的总次数 ≤ m，回退次数也 ≤ m。构建总时间 O(m)。

匹配阶段：主串指针 i 从 0 到 n-1，j 只会通过 next 回退减小，增加次数 ≤ n，回退次数也 ≤ n。匹配总时间 O(n)。

合计：O(n + m)。

空间复杂度：O(m)，next 数组大小。

我在 LeetCode 提交，运行时间 1ms，击败 99.5% 的 Java 用户。

四、解法三：Java 内置 indexOf（了解即可）

JDK 的 String.indexOf 在某些场景下有优化（如利用最后不匹配字符跳过），但不是 KMP，也不是 Boyer-Moore。了解即可，面试不要说"我直接用 indexOf 就好了"。

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);  // 不要在面试里这么写
    }
}

五、举一反三

同类型题目

LeetCode 459. 重复的子字符串

判断字符串 s 是否由其子字符串重复多次构成。巧妙利用 KMP 的 next 数组：如果 m % (m - next[m]) == 0 且 next[m] != 0，则是重复字符串。

LeetCode 686. 重复叠加字符串匹配（付费题）

判断 a 重复多少次后包含 b 作为子串。

LeetCode 214. 最短回文串

在字符串 s 前面添加字符，使其变成最短回文串。利用 KMP 找 s 中最长的回文前缀。

KMP 实际工程应用

  • 文本编辑器的"查找"功能
  • 防病毒软件的特征码匹配
  • 日志分析中的关键词搜索
  • 基因序列比对（虽然通常用更专业的算法）

面试中的变体和追问

  1. next 数组的值是什么意思？ 答：next[j] 是模式串前 j 个字符的最长公共前后缀的长度。当第 j 个字符匹配失败时，不需要把 j 退到 0，退到 next[j] 即可继续匹配。

  2. KMP 和 Boyer-Moore 有什么区别？ 答：KMP 利用模式串的前缀信息，从左到右扫描主串，每个字符只访问一次，适合流式匹配。Boyer-Moore 利用模式串的后缀信息，可以跳跃，在实践中通常更快，但实现复杂。JDK 内置的 indexOf 在长模式串上使用了类 BM 的优化。

六、踩坑实录

坑一：next 数组的索引定义不统一

现象： 网上看到的 KMP 代码和我写的不一样，调不通。

原因： next 数组有不同的定义方式：有的是 next[j] 表示 pattern[0..j]（包括 j）的最长公共前后缀；有的是 next[j] 表示 pattern[0..j-1]（不包括 j）的。两种定义都对，但代码里用的位置不同，混用就会出错。

解法： 坚持一种定义，我习惯用"next[j] 是前 j 个字符（下标 0 到 j-1）的最长公共前后缀长度"，数组大小 m+1，next[0]=0，next[1]=0。

坑二：构建 next 数组时死循环

现象： 构建 next 数组时程序卡死。

原因： while 循环的终止条件写错：应该是 while (k > 0 && ...)，如果写成 while (k >= 0 && ...)，当 k=0 且仍不匹配时，k = next[0] = 0，无限循环。

解法： 终止条件必须是 k > 0，保证 k 为 0 时退出 while 循环。

坑三：空串处理

现象： needle 为空串时返回了 -1 或者抛异常。

原因： next 数组构建时如果 m=0，循环不执行，没问题。但匹配阶段如果 m=0，j == m 在初始就满足，返回的是 0（i-m+1 = 0-0+1 = 1？不对）……

解法： 在最开始加空串特判：if (m == 0) return 0，这是 LeetCode 的约定答案。

七、总结

KMP 是字符串算法里"最被误解"的算法之一，很多人背过代码但不理解背后的逻辑。真正理解它需要搞懂两件事：next 数组的含义（最长公共前后缀长度），以及构建 next 数组本身就是一个 KMP 匹配过程（用模式串匹配模式串）。

三条核心要点：

  1. KMP 的本质：匹配失败时，利用已匹配部分的前后缀信息，跳过不必要的比较，让主串指针永远不回退。

  2. next[j] = 模式串前 j 个字符的最长公共前后缀长度。这个值告诉我们：失配后，j 应该退到哪个位置继续匹配。

  3. 构建 next 数组和 KMP 匹配的代码结构几乎完全一样，都是一个"指针 k 利用 next 值回退"的循环。理解了一个，另一个就自然理解了。

延伸思考：

KMP 只支持单个模式串的匹配。如果有多个模式串需要同时匹配（比如过滤一批关键词），用 Aho-Corasick（AC 自动机）算法，它是 KMP 在多模式串场景下的扩展，本质是 Trie 树加 KMP 的失配跳转。这是工程里防刷词过滤、内容审核等场景的标准算法。

编辑此页
最近更新:
贡献者: xiaozhangge