BF算法是暴力穷举所有对齐位置逐字符匹配的字符串搜索方法，Java中用char[]实现可避免charAt()开销；时间复杂度O(nm)，最坏情况下重复比较冗余，理解其回溯本质有助于掌握KMP等高效算法。
BF（Brute Force）算法是最基础的字符串匹配方法，核心思想是暴力穷举所有可能的对齐位置，逐字符比较主串与模式串。在 Java 中用数组实现时，可将字符串转为 char[]，直接通过下标访问提升效率，避免频繁调用 String.charAt() 的开销。
用 char 数组实现 BF 匹配的核心逻辑
假设主串为 s，模式串为 p，长度分别为 n 和 m。需检查从位置 i = 0 到 i = n - m 的每个起始点：
- 对每个
i，令j = 0，循环比较s[i+j]与p[j] - 若某次
s[i+j] != p[j]，则本次失配，i加 1，重试 - 若
j成功走到m（即完成全部m次匹配），返回i作为首次匹配起始索引 - 若所有
i都未匹配成功，返回-1
示例代码片段：
public static int bfSearch(char[] s, char[] p) {
int n = s.length, m = p.length;
if (m == 0) return 0;
if (n < m) return -1;
<pre class='brush:java;toolbar:false;'>for (int i = 0; i <= n - m; i++) {
int j = 0;
while (j < m && s[i + j] == p[j]) {
j++;
}
if (j == m) return i;
}
return -1;}
立即学习“Java免费学习笔记（深入）”；
最坏情况的典型输入与发生条件
BF 算法最坏时间复杂度为 O(n × m)，出现在每次尝试都几乎比到末尾才失配的情形。典型构造方式是：
- 主串全为相同字符，如
"aaaaaa" - 模式串前
m−1位与主串一致，但最后一位不同，如"aaab" - 此时对每个合法起始位置
i（共n−m+1个），都要执行m−1次成功比较 + 1 次失败比较，总比较次数 ≈(n−m+1) × m
例如：s = "aaaaaaaa", p = "aaab"（n=8, m=4），需检查 i=0~5 共 6 个位置，每轮比 4 次（前三次成功，第四次失败），共 24 次字符比较。
性能瓶颈与优化提示
BF 的低效源于“已知失配信息未被复用”——前面比过的字符不参与后续决策。这正是 KMP、BM 等算法改进的出发点：
- 不要在 Java 中对长文本用 BF 做生产级匹配；仅适合教学理解或极短字符串（如配置项名、命令关键词）
- 若坚持用数组实现，注意边界检查：避免
i+j >= s.length，循环条件中已隐含控制 - 可加简单预处理，如先检查
p[0]是否在s中存在，快速排除（但不改变最坏复杂度） - 实际开发中优先使用
String.indexOf()，其底层在 OpenJDK 中已针对不同长度采用混合策略（含 BM 变种），远优于手写 BF
小结：理解价值大于实用价值
BF 算法虽慢，却是字符串匹配的起点。用数组实现能清晰暴露其“回溯式扫描”的本质，也便于观察最坏情形下重复比较的冗余性。掌握它，是为了更好理解 KMP 中的 next 数组为何能跳过无效位移——那才是工业级匹配的基石。
