Update 01.String-Basic.md

itcharge · itcharge · commit 95e98239c519 · 2022-01-19T17:41:31.000+08:00
diff --git a/Contents/06.String/01.String-Basic/01.String-Basic.md b/Contents/06.String/01.String-Basic/01.String-Basic.md
@@ -145,33 +145,33 @@ def strcmp(str1, str2):
 
 ### 4.1 单模式串匹配问题
 
-> 单模式匹配问题：给定一个文本串 $T = t_1t_2...t_n$，再给定一个特定模式串 $p = p_1p_2...p_n$。要求从文本串 $T$ 找出特定模式串 $p$ 的所有出现位置。
+> **单模式匹配问题（Single Pattern Matching）**：给定一个文本串 $T = t_1t_2...t_n$，再给定一个特定模式串 $p = p_1p_2...p_n$。要求从文本串 $T$ 找出特定模式串 $p$ 的所有出现位置。
 
 有很多算法可以解决单模式匹配问题。而根据在文本中搜索模式串方式的不同，我们可以将单模式匹配算法分为以下几种：
 
 - **基于前缀搜索方法**：在搜索窗口内从前向后（沿着文本的正向）逐个读入文本字符，搜索窗口中文本和模式串的最长公共前缀。
-  - `Knuth-Morris-Pratt` 算法和更快的 `Shift-Or` 算法使用的就是这种方法。
+  - 著名的 `Knuth-Morris-Pratt (KMP)` 算法和更快的 `Shift-Or` 算法使用的就是这种方法。
 - **基于后缀搜索方法**：在搜索窗口内从后向前（沿着文本的反向）逐个读入文本字符，搜索窗口中文本和模式串的最长公共后缀。使用这种搜索算法可以跳过一些文本字符，从而具有亚线性的平均时间复杂度。
-  - 最著名的算法是 `Boyer-Moore` 算法、`Horspool` 算法和 `Sunday (Boyer-Moore 算法的简化)` 算法使用了这种方法。
+  - 最著名的 `Boyer-Moore` 算法，以及 `Horspool` 算法、`Sunday (Boyer-Moore 算法的简化)` 算法都使用了这种方法。
 - **基于子串搜索方法**：在搜索窗口内从后向前（沿着文本的反向）逐个读入文本字符，搜索满足「既是窗口中文本的后缀，也是模式串的子串」的最长字符串。与后缀搜索方法一样，使用这种搜索方法也具有亚线性的平均时间复杂度。这种方法的主要缺点在于需要识别模式串的所有子串，这是一个非常复杂的问题。
   - `Rabin-Karp` 算法、`Backward Dawg Matching (BDM)` 算法、`Backward Nondeterministtic Dawg Matching (BNDM)` 算法和 `Backward Oracle Matching (BOM)` 算法使用的就是这种思想。其中，`Rabin-Karp` 算法使用了基于散列的子串搜索算法。
 
 ### 4.2 多模式串匹配问题
 
-> 多模式匹配问题：给定一个文本串 $T = t_1t_2...t_n$，再给定一组模式串 $P = {p^1, p^2, ... ,p^r}$，其中每个模式串 $p^i$ 是定义在有限字母表上的字符串 $p^i = p^i_1p^i_2...p^i_n$。要求从文本串 $T$ 中找到模式串集合 $P$ 中所有模式串 $p^i$ 的所有出现位置。
+> **多模式匹配问题（Multi Pattern Matching）**：给定一个文本串 $T = t_1t_2...t_n$，再给定一组模式串 $P = {p^1, p^2, ... ,p^r}$，其中每个模式串 $p^i$ 是定义在有限字母表上的字符串 $p^i = p^i_1p^i_2...p^i_n$。要求从文本串 $T$ 中找到模式串集合 $P$ 中所有模式串 $p^i$ 的所有出现位置。
 
 模式串集合 $P$ 中的一些字符串可能是集合中其他字符串的子串、前缀、后缀，或者完全相等。解决多模式串匹配问题最简单的方法是利用「单模式串匹配算法」搜索 `r` 遍。这将导致预处理阶段的最坏时间复杂度为 $O(|P|)$，搜索阶段的最坏时间复杂度为 $O(r * n)$。
 
 如果使用「单模式串匹配算法」解决多模式匹配问题，那么根据在文本中搜索模式串方式的不同，我们也可以将多模式串匹配算法分为以下三种：
 
-- 基于前缀搜索方法：搜索从前向后（沿着文本的正向）进行，逐个读入文本字符，使用在 $P$ 上构建的自动机进行识别。对于每个文本位置，计算既是已读入文本的后缀，同时也是 $P$ 中某个模式串的前缀的最长字符串。
+- **基于前缀搜索方法**：搜索从前向后（沿着文本的正向）进行，逐个读入文本字符，使用在 $P$ 上构建的自动机进行识别。对于每个文本位置，计算既是已读入文本的后缀，同时也是 $P$ 中某个模式串的前缀的最长字符串。
   - 著名的 `Aho-Corasick Automaton (AC 自动机)` 算法、`Multiple Shift-And` 算法使用的这种方法。
-- 基于后缀搜索方法：搜索从后向前（沿着文本的反向）进行，搜索模式串的后缀。根据后缀的下一次出现位置来移动当前文本位置。这种方法可以避免读入所有的文本字符。
-  - `Commentz-Walter` 算法（`Boyer-Moore` 算法的扩展算法）、`Set Horspool` 算法（`Commentz-Walter` 算法的简化算法）、`Wu-Manber` 算法使用了这种方法。
-- 基于子串搜索方法：搜索从后向前（沿着文本的反向）进行，在模式串的长度为 $min(len(p^i))$ 的前缀中搜索子串，以此决定当前文本位置的移动。这种方法也可以避免读入所有的文本字符。
-  - `Multiple BNDM` 算法、`Set Backward Dawg Matching (SBDM)`、`Set Backwrad Oracle Matching (SBOM)` 使用了这种方法。
+- **基于后缀搜索方法**：搜索从后向前（沿着文本的反向）进行，搜索模式串的后缀。根据后缀的下一次出现位置来移动当前文本位置。这种方法可以避免读入所有的文本字符。
+  - `Commentz-Walter` 算法（`Boyer-Moore` 算法的扩展算法）、`Set Horspool` 算法（`Commentz-Walter` 算法的简化算法）、`Wu-Manber` 算法都使用了这种方法。
+- **基于子串搜索方法**：搜索从后向前（沿着文本的反向）进行，在模式串的长度为 $min(len(p^i))$ 的前缀中搜索子串，以此决定当前文本位置的移动。这种方法也可以避免读入所有的文本字符。
+  - `Multiple BNDM` 算法、`Set Backward Dawg Matching (SBDM)` 算法、`Set Backwrad Oracle Matching (SBOM)` 算法都使用了这种方法。
 
-需要注意的是，以上所介绍的多模式串匹配算法大多使用了一种基本的数据结构：**「字典树（Trie Tree）」**。著名的 **「Aho-Corasick Automaton (AC 自动机) 算法」** 就是在 `Knuth-Morris-Pratt` 算法的基础上，与「字典树（Trie Tree）」结构相结合而诞生的。而 AC 自动机算法也算是多模式串匹配算法中最有效的算法之一。
+需要注意的是，以上所介绍的多模式串匹配算法大多使用了一种基本的数据结构：**「字典树（Trie Tree）」**。著名的 **「Aho-Corasick Automaton (AC 自动机) 算法」** 就是在 `KMP` 算法的基础上，与「字典树」结构相结合而诞生的。而「AC 自动机算法」也是多模式串匹配算法中最有效的算法之一。
 
 所以学习多模式匹配算法，重点是要掌握 **「字典树」** 和 **「AC 自动机算法」** 。
 
