高频必考！KMP算法：主串指针绝不回退，一句话把O(mn)压成O(n+m)

溪语流沙

127人浏览 · 2026-09-28 08:00:00

溪语流沙 · 2026-09-28 08:00:00 发布

字符串匹配是每个程序员最早接触的算法：在一个文本里找一段模式串。

暴力做法O(mn)，面试官点点头，然后问：“还能优化吗？”

这就是KMP的登场时刻。它的全部洞察浓缩成一句话：失配时主串指针绝不回退，只移动模式串。

为什么敢这么干？

已匹配的那段文本里，存在可以被复用的“最长相等真前后缀”。

今天把三件事彻底讲透：

什么是“最长相等真前后缀”
next数组怎么构造（本质是模式串自己跟自己做一次KMP）
失配时j = next[j]到底在说什么

📦 题目速览 LeetCode 28（30秒读懂）

给定haystack和needle，返回needle在haystack中第一次出现的下标，不存在返回-1。

示例：

haystack = "sadbutsad", needle = "sad" → 0
haystack = "leetcode", needle = "leeto" → -1
haystack = "aabaabaaf", needle = "aabaaf" → 3（今天图解主角）

约束： 长度 ≤ 1e4，仅小写字母。
提示： 可以调库过题，但面试考的就是自己实现。

🧠 核心思路：用“最长相等真前后缀”量化失配时能滑多远

暴力为什么慢？

暴力匹配：拿模式串对准主串，逐字符比对；一旦失配，主串指针i回退到i+1，模式串j归零，从头再比。

病根只有一条：i回退了。 主串里已经比对过的字符，被白白重新比对。

KMP 的洞察

模式串已经匹配的前j个字符的信息，我们都拿到了——为什么不复用？

核心概念：最长相等真前后缀（PMT）

对模式串的某个前缀p[0..k]，把所有“既是它的前缀、又是它的后缀”的子串叫相等前后缀；其中长度最长的那个，长度记为PMT值。“真”字意味着这个子串不能等于它自己。

以p = "aabaaf"举例：

前缀	最长相等真前后缀	长度 PMT
`"a"`	—	0
`"aa"`	`"a"`	1
`"aab"`	—	0
`"aaba"`	`"a"`	1
`"aabaa"`	`"aa"`	2
`"aabaaf"`	—	0

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

这个表为什么有用？

假设已匹配前5个字符"aabaa"，第6个失配：

主串 s:   ... a a b a a | X ...     ← 已知这5个字符 == p的前5个
模式 p:       a a b a a | f
                          ↑ 失配

暴力会丢掉一切重来。但我们知道："aabaa"的最长相等真前后缀是"aa"（长度2）。这意味着：

它的前缀 "aa" == 它的后缀 "aa"
后缀"aa"已经在主串里被确认过了
所以可以直接把模式串右移，让前缀"aa"对准主串那两个字符，j跳到2继续比——中间字符不用重比！

一句话：失配时模式串能滑多远，取决于已匹配部分的最长相等真前后缀有多长。

next数组：把PMT右移一位

工程上把 PMT 整体右移一位，next[0] = -1：

p      :  a   a   b   a   a   f
PMT    : [0,  1,  0,  1,  2,  0]
next   : [-1, 0,  1,  0,  1,  2]   ← next[i] = PMT[i-1]

这样一来：

第j位失配时，直接j = next[j]——无需下标特判
next[j] = -1是哨兵信号：“没有任何前缀可复用，主串指针i也往后走一格”

next数组怎么构造？——模式串自己和自己做一次KMP

这是最惊艳的部分：构造next和匹配主串共用同一份控制流。

用两个指针i（当前要算next的位置）和j（当前已匹配的前缀长度），让p的后缀去“匹配”p自己的前缀：

若p[i] == p[j]：前缀延长，i++、j++，记next[i] = j
若失配或j == -1：j按next[j]回退，i不动；回退到-1则双方一起前进，记next[i] = 0

这既是动态规划（用已求出的next[0..i-1]推next[i]），也是“自匹配”。

🖼️ 图解算法（手把手走一遍）

1）构造next数组（`p = "aabaaf"`）

轮次	i	j	比较	动作	写入
初始	0	-1	`j == -1`	双方前进 → i=1, j=0	`next[1] = 0`
1	1	0	`'a'` vs `'a'` ✅	双方前进 → i=2, j=1	`next[2] = 1`
2	2	1	`'b'` vs `'a'` ❌	`j = next[1] = 0`	—
3	2	0	`'b'` vs `'a'` ❌	`j = next[0] = -1`	—
4	2	-1	`j == -1`	双方前进 → i=3, j=0	`next[3] = 0`
5	3	0	`'a'` vs `'a'` ✅	双方前进 → i=4, j=1	`next[4] = 1`
6	4	1	`'a'` vs `'a'` ✅	双方前进 → i=5, j=2	`next[5] = 2`

结果 next = [-1, 0, 1, 0, 1, 2]。注意：i从不回退，只有j在按next跳转。

2）用它去匹配（`s = "aabaabaaf"`, `p = "aabaaf"`）

下标:     0  1  2  3  4  5  6  7  8
主串 s:   a  a  b  a  a  b  a  a  f
模式 p:   a  a  b  a  a  f

步骤	i	j	比较	结果	说明
1	0→5	0→5	连续5次相同	双前进	已匹配 `"aabaa"`
2	5	5	`s[5]='b'` vs `p[5]='f'`	❌ 失配	`j = next[5] = 2`，i纹丝不动！
3	5	2	`s[5]='b'` vs `p[2]='b'`	✅ 双前进	复用已验证的`"aa"`
4	6→8	3→5	`a`、`a`、`f`三次相同	双前进	全部匹配
5	9	6	—	返回`i - m = 9 - 6 = 3`	✅

关键观察：整张表里 i从0单调走到9，一次都没有回退。第2步是高光时刻——失配时不看主串历史，只查next[5] = 2。

对照暴力：它得把i从5退回1，重新比对，白干4次。

💻 代码实现（Python + Java）

Python版

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        if m == 0:
            return 0
        nxt = self._build_next(needle)

        i = j = 0                                 # i主串指针（永不回退）
        while i < n and j < m:
            if j == -1 or haystack[i] == needle[j]:
                i += 1
                j += 1                            # 匹配（或j是哨兵-1）→ 双双前进
            else:
                j = nxt[j]                        # ★ 失配：只回退 j，i一动不动
        return i - m if j == m else -1

    @staticmethod
    def _build_next(p: str) -> list:
        """构造next数组：本质是模式串的前缀与后缀自己跟自己做一次匹配"""
        m = len(p)
        nxt = [-1] * m                            # next[0] = -1
        i, j = 0, -1
        while i < m - 1:
            if j == -1 or p[i] == p[j]:
                i += 1
                j += 1
                nxt[i] = j                        # 前缀成功延长一位
            else:
                j = nxt[j]                        # ★ 失配：回退到更短的可复用前缀
        return nxt

Java 版

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) return 0;
        int[] next = buildNext(needle);

        int i = 0, j = 0;                         // i主串指针（永不回退）
        while (i < n && j < m) {
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];                      // ★ 只移动模式串
            }
        }
        return j == m ? i - m : -1;
    }

    private int[] buildNext(String p) {
        int m = p.length();
        int[] next = new int[m];
        next[0] = -1;
        int i = 0, j = -1;
        while (i < m - 1) {
            if (j == -1 || p.charAt(i) == p.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];                      // ★ 递推：回退找次长前缀
            }
        }
        return next;
    }
}

⚠️ 防坑提醒（必看）：

while (i < m - 1)而不是 < m——next[0]已定为 -1，写成 < m会下标越界。
j == -1哨兵分支绝不能漏，它负责“彻底没得复用时让i前进”。
匹配成功返回i - m（循环里i已多走一格），不是i - j。
两段代码结构几乎一模一样——记住“自匹配”这个比喻，两份代码一起就都记住了。

⏱️ 复杂度分析（面试必问）

阶段	时间	说明
构造 next	O(m)	`i`单调增长，`j`回退总量 ≤ 前进总量
匹配	O(n)	`i`从不回退，`j`回退受限于前进次数
总计	O(n + m)	相比暴力O(n·m) 是降维打击
空间	O(m)	next数组本身，主串无需额外空间

常见误解：有人认为KMP是O(n·m)，因为j可能回退很多次。不对——j的回退严格受限于它之前的前进次数，而前进总和 ≤ n，所以回退总和也 ≤ n。这是均摊分析的经典小练习，面试讲出来很加分。

🚀 举一反三：5道高频变体题

题目	变化点	思路要点
LC.459 重复的子字符串	判断能否由子串重复构成	求PMT，答案 = `pmt[n-1] > 0 && n % (n - pmt[n-1]) == 0`
LC.686 重复叠加字符串匹配	A重复几次能包含B	KMP匹配时允许i循环复用A
LC.214 最短回文串	开头补最少字符变回文	构造`s + "#" + reverse(s)`求PMT
LC.1392 最长快乐前缀	求最长相等真前后缀本身	直接就是PMT的定义题
LC.28（今天）	找首次出现的下标	next数组 + 匹配

💬 面试追问模拟（提前准备，惊艳全场）

Q1：next数组为什么要右移一位？PMT和next有什么区别？

PMT[i]定义为“p[0…i]的最长相等真前后缀长度”，用它时失配得写j = pmt[j-1]，还得单独判断j == 0。右移一位并令next[0] = -1 之后，next[j]的语义变成“在第j位失配时，j应该跳到哪里”，循环里统一写成j = next[j]。这是一次纯粹为了代码优雅而做的下标平移，信息量完全等价。

Q2：怎么求next数组？能口述递推过程吗？

设已经算出next[0..i-1]，当前比较p[i]与p[j]。
若相等，说明最长前后缀延长一位：next[i] = ++j。
若不等，不是归零重来，而是令j = next[j]去找“次长的候选”继续试——因为next[j]已经告诉了我们“在j这个位置失配该退到哪”。退到-1说明没有可用的，next[i] = 0。
这就是DP的“子问题复用”。

Q3：BM / Sunday实际更快，为什么面试还是考KMP？

事实确实如此：Boyer-Moore和Sunday在真实文本上通常比KMP快数倍，各种标准库都用它们的变体或SIMD版本。但 KMP有两个不可替代的价值：
① 它是最坏情况严格O(n+m) 的算法；
② next数组所体现的“预处理自身 + 有限状态自动机 + 均摊分析”是一整套方法论，能考察候选人对DP和不变式的理解。
面试官考KMP，考的是思维，不是性能。

Q4：KMP在工程里真的有用吗？