入门：主串找模式串，从朴素 O(nm) 到线性

基于通用算法概念 · 核于 2026-07

速查

• 问题定义：给定主串 s（长 n）和模式串 p（长 m），找出 p 在 s 中所有出现位置——即所有满足 s[i..i+m-1] === p 的下标 i。
• 朴素法（双循环）：对每个起点 i 逐字符比对 s[i+k] 与 p[k]，失配则 i++ 重来——最坏 O(n·m)。
• 退化场景：主串 s = "aaaaaab"、模式 p = "aaab"——每个起点都对到第 4 个字符才发现 b≠a，主串指针反复回退，比较次数 ≈ n·m。
• 核心症结：朴素法失配后丢弃了「已匹配的那 k 个字符」的信息，盲目回到 i+1 重新比对。
• KMP（精确线性）：用 next 数组记录模式串自身的「最长公共前后缀」，失配时主串指针不动，模式串指针跳到 next[j] 复用已匹配前缀——严格 O(n+m)。
• Rabin-Karp（滚动哈希）：把模式串与主串每个 m 长窗口算哈希，比哈希值是否相等——平均 O(n+m)；多模式只需把多个模式哈希入集合一次扫描。
• Boyer-Moore（实际最快）：从后向前比对，靠坏字符规则（失配字符在模式中找下次对齐位置）+ 好后缀规则跳跃——常为亚线性（实际比较次数 < n）。
• 三者定位：KMP 精确最稳（严格线性、无冲突、主串不回溯，适合流式数据）；RK 多模式王者（哈希集合一次扫）；BM 工程实测最快（字母表越大跳跃越猛）。
• KMP 为何难：难点全在 next 数组构造——next[i] = 模式串前缀 p[0..i] 的「最长公共前后缀」长度，它的构造本身是「模式串自己跟自己做 KMP 匹配」。
• 复杂度速记：朴素最坏 O(nm)；KMP 预处理 O(m) + 匹配 O(n) = O(n+m)；RK 平均 O(n+m) 最坏 O(nm)；BM 最坏 O(n+m) 实际常亚线性。
• 应用：文本编辑器查找/替换（BM/BMH）、Ctrl+F 高亮、grep/正则引擎、生物序列比对、入侵检测特征串、DNA 序列 motif 查找。
• 进阶顺序：KMP 算法：next 数组与避免回溯 → Rabin-Karp 与 Boyer-Moore → 参考。

一、问题定义：主串里找模式串

字符串匹配是这样一个问题：给定一段主串（text / haystack）s，长度为 n；一个模式串（pattern / needle）p，长度为 m（m ≤ n）。目标是找出 p 在 s 中所有出现位置的起始下标。形式化地说，找出所有 i 使得：

s[i] s[i+1] ... s[i+m-1] === p[0] p[1] ... p[m-1]

比如 s = "ababcabcac"、p = "abcac"，匹配位置是 i = 5（s[5..9] = "abcac"）。输出匹配的起点下标而非匹配内容本身。

这个问题的工程意义无处不在：编辑器的查找替换、IDE 的全局搜索、grep 命令、浏览器的 Ctrl+F、垃圾邮件过滤（关键词命中）、入侵检测（特征串扫描）、基因测序（在某段 DNA 里找特定 motif）、String.indexOf / str.find 的底层实现，本质上都是「主串里找模式串」。

二、朴素法：直观但最坏 O(nm)

最直白的做法：把模式串 p 对齐到主串每个起点 i = 0, 1, ..., n-m，逐字符比对，全部相等则记录 i，遇到不等就让 i 前进一位、从头重新比对：

// 朴素字符串匹配：返回所有匹配起点下标
function naiveMatch(s, p) {
  const n = s.length, m = p.length;
  const res = [];
  for (let i = 0; i <= n - m; i++) {       // i = 当前对齐起点
    let j = 0;
    while (j < m && s[i + j] === p[j]) j++; // 逐字符比对
    if (j === m) res.push(i);               // 全部相等 → 命中
  }
  return res;
}

随机文本下朴素法其实很快（多数起点第 1 个字符就失配），平均接近 O(n+m)。问题在最坏情况：考虑 s = "aaaaa...aab"（n 个 a 加一个 b）、p = "aaa...ab"（m-1 个 a 加一个 b）。对每个起点 i，朴素法都比到第 m 个字符才发现 a ≠ b，然后 i++ 回到起点几乎重比一遍。比较次数约为 (n-m+1) · m，即 O(n·m)。

症结：丢弃了「已匹配信息」

朴素法失配时，已经比对过的那 j 个字符（s[i..i+j-1] === p[0..j-1]）是已知信息，但朴素法直接 i++ 把它们全扔了，重新从 p[0] 比对。所有进阶算法的本质，都是在「利用这些已匹配信息，避免主串回溯或跳跃式前进」：

• KMP：用模式串自身的结构（最长公共前后缀），失配后让模式串「往右挪到还能对上已匹配后缀的位置」，主串指针原地不动。
• Rabin-Karp：换一个视角——不比字符串相等，而比「长度为 m 的窗口的哈希值」是否相等，用滚动哈希 O(1) 滑动窗口。
• Boyer-Moore：从右往左比，一旦右侧失配，根据坏字符/好后缀直接把模式串大幅右移，跳过大量不可能的位置。

三、三种进阶算法的定位

算法	核心思想	预处理	匹配	实际表现
朴素	逐起点逐字符	无	最坏 O(n·m)	随机文本尚可，重复串退化
KMP	next 数组，主串不回溯	O(m)	O(n)	严格线性，最稳
Rabin-Karp	滚动哈希比相等	O(m)	平均 O(n)，最坏 O(n·m)	多模式王者
Boyer-Moore	坏字符 + 好后缀跳跃	O(m + 字母表)	最坏 O(n+m)，常亚线性	工程实测最快

• 何时选 KMP：要严格线性、无最坏退化、主串不可回退（流式数据 / 单次扫描）的场景。面试与教学的首选。
• 何时选 Rabin-Karp：要同时匹配多个模式串（把所有模式哈希值入集合，主串哈希一次扫描比对），或问题本身是「找等长子串」（如最长重复子串的二分 + RK）。
• 何时选 Boyer-Moore：实际工程追求最快（编辑器查找、grep），字母表越大（如英文/Unicode）坏字符跳跃收益越大；衍生算法 Boyer-Moore-Horspool（只保留坏字符规则、实现更简）是工业最常用变体。

四、为什么 KMP 这么难

KMP 的全部精髓与难点，集中在 next 数组（也叫「部分匹配表」partial match table、「失败函数」failure function）上。一句话定义：

next[i] = 模式串前缀 p[0..i] 的「真前缀」与「真后缀」中最长的公共串的长度。

例如 p = "abcab"：

i	p[0..i]	真前缀	真后缀	最长公共前后缀	next[i]
0	a	∅	∅	∅	0
1	ab	a	b	无	0
2	abc	a,ab	c,bc	无	0
3	abca	a,ab,abc	a,ca,bca	a	1
4	abcab	a,ab,abc,abca	b,ab,cab,bcab	ab	2

为什么是「最长公共前后缀长度」？因为失配发生在 p[j]，说明 p[0..j-1] 已经和主串对应位置相等；如果 p[0..j-1] 的长度为 next[j-1] 的前缀等于它的长度为 next[j-1] 的后缀，那么把这个前缀对齐到后缀位置，就能复用这 next[j-1] 个已匹配字符——主串指针无需回退，模式串指针跳到 next[j-1] 继续比即可。

next 数组的构造本身就是「模式串自己跟自己做 KMP 匹配」：用一个指针 i 扩展右端、一个指针 len 跟踪当前最长公共前后缀长度，详见 KMP 算法：next 数组与避免回溯。理解了这一句，KMP 就攻克了九成。

下一步

理解了匹配问题的症结（丢弃已匹配信息导致 O(nm)）与三种解法的定位后，下一步深入最核心、最常考的 KMP——拆解 next 数组的构造过程与「主串绝不回溯」的匹配机制，见 KMP 算法：next 数组与避免回溯。