Brute Force算法

基本概念

Brute Force 算法：简称为 BF 算法，也可以叫做「朴素匹配算法」。

  • Brute Force 算法核心思想：将模式串 pp 依次与文本串 TT 的每个起点对齐，从左到右逐字符比对；相等则继续，不等则把对齐起点右移一位，直到匹配成功或遍历完文本。

算法步骤

  1. 设文本串T长度为n，模式串p长度为m
  2. 设T的每个七点0…n-m依次与p对齐，逐字符比较：如果相等则继续，不相等则起点右移一位、p归零
  3. 如果某次对齐能把p的全部字符匹配完，则返回该起点；否则无解

内部实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def bruteForce(T:str,p:str)->int:
	n,m=len(T),len(p)
	i,j=0,0
	while i < n and j < m:
		if T[i]==p[j]:
			i+=1
			j+=1
		else:
			i=i-j+1
			j=0
		if j==m:
			return i-j
		else:
			return -1

复杂度分析

BF 简单直观，但因不匹配时会完全回退、重新对齐，存在大量重复比较，效率较低。

指标 复杂度 说明
最好时间复杂度 O(m) 首个起点即匹配成功
最坏时间复杂度 O(n×m) 每次都需回退，全部比较
平均时间复杂度 O(n×m) 一般情况下的复杂度
空间复杂度 O(1) 原地匹配，无需额外空间
  • 大量回溯导致重复比较，是 BF 变慢的根源。
  • 当文本或模式较长时，更应考虑 KMP、BM、Sunday 等改进算法。
    Brute Force（BF）算法通过将模式串与文本串每个可能的起点逐字符对齐比较，遇到不匹配时起点右移、模式串重头开始。该算法实现简单，空间复杂度为 O(1)，但时间复杂度较高：最好情况下为 O(m)（首位即匹配），平均和最坏情况下为 O(n×m)，适合小规模或一次性匹配场景。
  • 优点：实现简单、无需预处理、适合小规模或一次性匹配。
  • 缺点：回溯多、效率低，不适合长文本/长模式或多次匹配场景。

应用场景：