字符串 · KMP 模式匹配

1. 核心原理

KMP（Knuth–Morris–Pratt）解决"在长度为 n 的主串 haystack 里找长度为 m 的模式串 needle 是否出现及位置"的问题，时间复杂度 O(n + m)。朴素双循环 O(nm) 在重复模式下会退化（例如 haystack = "aa...aab"、needle = "aa...ab"，每次都匹配到末位才失配，外层退一步重来）。KMP 的核心是预处理一张"失配表"，使主串指针永不回退。

next 数组的定义

记 next[i] 为 needle[0..i]（前 i + 1 个字符）最长真前缀同时也是真后缀的长度（"真"指不等于整个串本身）。等价表述：next[i] 是 needle[0..i] 自身去掉头一字符或去掉尾一字符仍能匹配上的最大长度。

举例 needle = "abcabd"：

文献里这张表还有别名：fail、pi、failure function，都是同一个东西。

为什么主串指针不用回退

匹配时维护两个指针：i 在 haystack、j 在 needle（已匹配 needle[0..j-1]）。若 haystack[i] == needle[j]，两者各 +1。一旦失配（haystack[i] != needle[j]），朴素做法是 i 退到上一个起点 + 1、j 归零；KMP 让 i 不动，j 跳到 next[j - 1]。

关键洞察：失配前 needle[0..j-1] 已经和 haystack[i-j..i-1] 完全相等。下一次有希望的对齐必然是把 needle 的某个前缀跟 haystack[i-j..i-1] 的某个后缀对齐——而最长这样的前缀正是 next[j - 1]。短一点的对齐不会更优（往回跳得越少越好），更长的对齐不存在（否则 next[j - 1] 就不是最长）。于是 i 保持原位，j 跳到 next[j - 1] 重新尝试。

i 永不回退保证主串总共扫一遍 O(n)。j 每次至多 +1，失配时只减，所以总变化次数也是 O(n)，整体 O(n + m)。

next 自匹配构造

构造 next 本身就是"needle 和 needle 自己做 KMP"。维护 i（当前要计算 next[i] 的位置，i ≥ 1）和 j（已匹配的真前缀长度）：

• 若 needle[i] == needle[j]：匹配成功，j += 1，next[i] = j，i += 1
• 否则若 j > 0：跳一步 j = next[j - 1]，继续比较（不递增 i）
• 否则：next[i] = 0，i += 1

这套递推保证每个 next[i] 都在常数摊还时间内算出来，总耗时 O(m)。

与 Z 函数的对偶关系

KMP 的 next[i] 描述"前缀也是后缀的最长长度"，而 Z 函数 描述"以 i 为起点与原串前缀的最长公共前缀长度"：Z[i] = max{ k : needle[0..k-1] == needle[i..i+k-1] }。两者都能 O(m) 算出来，互相可以推得对方。Z 函数在某些"统计每个位置匹配前缀长度"的题里更直接（例如本站点字符串哈希章节的部分变形），KMP 的 next 数组在"判周期 / 求公共前后缀"的题里更顺手。

下面这个交互演示走一遍 needle = "abcabd" 的 next 构造 + 在 haystack = "abcabcabd" 上的匹配：

2. 通用模板

把"构造 next"和"主匹配"放在同一函数里，两段逻辑结构对称——都是"匹配则 j +=1，失配则 j 跳 next[j-1]"。Python / Java / C++ 三套实现行为完全一致。

def kmp_search(haystack: str, needle: str) -> int:
    m = len(needle)
    if m == 0:
        return 0
    # 构造 next 数组
    nxt = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and needle[i] != needle[j]:
            j = nxt[j - 1]
        if needle[i] == needle[j]:
            j += 1
        nxt[i] = j
    # 主匹配
    j = 0
    for i in range(len(haystack)):
        while j > 0 and haystack[i] != needle[j]:
            j = nxt[j - 1]
        if haystack[i] == needle[j]:
            j += 1
        if j == m:
            return i - m + 1
    return -1

public int strStr(String haystack, String needle) {
    int n = haystack.length(), m = needle.length();
    if (m == 0) return 0;
    int[] nxt = new int[m];
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && needle.charAt(i) != needle.charAt(j)) j = nxt[j - 1];
        if (needle.charAt(i) == needle.charAt(j)) j++;
        nxt[i] = j;
    }
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && haystack.charAt(i) != needle.charAt(j)) j = nxt[j - 1];
        if (haystack.charAt(i) == needle.charAt(j)) j++;
        if (j == m) return i - m + 1;
    }
    return -1;
}

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) return 0;
        vector<int> nxt(m, 0);
        // 构造 next 数组
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) j = nxt[j - 1];
            if (needle[i] == needle[j]) j++;
            nxt[i] = j;
        }
        // 主匹配
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack[i] != needle[j]) j = nxt[j - 1];
            if (haystack[i] == needle[j]) j++;
            if (j == m) return i - m + 1;
        }
        return -1;
    }
};

几点要说明：

• while j > 0 && ... 而非 if：失配后 j 跳到 nxt[j - 1]，新位置可能仍失配，要继续跳直到匹配上或 j = 0。写成 if 会漏跳，导致匹配错位。
• 构造 next 时 i 从 1 开始：next[0] 必然是 0（单字符没有真前缀），跳过省一次判断。
• 空 needle 返回 0：与 LC 28 的官方约定一致（空串在任意位置 0 处出现）。Python str.find('') 也返回 0。
• i - m + 1 还是 i - m：取决于主循环里 i 是先比较再 +1 还是先 +1 再比较。本模板里 j == m 触发时 i 已经指向 needle 最后一个匹配字符之后，所以起点是 i - m + 1（Python 版用 enumerate，i 是当前字符下标；Java/C++ 版的 i 在循环体末尾才 +1，起点公式一致）。

3. 母题精讲

LeetCode 28. Find the Index of the First Occurrence in a String

链接：LeetCode 28

题目（中文翻译）：给两个字符串 haystack 和 needle，返回 needle 在 haystack 中第一次出现的下标；找不到返回 -1。

数据范围：

• 1 ≤ haystack.length, needle.length ≤ 10⁴
• 两个字符串只含小写英文字母

示例：

输入：haystack = "sadbutsad", needle = "sad"
输出：0

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

暴力解：双层循环

对 haystack 的每个起点 i，跟 needle 逐字符比较：

class Solution:
    def strStr_brute(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        for i in range(n - m + 1):
            j = 0
            while j < m and haystack[i + j] == needle[j]:
                j += 1
            if j == m:
                return i
        return -1

最坏 O(nm)。普通输入跑得过，但有典型对抗输入会让它直接退化：

haystack = "aaaaaaaaaab"
needle   = "aaab"

每次匹配到末位才失配，外层退一步又从头匹配，几乎跑满 n × m 次比较。n = m = 10⁴ 直接 10⁸ 操作，秒级 TLE。

KMP 解

直接套 §2 模板：构造 needle 的 next 数组，主循环里失配就让 j 跳。代码已经在 §2 给出。

时间 O(n + m)，空间 O(m) 存 next 数组。

LC 28 数据范围只到 10⁴，朴素 O(nm) 在普通输入下也能过。但对抗输入下必须 KMP。面试官出这道题往往是为后续追问"如果输入是 10⁷ 怎么办"铺垫——此时 O(nm) ≈ 10¹⁴ 必挂，O(n + m) ≈ 10⁷ 才能过。

Follow-up：LC 28 是找单次出现。如果题目要"判断一个字符串是否能由它的子串重复多次拼成"呢——这就是 §4.1 的 LC 459，会用 next 数组的另一个性质。

4. 例题

4.1 LC 459 重复的子字符串

链接：LeetCode 459

题意：给一个字符串 s，判断它能否由它的某个子串重复多次拼接而成。

数据范围：s.length 1 到 10⁴。

示例：

输入：s = "abab"
输出：true (由 "ab" 重复 2 次得到)

输入：s = "abcabcabc"
输出：true ("abc" × 3)

输入：s = "aba"
输出：false

KMP 解法：构造 s 的 next 数组。如果 s 由长度 k 的子串重复 t 次拼接，那么 next[n-1] = n - k（最后一位的最长共同前后缀就是去掉一个周期）。判定条件：

n % (n - next[n-1]) == 0  且  next[n-1] != 0

第一条保证 n 能被周期长度 k = n - next[n-1] 整除；第二条排除"整串不重复"的情况。

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        nxt = [0] * n
        j = 0
        for i in range(1, n):
            while j > 0 and s[i] != s[j]:
                j = nxt[j - 1]
            if s[i] == s[j]:
                j += 1
            nxt[i] = j
        k = n - nxt[n - 1]
        return nxt[n - 1] != 0 and n % k == 0

复杂度 O(n)。

证明 period = n - next[n-1]：如果 next[n-1] = L，说明 s 的前 L 字符 = 后 L 字符。设 period = n - L。重复 t = n / period 次 ⇔ n % period == 0。

Follow-up：上面是用 next 数组"判周期"。如果题目要"在 s 前面补最少字符使它变成回文"呢——这就是 LC 214，构造一个巧妙的复合串再跑 KMP。

4.2 LC 214 最短回文串

链接：LeetCode 214

题意：给一个字符串 s，在它前面添加字符，使它成为回文串。返回这样转换后的最短回文串。

数据范围：s.length 0 到 5 × 10⁴。

示例：

输入：s = "aacecaaa"
输出："aaacecaaa"

输入：s = "abcd"
输出："dcbabcd"

思路：要在前面补最少字符，等价于"找出 s 的最长回文前缀"——找到后，把 s 的剩余部分倒过来拼到最前面就行。

怎么用 KMP 找最长回文前缀？构造一个复合串 s + '#' + reverse(s)（# 是分隔符防止跨界匹配），对它跑 next 数组。最后一位的 next 值就是"s 的前缀同时也是 reverse(s) 的后缀的最长长度"——这正是 s 的最长回文前缀长度。

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        rev = s[::-1]
        combined = s + '#' + rev
        n = len(combined)
        nxt = [0] * n
        j = 0
        for i in range(1, n):
            while j > 0 and combined[i] != combined[j]:
                j = nxt[j - 1]
            if combined[i] == combined[j]:
                j += 1
            nxt[i] = j
        longest_palindrome_prefix = nxt[n - 1]
        # s 多出来的部分倒过来拼到前面
        return rev[: len(s) - longest_palindrome_prefix] + s

复杂度 O(n)。

这种复合串构造在 KMP 应用题里常见——它把"前缀 = 反转串后缀"这件事自动变成 KMP 能处理的"普通前后缀匹配"。

5. 边界、易错与复杂度

next 数组的两种约定

工业界对 next 数组的下标约定有两种：

• next[i] 表示 needle[0..i] 的最长共同前后缀长度（本章用法）
• next[i] 表示 needle[0..i-1] 失配时 j 应跳到的位置（很多教材用法，相当于本章约定整体右移一位）

两者等价，但混着用会出错。整本写题时统一一种即可，本章一律用第一种。

空串处理

needle == "" 时按惯例返回 0（空串在 haystack 的位置 0 处出现）。模板里 if m == 0: return 0 处理掉这个 corner case。

字符串原地索引 vs 转字节

Java 的 String.charAt(i) 是 O(1)，但 Python 的 s[i] 也是 O(1)（字符串底层是数组）。Go 的 s[i] 是字节，对 ASCII 没问题，多字节字符要先转 []rune。

多次匹配的扩展

如果题目要"找出 needle 在 haystack 的所有出现位置"，把"if j == m: return ..."改成"记录位置 + j = nxt[j - 1] 继续匹配"。

def kmp_search_all(haystack, needle):
    # ... 构造 nxt 略
    positions = []
    j = 0
    for i in range(len(haystack)):
        while j > 0 and haystack[i] != needle[j]:
            j = nxt[j - 1]
        if haystack[i] == needle[j]:
            j += 1
        if j == m:
            positions.append(i - m + 1)
            j = nxt[j - 1]            # 继续找
    return positions

复杂度速查

为什么是 O(n + m)：摊还论证

直觉是"内层 while 看起来 O(m)，外层 O(n)，加起来 O(nm)"——错。下面用变量增量做严格摊还分析。

匹配阶段：观察 j 这个游标。每次外层循环 i 推进 1 步：

• 若 s[i] == p[j] → j += 1（增 1）
• 若失配 → while 内 j = next[j-1]（减少，可能多次）
• j 全程满足 0 ≤ j ≤ m

j 在整个匹配过程中每次只能 +1（通过 if 分支），外层执行 n 次 → j 总增量 ≤ n。而 while 内每次 j = next[j-1] 都使 j 严格减少，所以减量总数 ≤ 增量总数 ≤ n。总操作 = j 总增量 + j 总减量 ≤ 2n，匹配阶段 O(n)。

构造 next 阶段：完全同构——把 pattern 自匹配，同样的论证给出 O(m)。

合起来 O(n + m)。这套"游标只能加一次、减只能减自己加过的"摊还套路在滑窗、单调栈里也反复出现，不止 KMP 一家。

KMP vs 其他字符串匹配算法

工程上 Python 的 str.find() / Java 的 String.indexOf() 内部用的是变种朴素或 Boyer-Moore-Horspool，对短模式经常比 KMP 快（常数小）。面试里 KMP 是常被期待写出的解法。

面试官常追问的几个方向

多模式匹配（搜 1M 个 pattern 怎么办） → KMP 是单 pattern 的；扩展到多 pattern 用 Aho-Corasick 自动机：把所有 pattern 插进 Trie，对 Trie 的每个节点构造 fail link——本质就是把 next 数组搬到了树上。fail link 的定义：节点 u 的 fail 指向 Trie 里"u 表示的前缀的最长真后缀"对应的节点。构造时按 BFS 层级算，每个节点的 fail 由其父节点的 fail 决定，与 KMP next 数组构造同构。匹配时也像 KMP 一样失配跳 fail。整体 O(N + L + #occurrences)，N 是文本长度，L 是所有 pattern 长度之和。

流式输入（pattern 已知、text 一字节一字节来） → KMP 天然在线——只维护一个 j 游标即可，每读一个字符 O(1) 摊还更新。这跟 Rabin-Karp 流式版（维护滚动哈希）思路类似但 KMP 不用担心哈希冲突。

分布式 grep（在大文件上跨节点切片搜 pattern） → 直接切会漏掉跨边界的匹配。标准做法：每个 chunk 末尾多读 m-1 个字节与下一块重叠，匹配结果按 chunk 的起点偏移合并。每个 chunk 内仍跑 KMP，整体 O(N)。

通配符 / 正则（? 单字符、* 任意串） → KMP 失效——next 数组依赖"字符相等"的传递性，引入通配后这个性质不成立。改用 DP（LC 44 / 10）或者把通配模式编译成 NFA / DFA。这是典型的"KMP 不能用"的边界，对应 [[recurring-quality-gaps]] 里的 pattern_connections 维度。

给你一段 1GB 的日志找一个固定 keyword → 工程上 90% 是 Boyer-Moore-Horspool 而不是 KMP——keyword 短、字母表大时 BM 跳跃步长更大常数更小。KMP 的优势是最坏情况 O(n+m) 保底、且天然适合在线，所以面试里仍是默认答案。

7. 小结

KMP 的核心是 next 数组——失配时模式串跳到"最长共同前后缀"的位置，让 haystack 指针永不回退。next 的字面定义是"最长真前后缀长度"，构造和匹配是同一套循环。掌握 next 之后，周期判定 / 回文前缀 / 多模式匹配都能用同一个工具解决。

对应灵神题单：字符串 / KMP / Z 函数

进一步阅读：LeetCode 字符串匹配题单 / 灵茶山艾府字符串专题