题目
实现字符串匹配的暴力算法（Brute-Force）
信息
- 类型：问答
- 难度：⭐
考点
字符串匹配,暴力算法,循环控制
快速回答
暴力算法（Brute-Force）通过两层循环逐个比较字符：
- 外层循环遍历主串每个可能的起始位置
- 内层循环逐个比较子串字符
- 时间复杂度：O(n*m)，空间复杂度：O(1)
- 匹配成功返回起始索引，失败返回-1
原理说明
暴力算法（Brute-Force）是字符串匹配的基础方法：
1. 从主串 text 的第 i 个字符开始
2. 逐个比较子串 pattern 的每个字符
3. 若全部匹配则返回 i
4. 若中途失败，则从 i+1 位置重新开始匹配
代码示例
def brute_force(text, pattern):
n, m = len(text), len(pattern)
for i in range(n - m + 1): # 外层循环
j = 0
while j < m and text[i+j] == pattern[j]: # 内层比较
j += 1
if j == m: # 完全匹配
return i
return -1 # 未找到最佳实践
- 提前终止：当剩余主串长度小于子串时终止循环（
n - m + 1） - 边界处理：检查空子串（直接返回0）或空主串（返回-1）
- 可读性：明确变量命名（如
n主串长，m子串长）
常见错误
- 索引越界：未限制
i的范围导致i+j越界（内层需j < m保护） - 忽略空串：未处理
pattern=""的情况（应返回0） - 低效循环：外层循环误写为
range(n)（浪费计算）
扩展知识
- 应用场景：短文本匹配、算法教学基础
- 优化方向：KMP算法（利用失败信息跳转）、Boyer-Moore（从右向左比较）
- 效率对比：
- 最好情况 O(m)（首字符常失败）
- 最坏情况 O(n*m)（如 text="AAA...A"，pattern="AA...AB"）
