01. Brute Force 算法
01. Brute Force 算法
1. Brute Force 算法介绍
Brute Force 算法:简称为 BF 算法。中文意思是暴力匹配算法,也可以叫做朴素匹配算法。
- BF 算法思想:对于给定文本串
与模式串 ,从文本串的第一个字符开始与模式串 的第一个字符进行比较,如果相等,则继续逐个比较后续字符,否则从文本串 的第二个字符起重新和模式串 进行比较。依次类推,直到模式串 中每个字符依次与文本串 的一个连续子串相等,则模式匹配成功。否则模式匹配失败。
2. Brute Force 算法步骤
- 对于给定的文本串
与模式串 ,求出文本串 的长度为 ,模式串 的长度为 。 - 同时遍历文本串
和模式串 ,先将 与 进行比较。- 如果相等,则继续比较
和 。以此类推,一直到模式串 的末尾 为止。 - 如果不相等,则将文本串
移动到上次匹配开始位置的下一个字符位置,模式串 则回退到开始位置,再依次进行比较。
- 如果相等,则继续比较
- 当遍历完文本串
或者模式串 的时候停止搜索。
3. Brute Force 算法代码实现
def bruteForce(T: str, p: str) -> int:
n, m = len(T), len(p)
i, j = 0, 0 # i 表示文本串 T 的当前位置,j 表示模式串 p 的当前位置
while i < n and j < m: # i 或 j 其中一个到达尾部时停止搜索
if T[i] == p[j]: # 如果相等,则继续进行下一个字符匹配
i += 1
j += 1
else:
i = i - (j - 1) # 如果匹配失败则将 i 移动到上次匹配开始位置的下一个位置
j = 0 # 匹配失败 j 回退到模式串开始位置
if j == m:
return i - j # 匹配成功,返回匹配的开始位置
else:
return -1 # 匹配失败,返回 -1
4. Brute Force 算法分析
BF 算法非常简单,容易理解,但其效率很低。主要是因为在匹配过程中可能会出现回溯:当遇到一对字符不同时,模式串
在回溯之后,文本串和模式串中一些部分的比较是没有必要的。由于这种操作策略,导致 BF 算法的效率很低。最坏情况是每一趟比较都在模式串的最后遇到了字符不匹配的情况,每轮比较需要进行
在最理想的情况下(第一次匹配直接匹配成功),BF 算法的最佳时间复杂度是
在一般情况下,根据等概率原则,平均搜索次数为
参考资料
- 【书籍】数据结构与算法 Python 语言描述 - 裘宗燕 著
- 【文章】动画:什么是 BF 算法 ?- 吴师兄学编程
- 【文章】BF 算法(普通模式匹配算法)及 C 语言实现 - 数据结构与算法教程
- 【文章】字符串匹配基础(上)- 数据结构与算法之美 - 极客时间
来源:https://github.com/itcharge/LeetCode-Py