朴素模式匹配（BF 算法）

2026 大纲 六（八）字符串模式匹配 · 朴素匹配部分（KMP 见《KMP 算法》，前置概念见《串的基本概念》）。

不用想就能想到的那个办法

要在主串 $S$ 里找模式串 $T$，最朴素的念头是：把 $T$ 摆到 $S$ 的第 1 位上比一比，不行就整体右移一位再比，一直挪到挪不动为止。

$T$ 一共能摆多少个位置？$T$ 的末字符不能越过 $S$ 的末字符，所以起点从 1 到 $n-m+1$，共 $n-m+1$ 个对齐位置。每摆一个位置，就从头逐字符比 $T$ 的 $m$ 个字符：全对上就成功，中途撞上一个不等就作废，换下一个位置。

这就是 BF（Brute-Force，朴素/暴力匹配）的全部思想，穷举而已。它值得单独讲一节，不是因为算法本身有多难，而是因为它失败的方式，正好指出了 KMP 该往哪儿改。所以这一篇的重点不在"怎么写"，在"哪几个字符是白比的"。

先看一眼

下面的可视化把两个指针的移动画了出来。看的时候注意一件事：每次失配之后，$i$ 是不是往回退了。

加载可视化中...

看完你应该确认：$j$ 一失配就归 1，$i$ 也跟着退回本趟起点的下一位——主串里有些字符被读了不止一次。

唯一需要想一下的一行：i = i - j + 2

代码本身很短，麻烦只有回退那一行。

// BF 算法（串下标从 1 开始，ch[0] 闲置不用）
// 返回 T 在 S 中首次出现的起始位置；失败返回 0
int BF(char S[], char T[], int n, int m) {
    int i = 1, j = 1;                 // i 指向主串当前比较位置，j 指向模式串当前比较位置
    while (i <= n && j <= m) {        // 两个都要判：j>m 是成功，i>n 是失败
        if (S[i] == T[j]) {
            i++;                      // 本对字符相等，两个指针同步后移
            j++;
        } else {
            i = i - j + 2;            // 关键行：退回本趟起点的下一位
            j = 1;                    // 模式串从头再来，前面比对过的信息全部作废
        }
    }
    if (j > m)
        return i - m;                 // i 已停在匹配段之后一位，匹配段占 [i-m, i-1]
    else
        return 0;                     // i 越界而 j 未越界，剩余主串已不够长
}

这一行不必背，两步就能推出来。 设本趟对齐的起点是 $i_0$，也就是本趟从 S[i0] 与 T[1] 开始比。现在比到 S[i] 与 T[j] 时失配了，这说明 T[1..j-1] 与 S[i0..i-1] 已经逐个匹配上——本趟已经成功比对了 $j-1$ 对字符。于是

$$i=i_0+(j-1)⟹i_0=i-j+1$$

本趟作废，下一趟从 $i_0+1$ 开始，即 $i_{\text{new}}=i-j+2$。

写完之后花两秒自检：取 $j=1$（第一个字符就失配）代入，得 $i_{\text{new}}=i-1+2=i+1$——主串指针只前进一位，完全符合直觉。+2 还是 +1，一试就分得清。

另外两处细节也是同一种推法：

• 成功时返回 i - m。跳出循环时最后那次 i++ 已经执行完，i 停在匹配段末字符的下一位；匹配段占 $[i-m,i-1]$ 共 $m$ 格，起点自然是 i - m。这里不需要 $\pm 1$ 修正，正是因为串下标从 1 起、ch[0] 闲置。
• 判成功只能看 j > m。循环有两个出口：j > m 是模式串被完整比完（成功），i > n 是主串扫到头了（失败）。出来之后用 j > m 区分是哪一个——不能靠 i 是否越界判。失败返回 0 而不是 $-1$，是因为位置从 1 开始计，0 天然不是合法位置。

走一遍，把浪费指出来

以主串 $S=\text{"ababcabcac"}$、模式串 $T=\text{"abcac"}$ 为例（$n=10$，$m=5$）：

位置:  1 2 3 4 5 6 7 8 9 10
S   :  a b a b c a b c a c
T   :  a b c a c

趟	对齐起点 $i_0$	比较过程	本趟比较次数	结果
1	1	$S_1=a=T_1$，$S_2=b=T_2$，$S_3=a\ne T_3=c$	3	失配于 $i=3,j=3$；$i\leftarrow 3-3+2=2$
2	2	$S_2=b\ne T_1=a$	1	失配于 $i=2,j=1$；$i\leftarrow 2-1+2=3$
3	3	$S_3=a$，$S_4=b$，$S_5=c$，$S_6=a$ 均相等，$S_7=b\ne T_5=c$	5	失配于 $i=7,j=5$；$i\leftarrow 7-5+2=4$
4	4	$S_4=b\ne T_1=a$	1	$i\leftarrow 4-1+2=5$
5	5	$S_5=c\ne T_1=a$	1	$i\leftarrow 5-1+2=6$
6	6	$S_6=a$，$S_7=b$，$S_8=c$，$S_9=a$，$S_{10}=c$ 全相等	5	匹配成功，$j=6>m$，返回 $i-m=11-5=6$

共 6 趟、16 次字符比较，返回位置 6。三笔浪费全在这张表里：

第一笔，比对结果被整体丢弃。 第 3 趟比了 4 个字符才失配，这 4 个字符的信息随着 j = 1 一起作废，下一趟从零开始。

第二笔，有些趟本来就不必发生。 第 3 趟其实已经"看到"了 $S_4=b$、$S_5=c$（它们等于 $T_2$、$T_3$），而 $T_1=a$ 与这两个都不等——第 4、5 趟注定失败，却还是老老实实比了两次。

第三笔，主串指针来回走。 $i$ 走到 7 又退回 4，第 4~7 号字符被反复读取。这一笔的代价不只是时间：$i$ 会回退，就意味着必须能随机访问主串，没法边读入边匹配。

第二笔浪费最关键，因为它暴露了一个可以利用的事实：

失配时，主串中已比对过的那一段，其内容恰好等于模式串的一个前缀。 既然它等于模式串的前缀，那么"下一个可能成功的对齐位置在哪"就只由模式串自己决定，与主串是什么完全无关——可以在还没看到主串的时候就算好。

这一句就是 KMP 的全部动机：把 j = 1 换成查一张表，$i$ 也就没有回退的必要了。

复杂度：两个式子回答的是不同的问题

BF 有两个常被写在一起的式子，混用会直接算错。分清它们的办法是先问：这一趟是在哪个位置失配的。

最好情形——每趟都在模式串的第一个字符上失配。 例如 $S=\text{"aaaaaba"}$、$T=\text{"ba"}$，每趟只比 1 次就换位置。设匹配成功发生在第 $i$ 个对齐位置，则前 $i-1$ 趟各比 1 次、第 $i$ 趟比 $m$ 次，总计 $i-1+m$ 次。假定 $n-m+1$ 个起点等概率，平均比较次数

$$\sum _{i=1}^{n-m+1}\frac{1}{n-m+1}(i-1+m)=\frac{n-m}{2}+m=\frac{n+m}{2}$$

即 $O(n+m)$。

最坏情形——每趟都拖到模式串的最后一个字符才失配。 想构造这种输入，只要让模式串前 $m-1$ 位全是同一个字符、末位换一个，主串则用那个字符铺满：

$$S=\underset{n-1\text{ 个}}{\underbrace{aaaa\cdots a}}b,T=aaab(m=4)$$

取 $n=8$ 走一遍：$S=\text{"aaaaaaab"}$、$T=\text{"aaab"}$，5 趟每趟都是"前三个 $a$ 匹配上、第四个字符失配"，各比 4 次，共 20 次。一般地，趟数 $n-m+1$、每趟 $m$ 次：

$$\text{最坏比较次数}=m(n-m+1)$$

而按刚才同样的期望算法（前 $i-1$ 趟各 $m$ 次、第 $i$ 趟 $m$ 次，总 $i\cdot m$）：

$$\sum _{i=1}^{n-m+1}\frac{1}{n-m+1}(i\cdot m)=\frac{m(n-m+2)}{2}$$

两个式子的分工：$m(n-m+1)$ 回答"最多比较多少次"（全部失败，或最后一趟才成功）；$\frac{m(n-m+2)}{2}$ 回答"平均比较多少次"（成功位置在各对齐点等概率下的期望）。量级都是 $O(nm)$，但数值差一倍，问法不同不能换着用。

顺带一提：把 $m(n-m+1)$ 看成 $m$ 的函数，它在 $m\approx n/2$ 处取到最大值 $\approx n^2/4$；而当 $m\ll n$ 时退化成 $\approx mn$。两种写法都对。

最后是最容易被误解的一点：最坏 $O(nm)$ 与"实际接近 $O(n+m)$"并不矛盾。 触发最坏情形，需要"模式串的前 $m-1$ 位能被反复匹配上"，这要求主串与模式串高度自相似（大量重复字符）。而在自然文本、随机字符串这类输入上，绝大多数对齐位置在第 1 个字符就失配，每趟只比常数次，总量接近 $O(n)$。教材因此写道：BF 算法"在一般情况下，其实际的执行时间近似于 $O(n+m)$，因此至今仍被采用"。

所以 KMP 的优势是有条件的：它买到的是最坏情形的保证，以及更本质的那条——主串指针不回溯，可以边读入边匹配。至于空间，BF 是 $O(1)$、不需要任何预处理数组，这是它唯一优于 KMP 的指标。

考点速记

三条会被反复调用的结论：

1. 回退公式不背也能推：本趟起点 $i_0=i-j+1$，下一趟起点 $i_0+1=i-j+2$；拿 $j=1$ 代入即可自检。
2. 失配时主串已比对的那一段，内容恰好是模式串的一个前缀——这是与主串无关的已知量，能离线预处理。这一句就是 KMP 的全部动机。
3. BF 空间 $O(1)$、无预处理，一般文本上实际接近 $O(n+m)$，它不是被淘汰的算法；KMP 换来的是最坏保证与主串指针不回溯。

这一节在 408 真题里不单独成题，但它以另一种身份反复出现——KMP 题的错误选项。 整个「串」章的真题（下方「真题练习」）全部考 KMP，而这三道题里，每一道的干扰项都是"把 BF 的行为套到 KMP 上"：

• 2015 年那道问失配后的 $i$、$j$，选项 A 给的是 i=1, j=0——这正是 BF 的回退方式（$i$ 退回本趟起点的下一位、$j$ 归零）。
• 2019 年那道问比较次数，选项 D 给的是 15（约等于 $|T|$ 的量级）——这是完全按 BF 逐趟回退算出来的结果。

换句话说，BF 在真题里的作用是"用来跟 KMP 对照的错误答案"。把这两条行为差异记牢，等于同时排掉 KMP 题里的一半选项：

	失配时 $i$	失配时 $j$
BF	退到 $i-j+2$	归 1（或 0）
KMP	不动	$j\leftarrow next[j]$

易错：用 i 是否越界来判匹配成功。 唯一依据是 j > m。

易错：把 $m(n-m+1)$ 与 $\frac{m(n-m+2)}{2}$ 换着用。 前者答"最多"，后者答"平均"。

易错：认为 BF 已被 KMP 淘汰。 BF 空间 $O(1)$、常数小，一般文本上并不慢；KMP 赢的是最坏情形和"不回溯"。

教材出处

• 严蔚敏、李冬梅、吴伟民《数据结构（C 语言版）》（第 3 版），第 4 章 4.3.3 节「串的模式匹配算法」，印刷第 110–111 页：算法 4.1 BF 算法的算法步骤与算法描述 Index_BF，含"若不相等，指针后退重新开始匹配，从主串的下一个字符（$i=i-j+2$）起再重新和模式的第一个字符（$j=1$）比较"。
• 同书印刷第 111–112 页：BF 算法分析。最好情况取 $S=\text{"aaaaaba"}$、$T=\text{"ba"}$，平均比较次数 $\frac{1}{2}(n+m)$，时间复杂度 $O(n+m)$；最坏情况每趟不成功的匹配都发生在模式串的最后一个字符，平均比较次数 $\frac{1}{2}m(n-m+2)$，时间复杂度 $O(n\times m)$；并指出"BF 算法思路直观简明。但当匹配失败时，主串的指针 $i$ 总是回溯到 $i-j+2$ 位置，模式串的指针总是回溯到首字符位置 $j=1$，因此，算法时间复杂度高"。
• 同书印刷第 110–111 页例 4.1 与图 4.4：以 $S=\text{"abaabaabcde"}$、$T=\text{"abaabc"}$ 演示 BF 的四趟匹配。本篇逐趟表用的是 $T=\text{"abcac"}$ 的例子（第 2 版图 4.4 的例子），过程的读法相同。
• 同书印刷第 117 页：「虽然 BF 算法的时间复杂度是 $O(n\times m)$，但在一般情况下，其实际的执行时间近似于 $O(n+m)$，因此至今仍被采用」，以及 KMP 主串指针不回溯、可边读入边匹配的说明。

相关知识

串的基本概念（下标从 1 开始、ch[0] 闲置的约定，本篇代码的前提）｜ KMP 算法（把本篇指出的两笔浪费一次修掉）｜ 从 KMP 到工业级全文搜索（超纲延伸）｜ 查找的基本概念（按关键字等值比较，不覆盖字符串模式匹配）

相关文章

• 串的基本概念
• KMP 算法
• 拓展：从 KMP 到工业级全文搜索

交互体验

前往完整可视化页面 →

真题练习