【LeetCode刷题日记】一篇彻底搞懂KMP算法（附LeetCode28.详解）及原理剖析

北极的代码

发布于 2026-04-22 13:51:33

2550

摘要： KMP算法是字符串匹配中的经典算法，通过利用匹配失败后的信息，避免主串指针的回溯，将时间复杂度从暴力匹配的O(n×m)优化到O(n+m)。本文从核心概念入手，详细讲解了前缀与后缀的定义、最长相等前后缀的计算方法，以及next数组的四种实现方式（经典版、统一减一版、nextval优化版、PMT版），并通过图解和代码示例展示构建过程。文章还包含LeetCode 28题的完整题解、多个生动比喻帮助理解，以及时间复杂度的详细分析。无论你是初学者还是准备面试，本文都能帮你彻底搞懂KMP算法的理论基础与代码实现。

KMP算法理论基础：

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，由Knuth、Morris和Pratt三位大神共同发明。它通过利用模式串自身的重复模式，避免不必要的回溯，将时间复杂度优化到O(m+n)。

核心原理

1. 传统暴力匹配的问题暴力匹配在匹配失败时，模式串会回溯到开头，主串回溯到起始位置的下一个字符，导致大量重复比较。 2. KMP的核心思想

主串指针不回溯：匹配失败时，主串的指针i不往回走
利用部分匹配信息：模式串向右滑动尽可能远的距离
前缀函数（Partial Match Table）：预先计算模式串中每个位置的最长相等前后缀长度

前缀和后缀（核心概念）

1. 定义

前缀：从字符串开头开始，不包含最后一个字符的所有连续子串 后缀：从字符串结尾开始，不包含第一个字符的所有连续子串 真前缀/真后缀：不包含整个字符串本身

2. 形象比喻 🎪

想象一串糖葫芦：A B A B C（5个山楂）

text

前缀（从左边吃）：
- "A"          （吃第1个）
- "AB"         （吃第1-2个）
- "ABA"        （吃第1-3个）
- "ABAB"       （吃第1-4个）
- ❌ 不吃"ABABC"（那是整串）

后缀（从右边吃）：
- "C"          （吃最后1个）
- "BC"         （吃最后2个）
- "ABC"        （吃最后3个）
- "BABC"       （吃最后4个）
- ❌ 不吃"ABABC"（那是整串）

3. 具体例子

以字符串 "ABABA" 为例：

长度	前缀	后缀	是否相等
1	"A"	"A"	✅ 相等
2	"AB"	"BA"	❌ 不相等
3	"ABA"	"ABA"	✅ 相等
4	"ABAB"	"BABA"	❌ 不相等

最长相等前后缀长度 = 3（"ABA"）

最长相等前后缀

对于模式串"ABABC"：

"A"：前缀集合{}，后缀集合{} → 长度0
"AB"：前缀{A}，后缀{B} → 长度0
"ABA"：前缀{A, AB}，后缀{A, BA} → 最长相等前后缀"A" → 长度1
"ABAB"：前缀{A, AB, ABA}，后缀{B, AB, BAB} → 最长相等前后缀"AB" → 长度2
"ABABC"：前缀{A, AB, ABA, ABAB}，后缀{C, BC, ABC, BABC} → 长度0

next数组的含义

next[i] 表示：模式串前 i+1 个字符组成的子串中，最长相等前后缀的长度

举例：模式串 "ABABAC"

位置i	子串	前缀集合	后缀集合	最长相等前后缀	next[i]
0	"A"	{}	{}	无	0
1	"AB"	{A}	{B}	无	0
2	"ABA"	{A, AB}	{A, BA}	"A" (长度1)	1
3	"ABAB"	{A, AB, ABA}	{B, AB, BAB}	"AB" (长度2)	2
4	"ABABA"	{A, AB, ABA, ABAB}	{A, BA, ABA, BABA}	"ABA" (长度3)	3
5	"ABABAC"	{A, AB, ABA, ABAB, ABABA}	{C, AC, BAC, ABAC, BABAC}	无	0

next数组的多种实现方式

方式1：经典版（前缀表不减一）

这是最常用的实现，next[i]直接存储最长相等前后缀长度。其实寻找的方法跟我们知道的辗转相除法原理有异曲同工之妙。可以抽空对比一下。

我们刚学的时候很不理解，我们要找的是最大长度相等前后缀，这里仅仅比较了某两位位置的字符是否相等，很不理解，其实，这里的门道全在next数组中，类似于多米诺骨牌，我们前面比较的结果已经被记录在案了，影响我们后面的比较，看似是两个字符的比较，实则已经是动态规划的必然结果了。

next[0]=0  (基础)
    ↓
next[1]=0  (通过比较s[0]和s[1])
    ↓
next[2]=1  (通过比较s[0]和s[2]，利用next[1])
    ↓
next[3]=2  (通过比较s[1]和s[3]，利用next[2])
    ↓
next[4]=3  (通过比较s[2]和s[4]，利用next[3])
    ↓
next[5]=0  (通过比较，利用next[4]、next[2]、next[0])

java

/**
 * 经典版next数组
 * next[i] = 子串s[0...i]的最长相等前后缀长度
 */
public static int[] getNext(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];
    int j = 0;  // 前缀指针，也表示长度
    
    next[0] = 0;  // 第一个字符没有前后缀
    
    for (int i = 1; i < m; i++) {
        // 不匹配时回溯
        while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
            j = next[j - 1];
        }
        
        // 匹配时前进
        if (pattern.charAt(j) == pattern.charAt(i)) {
            j++;
        }
        
        next[i] = j;
    }
    
    return next;
}

示例运行

java

String pattern = "ABABC";
int[] next = getNext(pattern);
// 结果: [0, 0, 1, 2, 0]

三、方式2：统一减一版（next[0] = -1）

这种实现在KMP原论文中使用，代码更简洁。

java

/**
 * 减一版next数组
 * next[i] = 最长相等前后缀长度 - 1
 */
public static int[] getNextMinusOne(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];
    int j = -1;  // 前缀指针，从-1开始
    int i = 0;
    
    next[0] = -1;  // 第一个字符设为-1
    
    while (i < m - 1) {
        if (j == -1 || pattern.charAt(j) == pattern.charAt(i)) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];  // 回溯
        }
    }
    
    return next;
}

示例运行

java

String pattern = "ABABC";
int[] next = getNextMinusOne(pattern);
// 结果: [-1, 0, 0, 1, 2]
// 对应关系：经典版+1 = 减一版的值

配套的匹配代码

java

public static int kmpSearchMinusOne(String text, String pattern) {
    int[] next = getNextMinusOne(pattern);
    int n = text.length(), m = pattern.length();
    int i = 0, j = 0;
    
    while (i < n && j < m) {
        if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    
    if (j == m) {
        return i - j;
    }
    return -1;
}

四、方式3：优化版（nextval）

解决模式串有大量重复字符时的效率问题。

java

/**
 * 优化版next数组（nextval）
 * 避免在重复字符上多次回溯
 */
public static int[] getNextVal(String pattern) {
    int m = pattern.length();
    int[] nextval = new int[m];
    int j = 0;
    
    nextval[0] = 0;
    
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
            j = nextval[j - 1];
        }
        
        if (pattern.charAt(j) == pattern.charAt(i)) {
            j++;
        }
        
        // 优化：如果下一个字符相同，继续回溯
        if (i + 1 < m && pattern.charAt(i + 1) == pattern.charAt(j)) {
            nextval[i] = nextval[j - 1];
        } else {
            nextval[i] = j;
        }
    }
    
    return nextval;
}

优化效果对比

java

// 模式串 "AAAAA"
String pattern = "AAAAA";

// 经典版
int[] next1 = getNext(pattern);      // [0, 1, 2, 3, 4]

// 优化版
int[] nextval = getNextVal(pattern); // [0, 0, 0, 0, 0]

// 优化版避免了重复比较，效率更高

五、方式4：PMT部分匹配表版

直接体现"部分匹配表"的概念。

java

/**
 * PMT (Partial Match Table) 版本
 * 与经典版相同，但命名更学术
 */
public static int[] getPMT(String pattern) {
    int m = pattern.length();
    int[] pmt = new int[m];
    int j = 0;
    
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = pmt[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        pmt[i] = j;
    }
    
    return pmt;
}

图解next数组构建过程

以 "ABABAC" 为例，详细跟踪：

text

初始: pattern = "A B A B A C"
索引:           0 1 2 3 4 5
next:          0 0 0 0 0 0

i=1, j=0: pattern[1]='B' vs pattern[0]='A' → 不匹配
         j=0, next[1]=0
         
i=2, j=0: pattern[2]='A' vs pattern[0]='A' → 匹配！
         j=1, next[2]=1
         
i=3, j=1: pattern[3]='B' vs pattern[1]='B' → 匹配！
         j=2, next[3]=2
         
i=4, j=2: pattern[4]='A' vs pattern[2]='A' → 匹配！
         j=3, next[4]=3
         
i=5, j=3: pattern[5]='C' vs pattern[3]='B' → 不匹配
         j=next[2]=1 (回溯)
         pattern[5]='C' vs pattern[1]='B' → 不匹配
         j=next[0]=0
         pattern[5]='C' vs pattern[0]='A' → 不匹配
         j=0, next[5]=0

结果: next = [0, 0, 1, 2, 3, 0]

各版本对比总结

版本	next[0]	特点	适用场景
经典版本	0	直观易懂，最常用	一般场景
-1偏移版	-1	代码简洁，判断方便	教材、竞赛
nextval	0	优化重复字符	特殊模式串
PMT	0	原始定义	学术理解

使用建议

初学者：先用经典版本（next[0]=0）
竞赛编程：用-1偏移版本（代码更简洁）
特殊模式（如"AAAAA"）：用nextval优化版
面试：掌握经典版本即可，理解原理最重要

时间复杂度分析

构建next数组：O(m)，其中m为模式串长度
匹配过程：O(n)，其中n为主串长度
总时间复杂度：O(m + n)
空间复杂度：O(m)，用于存储next数组

总结

KMP算法的精髓在于：

避免主串回溯：通过分析模式串自身特性，确定在不匹配时模式串应该移动的距离
前缀函数：核心是next数组，记录了模式串的前后缀匹配信息
空间换时间：用O(m)的预处理空间，换取O(m+n)的匹配时间

KMP算法适用于需要多次匹配或模式串较长、主串很大的场景，但对于一般场景，语言一些内置的find()方法（基于Boyer-Moore和Horspool等优化算法）通常更快。

类比理解：

以上就是KMO算法的理论基础，对于不了解的同学听起来肯定很晦涩难懂。下面我们来形象的理解一下：

比喻一：查字典找单词

想象你在查字典找单词 "APPLE"：

暴力方法（笨办法）：

从第一页第一个词开始，一个字母一个字母对比
发现第3个字母对不上，就回到开头，从下一页第一个词重新开始
就像你每次犯错都要从头翻字典，超级慢

KMP方法（聪明办法）：

你已经知道"APP"这三个字母是对的
下一次查找时，直接从"P"开始继续往后找
因为你知道"APP"后面可能接着"LE"，不需要重新检查已知的部分

比喻二：开车找路

假设你要从A点到B点，路线是：直行→右转→直行→左转→直行

暴力匹配（迷路后回到起点）：

text

你在路上开，到了第4个路口发现走错了
然后掉头开回起点，重新开始找路
每次都这样，太浪费时间！

KMP（记住经验）：

text

你在第4个路口发现错了，但你知道：
"前面3个路口（直行→右转→直行）是对的"
下次你就直接从这个经验点开始，不用回到起点

题目引入：LeetCode28

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

示例 1：

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

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成

题目解析：

这道题是KMP算法的经典应用，直接套用KMP匹配过程即可。

关键点：

构建 needle 的 next 数组
用 next 数组指导匹配，避免主串指针回溯
找到第一个匹配位置后立即返回

关于这里的回溯，我们可能并不是很能理解，我们不知道到底会移到哪里，然后就是关于循环中的i和j分别代表什么和初值处理

首先：

strStr方法中的i和j：

变量	全称	含义	指向
i	index of text	主串（haystack）的当前位置	正在比较的主串字符
j	index of pattern	模式串（needle）的当前位置	正在比较的模式串字符

然后就是getNext方法中的i和j：

这里的i是从1开始的，因为如果i=0，此时j也等于0，没法比较，我们这里的目的是找到字符串的最长相等前后缀。

方法	i的含义	i初值	原因
getNext	后缀末尾指针	i=1	至少需要2个字符才能比较前后缀
strStr	主串指针	i=0	从主串第一个字符开始匹配

然后就是关于回溯的过程，并不是只有一次，所以我们不能用if，必须要用while

needle:     A  B  A  B  A  C
索引:       0  1  2  3  4  5
next:      [0, 0, 1, 2, 3, 0]

主串某个字符: X (假设不等于 'C', 'B', 'A')

回溯路径（while）：
j=5 → next[4]=3 → 检查needle[3]='B' ≠ X
     → next[2]=1 → 检查needle[1]='B' ≠ X  
     → next[0]=0 → 检查needle[0]='A' ≠ X
     → 最终 j=0

用if只能走一步：
j=5 → next[4]=3 → 停止！j=3
但needle[3]='B' ≠ X，错误！应该继续回溯到0

回溯位置的确定：新位置 = 最长相等前后缀的长度

简单的说：跳过的就是最长相等前后缀中的"前缀部分"。因为我们的next数组已经找到了最长相等的前后缀

已匹配: [0...k-1] ... [L-k...L-1]
         └─前缀─┘     └─后缀─┘
             相等

后缀已经和主串比较过（肯定匹配）
所以前缀也一定和主串的对应部分匹配
因此不需要重新比较前缀部分
直接从前缀的下一个位置开始

为什么不能回溯到后缀呢，其实也很简单：

跳到后缀后面需要调整i，让i回溯，因为有时候还没匹配完，主串就没了，
会丢失已经确认匹配的前缀信息
需要重新比较已经匹配过的字符
时间复杂度会退化成O(n²)

next数组就写完了，之后就是比对主串的方法

变量	含义	初始值	作用
i	主串指针	0	指向主串当前要比较的字符
j	模式串指针	0	指向模式串当前要比较的字符
next	next数组	预先计算好	记录回溯位置

主串指针i从0开始，逐个遍历主串的每个字符， i只增不减，永不回溯，然后不匹配的时候就执行上面的回溯逻辑，之后就是常规操作了。

疑点分析：

我们刚学的时候很不理解，我们要找的是最大长度相等前后缀

这里仅仅比较了某两位位置的字符是否相等，很不理解

其实，这里的门道全在next数组中，类似于多米诺骨牌，我们前面比较的结果已经被记录在案了，影响我们后面的比较，看似是两个字符的比较，实则已经是动态规划的必然结果了。

next[0]=0  (基础)
    ↓
next[1]=0  (通过比较s[0]和s[1])
    ↓
next[2]=1  (通过比较s[0]和s[2]，利用next[1])
    ↓
next[3]=2  (通过比较s[1]和s[3]，利用next[2])
    ↓
next[4]=3  (通过比较s[2]和s[4]，利用next[3])
    ↓
next[5]=0  (通过比较，利用next[4]、next[2]、next[0])

表面只比较两个字符，但next数组已经"记住"了之前所有字符的相等关系，所以一个字符的比较就能推断出整个前后缀的相等性！这是动态规划的思想，用小问题的解构建大问题的解

题目答案：

class Solution {
    //前缀表（不减一）Java实现
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];
        getNext(next, needle);

        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) 
                j = next[j - 1];
            if (needle.charAt(j) == haystack.charAt(i)) 
                j++;
            if (j == needle.length()) 
                return i - needle.length() + 1;
        }
        return -1;

    }
    
    private void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) 
                j = next[j - 1];
            if (s.charAt(j) == s.charAt(i)) 
                j++;
            next[i] = j; 
        }
    }
}

结语：如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！