Update 01.String-Brute-Force.md

itcharge · itcharge · commit f593f946ab95 · 2022-11-03T17:56:28.000+08:00
diff --git a/Contents/06.String/02.String-Single-Pattern-Matching/01.String-Brute-Force.md b/Contents/06.String/02.String-Single-Pattern-Matching/01.String-Brute-Force.md
@@ -1,18 +1,20 @@
-## 1. BF 算法介绍
+## 1. Brute Force 算法介绍
 
-BF 算法的全称是 **「Brute Force 算法」**，中文意思是暴力匹配算法，也可以叫做朴素匹配算法。
+> **Brute Force 算法**：简称为 BF 算法。中文意思是暴力匹配算法，也可以叫做朴素匹配算法。
+>
+> - **BF 算法思想**：对于给定文本串 `T` 与模式串 `p`，从文本串的第一个字符开始与模式串 `p` 的第一个字符进行比较，如果相等，则继续逐个比较后续字符，否则从文本串 `T` 的第二个字符起重新和模式串 `p` 进行比较。依次类推，直到模式串 `p` 中每个字符依次与文本串 `T` 的一个连续子串相等，则模式匹配成功。否则模式匹配失败。
 
-> **BF 算法思想**：对于给定文本串 `T` 与模式串 `p`，从文本串的第一个字符开始与模式串 `p` 的第一个字符进行比较，如果相等，则继续逐个比较后续字符，否则从文本串 `T` 的第二个字符起重新和模式串 `p` 进行比较。依次类推，直到模式串 `p` 中每个字符依次与文本串 `T` 的一个连续子串相等，则模式匹配成功。否则模式匹配失败。
+![](https://qcdn.itcharge.cn/images/20220205003716.png)
 
-## 2. BF 算法步骤
+## 2. Brute Force 算法步骤
 
-- 对于给定的文本串 `T` 与模式串 `p`，求出文本串 `T` 的长度为 `n`，模式串 `p` 的长度为 `m`。
-- 同时遍历文本串 `T` 和模式串 `p`，先将 `T[0]` 与 `p[0]` 进行比较。
-- 如果相等，则继续比较 `T[1]` 和 `p[1]`。以此类推，一直到模式串 `p` 的末尾 `p[m - 1]` 为止。
-- 如果不相等，则将文本串 `T` 移动到上次匹配开始位置的下一个字符位置，模式串 `p` 则回退到开始位置，再依次进行比较。
-- 当遍历完文本串 `T` 或者模式串 `p` 的时候停止搜索。
+1. 对于给定的文本串 `T` 与模式串 `p`，求出文本串 `T` 的长度为 `n`，模式串 `p` 的长度为 `m`。
+2. 同时遍历文本串 `T` 和模式串 `p`，先将 `T[0]` 与 `p[0]` 进行比较。
+   1. 如果相等，则继续比较 `T[1]` 和 `p[1]`。以此类推，一直到模式串 `p` 的末尾 `p[m - 1]` 为止。
+   2. 如果不相等，则将文本串 `T` 移动到上次匹配开始位置的下一个字符位置，模式串 `p` 则回退到开始位置，再依次进行比较。
+3. 当遍历完文本串 `T` 或者模式串 `p` 的时候停止搜索。
 
-## 3. BF 算法代码实现
+## 3. Brute Force 算法代码实现
 
 ```Python
 def bruteForce(T: str, p: str) -> int:
@@ -33,15 +35,15 @@ def bruteForce(T: str, p: str) -> int:
         return -1                   # 匹配失败，返回 -1
 ```
 
-## 4. BF 算法分析
+## 4. Brute Force 算法分析
 
 BF 算法非常简单，容易理解，但其效率很低。主要是因为在匹配过程中可能会出现回溯：当遇到一对字符不同时，模式串 `p` 直接回到开始位置，文本串也回到匹配开始位置的下一个位置，再重新开始比较。
 
-在回溯之后，文本串和模式串中一些部分的比较是没有必要的。由于这种操作策略，导致 BF 算法的效率很低。最坏情况是每一趟比较都在模式串的最后遇到了字符不匹配的情况，每轮比较需要进行 `m` 次字符对比，总共需要进行 `n - m + 1` 轮比较，总的比较次数为 `m * (n - m + 1) `。所以 BF 算法的最坏时间复杂度为 $O(m * n)$。
+在回溯之后，文本串和模式串中一些部分的比较是没有必要的。由于这种操作策略，导致 BF 算法的效率很低。最坏情况是每一趟比较都在模式串的最后遇到了字符不匹配的情况，每轮比较需要进行 `m` 次字符对比，总共需要进行 `n - m + 1` 轮比较，总的比较次数为 `m * (n - m + 1) `。所以 BF 算法的最坏时间复杂度为 $O(m \times n)$。
 
 在最理想的情况下（第一次匹配直接匹配成功），BF 算法的最佳时间复杂度是 $O(m)$。
 
-在一般情况下，根据等概率原则，平均搜索次数为 $\frac{(n + m)}{2}$，所以 BF 算法的平均时间复杂度为 $O(n + m)$。
+在一般情况下，根据等概率原则，平均搜索次数为 $\frac{(n + m)}{2}$，所以 Brute Force 算法的平均时间复杂度为 $O(n + m)$。
 
 ## 参考资料
 
