Update 04.String-Boyer-Moore.md

itcharge · itcharge · commit fa18ee2b77d3 · 2022-11-03T17:56:40.000+08:00
diff --git a/Contents/06.String/02.String-Single-Pattern-Matching/04.String-Boyer-Moore.md b/Contents/06.String/02.String-Single-Pattern-Matching/04.String-Boyer-Moore.md
@@ -1,8 +1,8 @@
-## 1. BM 算法介绍
+## 1. Boyer Moore 算法介绍
 
-BM 算法的全称叫做 **「Boyer Moore 算法」**，是由它的两位发明者 Robert S. Boyer 和 J Strother Moore 的名字来命名的。BM 算法是他们在 1977 年提出的高效字符串搜索算法。在实际应用中，比 KMP 算法要快 3~5 倍。
-
-> **BM 算法思想**：对于给定文本串 `T` 与模式串 `p`，先对模式串 `p` 进行预处理。然后在匹配的过程中，当发现文本串 `T` 的某个字符与模式串 `p` 不匹配的时候，根据启发策略，能够直接尽可能地跳过一些无法匹配的情况，将模式串多向后滑动几位。
+> **Boyer Moore 算法**：简称为 BM 算法，是由它的两位发明者 Robert S. Boyer 和 J Strother Moore 的名字来命名的。BM 算法是他们在 1977 年提出的高效字符串搜索算法。在实际应用中，比 KMP 算法要快 3~5 倍。
+>
+> - **BM 算法思想**：对于给定文本串 `T` 与模式串 `p`，先对模式串 `p` 进行预处理。然后在匹配的过程中，当发现文本串 `T` 的某个字符与模式串 `p` 不匹配的时候，根据启发策略，能够直接尽可能地跳过一些无法匹配的情况，将模式串多向后滑动几位。
 
 BM 算法的精髓在于使用了两种不同的启发策略来计算后移位数：**「坏字符规则（The Bad Character Rule）」** 和 **「好后缀规则（The Good Suffix Shift Rule）」**。
 
@@ -12,7 +12,7 @@ BM 算法的精髓在于使用了两种不同的启发策略来计算后移位
 
 下面我们来讲解一下 BF 算法中的两种不同启发策略：「坏字符规则」和「好后缀规则」。
 
-## 2. BM 算法启发策略
+## 2. Boyer Moore 算法启发策略
 
 ### 2.1 坏字符规则
 
@@ -56,7 +56,7 @@ BM 算法的精髓在于使用了两种不同的启发策略来计算后移位
 
 ![](https://qcdn.itcharge.cn/images/20220128162651.png)
 
-## 3. BM 算法匹配过程示例
+## 3. Boyer Moore 算法匹配过程示例
 
 下面我们根据  J Strother Moore 教授给出的例子，先来介绍一下 BF 算法的匹配过程，顺便加深对 **「坏字符规则」** 和 **「好后缀规则」** 的理解。
 
@@ -114,23 +114,22 @@ BM 算法的精髓在于使用了两种不同的启发策略来计算后移位
 
 11. 继续从模式串的尾部开始逐位比较，发现模式串全部匹配，于是搜索结束，返回模式串在文本串中的位置。
 
-## 4. BM 算法步骤
+## 4. Boyer Moore 算法步骤
 
 整个 BM 算法步骤描述如下：
 
-- 计算出文本串 `T` 的长度为 `n`，模式串 `p` 的长度为 `m`。
-
-- 先对模式串 `p` 进行预处理，生成坏字符位置表 `bc_table` 和好后缀规则后移位数表 `gs_talbe`。
-- 将模式串 `p` 的头部与文本串 `T` 对齐，将 `i` 指向文本串开始位置，即 `i = 0`。`j` 指向模式串末尾位置，即 `j = m - 1`，然后从模式串末尾位置开始进行逐位比较。
-  - 如果文本串对应位置 `T[i + j]` 上的字符与 `p[j]` 相同，则继续比较前一位字符。
-    - 如果模式串全部匹配完毕，则返回模式串 `p` 在文本串中的开始位置 `i`。
-  - 如果文本串对应位置 `T[i + j]` 上的字符与 `p[j]` 不相同，则：
-    - 根据坏字符位置表计算出在「坏字符规则」下的移动距离 `bad_move`。
-    - 根据好后缀规则后移位数表计算出在「好后缀规则」下的移动距离 `good_mode`。
-    - 取两种移动距离的最大值，然后对模式串进行移动，即 `i += max(bad_move, good_move)`。
-- 如果移动到末尾也没有找到匹配情况，则返回 `-1`。
+1. 计算出文本串 `T` 的长度为 `n`，模式串 `p` 的长度为 `m`。
+2. 先对模式串 `p` 进行预处理，生成坏字符位置表 `bc_table` 和好后缀规则后移位数表 `gs_talbe`。
+3. 将模式串 `p` 的头部与文本串 `T` 对齐，将 `i` 指向文本串开始位置，即 `i = 0`。`j` 指向模式串末尾位置，即 `j = m - 1`，然后从模式串末尾位置开始进行逐位比较。
+   1. 如果文本串对应位置 `T[i + j]` 上的字符与 `p[j]` 相同，则继续比较前一位字符。
+      1. 如果模式串全部匹配完毕，则返回模式串 `p` 在文本串中的开始位置 `i`。
+   2. 如果文本串对应位置 `T[i + j]` 上的字符与 `p[j]` 不相同，则：
+      1. 根据坏字符位置表计算出在「坏字符规则」下的移动距离 `bad_move`。
+      2. 根据好后缀规则后移位数表计算出在「好后缀规则」下的移动距离 `good_mode`。
+      3. 取两种移动距离的最大值，然后对模式串进行移动，即 `i += max(bad_move, good_move)`。
+4. 如果移动到末尾也没有找到匹配情况，则返回 `-1`。
 
-## 5. BM 算法代码实现
+## 5. Boyer Moore 算法代码实现
 
 BM 算法的匹配过程实现起来并不是很难，而整个算法实现的难点在于预处理阶段的「生成坏字符位置表」和「生成好后缀规则后移位数表」这两步上。尤其是「生成好后缀规则后移位数表」，实现起来十分复杂。下面我们一一进行讲解。
 
@@ -219,7 +218,7 @@ def generageGoodSuffixList(p: str):
     return gs_list
 ```
 
-### 5.3 BM 算法整体代码实现
+### 5.3 Boyer Moore 算法整体代码实现
 
 ```Python
 # BM 匹配算法
@@ -291,7 +290,7 @@ print(boyerMoore("abbcfdddbddcaddebc", "aaaaa"))
 print(boyerMoore("", ""))
 ```
 
-## 6. BM 算法分析
+## 6. Boyer Moore 算法分析
 
 - BM 算法在预处理阶段的时间复杂度为 $O(n + \sigma)$，其中 $\sigma$ 是字符集的大小。
 - BM 算法在搜索阶段最好情况是每次匹配时，模式串 `p` 中不存在与文本串 `T` 中第一个匹配的字符。这时的时间复杂度为 $O(n / m)$。
