Appearance
朴素模式匹配（BF 算法）
为什么需要朴素模式匹配
在实际应用中，经常需要在一个长字符串（主串）中查找某个短字符串（模式串）是否出现以及出现的位置，例如文本编辑器中的"查找"功能。
朴素模式匹配（Brute-Force，简称 BF 算法）是最直观的字符串匹配方法：逐个位置尝试，逐个字符比对。它是 408 考研中理解 KMP 算法的基础，也是对比学习 KMP 优化思路的参照物。
核心思想
BF 算法的核心思路：
- 穷举所有对齐位置：将模式串依次与主串的第 1、2、3、…、n-m+1 个位置对齐
- 逐字符比较：每次对齐后，从模式串的第一个字符开始逐个比较
- 匹配失败则回溯：一旦某个字符不匹配，主串指针 i 回退，模式串指针 j 归零，从下一个对齐位置重新开始
主串 S: a b a b c a b c a c
模式 T: a b c
↑ 第1次对齐（i=1, j=1）BF 算法流程图
交互可视化
通过下方的交互动画，你可以逐步观察朴素模式匹配的执行过程：
操作详解
算法思路
设主串 S 长度为 n，模式串 T 长度为 m，用指针 i 指向主串当前比较位置，j 指向模式串当前比较位置。
cpp
// BF 算法（下标从 1 开始）
int BF(char S[], char T[], int n, int m) {
int i = 1, j = 1;
while (i <= n && j <= m) {
if (S[i] == T[j]) {
i++; // 匹配成功，两个指针同时后移
j++;
} else {
i = i - j + 2; // i 回退到本次对齐起点的下一位
j = 1; // j 归零（回到模式串开头）
}
}
if (j > m)
return i - m; // 匹配成功，返回匹配起始位置
else
return 0; // 匹配失败
}关键步骤：
- 初始化
i = 1, j = 1 - 若
S[i] == T[j]，则i++, j++，继续比较下一对字符 - 若
S[i] != T[j]，则 回溯：i = i - j + 2，j = 1 - 当
j > m时匹配成功，返回起始位置i - m
匹配过程详解
以主串 S = "ababcabcac"、模式串 T = "abcac" 为例，展示匹配过程：
| 趟数 | 对齐位置 | 比较过程 | 结果 |
|---|---|---|---|
| 第 1 趟 | i=1 | a=a, b=b, a≠c | 失败，i 回退到 2，j 归 1 |
| 第 2 趟 | i=2 | b≠a | 失败，i 回退到 3，j 归 1 |
| 第 3 趟 | i=3 | a=a, b=b, c=c, a=a, c=c | 匹配成功，返回位置 3 |
每一趟匹配失败后，主串指针 i 都要回退到本趟起始位置的下一位，模式串指针 j 回到 1，这就是 BF 算法的核心流程。
回溯机制
BF 算法效率低的根本原因在于不必要的回溯。
当 S[i] != T[j] 时，算法执行：
i = i - j + 2：主串指针回退到本趟对齐起点的下一个位置j = 1：模式串指针归零
为什么回溯是低效的？ 假设已经匹配了 j-1 个字符才失败，这意味着我们已经"看过"了主串中 j-1 个字符的信息，但回溯时完全丢弃了这些信息，从头开始比较。这些被丢弃的信息正是 KMP 算法利用 next 数组所保留的。
第 1 趟: S: a b a b c ... 匹配到第 3 个字符失败
T: a b c
↑ 失败
第 2 趟: S: a b a b c ... i 回退到 2，重新开始
T: a b c
↑ 回退后从这里开始（实际上 b≠a 显然不可能匹配）上例中第 2 趟的比较是多余的——已知 S[2] = b，而 T[1] = a，不可能匹配。KMP 算法正是通过避免这类无效回溯来提升效率。
复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n+m) | 第一趟就匹配成功，或每趟第一个字符就失败 |
| 最坏情况 | O(nm) | 每趟比较到模式串最后一个字符才失败，如 S="aaa...ab"，T="aaa...b" |
| 平均情况 | O(nm) | 一般认为接近最坏情况 |
空间复杂度：O(1)，只需要 i、j 两个辅助变量。
⭐ 考研重点：最坏情况下比较次数为 (n-m+1) * m 次。例如 S 长度为 n，T 长度为 m，且每趟都在第 m 个字符失败，则共需比较 (n-m+1) 趟，每趟比较 m 次。
考研高频考点
- ⭐ BF 算法最坏时间复杂度 O(nm) 及最坏比较次数 (n-m+1)*m（选择题/填空题高频）
- ⭐ 匹配失败时 i 的回退公式
i = i - j + 2和 j 的归零（代码填空题常考） - ⭐ BF 与 KMP 的本质区别：BF 回溯主串指针，KMP 不回溯（简答题/对比题必考）
- 给定主串和模式串，手动模拟 BF 匹配过程，写出每趟的 i、j 值（大题偶考）
- BF 算法最好情况 O(n+m) 的条件（概念题）