更新文章目录结构

itcharge · Jan 29, 2022 · a65cfeb · a65cfeb
1 parent 6bb273a
commit a65cfeb
Show file tree

Hide file tree

Showing 11 changed files with 295 additions and 280 deletions.
diff --git a/Assets/Origins/README-Catalogue-List.md b/Assets/Origins/README-Catalogue-List.md
@@ -82,10 +82,12 @@
   - [字符串基础知识](https://github.com/itcharge/LeetCode-Py/blob/main/Contents/06.String/01.String-Basic/01.String-Basic.md)
   - [字符串经典题目](https://github.com/itcharge/LeetCode-Py/blob/main/Contents/06.String/01.String-Basic/10.String-Basic-List.md)
 - 单模式串匹配算法
-  - [BF 算法和 RK 算法](https://github.com/itcharge/LeetCode-Py/blob/main/Contents/06.String/02.String-Single-Pattern-Matching/01.String-BF-RK.md)
-  - ~~[KMP 算法](https://github.com/itcharge/LeetCode-Py/blob/main/Contents/06.String/02.String-Single-Pattern-Matching/02.String-KMP.md)~~
-  - [BM 算法](https://github.com/itcharge/LeetCode-Py/blob/main/Contents/06.String/02.String-Single-Pattern-Matching/03.String-BM.md)
-  - [Horspool 算法 和 Sunday 算法](https://github.com/itcharge/LeetCode-Py/blob/main/Contents/06.String/02.String-Single-Pattern-Matching/04.String-Horspool-Sunday.md)
+  - [Brute Force 算法](https://github.com/itcharge/LeetCode-Py/blob/main/Contents/06.String/02.String-Single-Pattern-Matching/01.String-Brute-Force.md)
+  - [Rabin Karp 算法](https://github.com/itcharge/LeetCode-Py/blob/main/Contents/06.String/02.String-Single-Pattern-Matching/02.String-Rabin-Karp.md)
+  - ~~[KMP 算法](https://github.com/itcharge/LeetCode-Py/blob/main/Contents/06.String/02.String-Single-Pattern-Matching/03.String-KMP.md)~~
+  - [Boyer Moore 算法](https://github.com/itcharge/LeetCode-Py/blob/main/Contents/06.String/02.String-Single-Pattern-Matching/04.String-Boyer-Moore.md)
+  - [Horspool 算法](https://github.com/itcharge/LeetCode-Py/blob/main/Contents/06.String/02.String-Single-Pattern-Matching/05.String-Horspool.md)
+  - [Sunday 算法](https://github.com/itcharge/LeetCode-Py/blob/main/Contents/06.String/02.String-Single-Pattern-Matching/06.String-Sunday.md)
   - [单模式串匹配题目](https://github.com/itcharge/LeetCode-Py/blob/main/Contents/06.String/02.String-Single-Pattern-Matching/10.String-Single-Pattern-Matching-List.md)
 - 多模式串匹配
   - 字典树

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
@@ -0,0 +1,51 @@
+## 1. BF 算法介绍
+
+BF 算法的全称是 **「Brute Force 算法」**，中文意思是暴力匹配算法，也可以叫做朴素匹配算法。
+
+> **BF 算法思想**：对于给定文本串 `T` 与模式串 `p`，从文本串的第一个字符开始与模式串 `p` 的第一个字符进行比较，如果相等，则继续逐个比较后续字符，否则从文本串 `T` 的第二个字符起重新和模式串 `p` 进行比较。依次类推，直到模式串 `p` 中每个字符依次与文本串 `T` 的一个连续子串相等，则模式匹配成功。否则模式匹配失败。
+
+## 2. BF 算法步骤
+
+- 对于给定的文本串 `T` 与模式串 `p`，求出文本串 `T` 的长度为 `n`，模式串 `p` 的长度为 `m`。
+- 同时遍历文本串 `T` 和模式串 `p`，先将 `T[0]` 与 `p[0]` 进行比较。
+- 如果相等，则继续比较 `T[1]` 和 `p[1]`。以此类推，一直到模式串 `p` 的末尾 `p[m - 1]` 为止。
+- 如果不相等，则将文本串 `T` 移动到上次匹配开始位置的下一个字符位置，模式串 `p` 则回退到开始位置，再依次进行比较。
+- 当遍历完文本串 `T` 或者模式串 `p` 的时候停止搜索。
+
+## 3. BF 算法代码实现
+
+```Python
+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. BF 算法分析
+
+BF 算法非常简单，容易理解，但其效率很低。主要是因为在匹配过程中可能会出现回溯：当遇到一对字符不同时，模式串 `p` 直接回到开始位置，文本串也回到匹配开始位置的下一个位置，再重新开始比较。
+
+在回溯之后，文本串和模式串中一些部分的比较是没有必要的。由于这种操作策略，导致 BF 算法的效率很低。最坏情况是每一趟比较都在模式串的最后遇到了字符不匹配的情况，每轮比较需要进行 `m` 次字符对比，总共需要进行 `n - m + 1` 轮比较，总的比较次数为 `m * (n - m + 1) `。所以 BF 算法的最坏时间复杂度为 $O(m * n)$。
+
+在最理想的情况下（第一次匹配直接匹配成功），BF 算法的最佳时间复杂度是 $O(m)$。
+
+在一般情况下，根据等概率原则，平均搜索次数为 $\frac{(n + m)}{2}$，所以 BF 算法的平均时间复杂度为 $O(n + m)$。
+
+## 参考资料
+
+- 【书籍】数据结构与算法 Python 语言描述 - 裘宗燕 著
+- 【文章】[动画：什么是 BF 算法 ？- 吴师兄学编程](https://www.cxyxiaowu.com/560.html)
+- 【文章】[BF 算法（普通模式匹配算法）及 C 语言实现 - 数据结构与算法教程](http://data.biancheng.net/view/12.html)
+- 【文章】[字符串匹配基础（上）- 数据结构与算法之美 - 极客时间](https://time.geekbang.org/column/article/71187)
diff --git a/Contents/06.String/02.String-Single-Pattern-Matching/02.String-KMP.md b/Contents/06.String/02.String-Single-Pattern-Matching/02.String-KMP.md
diff --git a/...ingle-Pattern-Matching/01.String-BF-RK.md → ...-Pattern-Matching/02.String-Rabin-Karp.md b/...ingle-Pattern-Matching/01.String-BF-RK.md → ...-Pattern-Matching/02.String-Rabin-Karp.md
@@ -1,63 +1,12 @@
-## 1. BF 算法（Brute Force）
+## 1. RK 算法介绍
 
-BF 是 Brute Force 的缩写，中文意思是暴力匹配算法，也可以叫做朴素匹配算法。
-
-### 1.1 BF 算法思想
-
-> **BF 算法思想**：对于给定文本串 `T` 与模式串 `p`，从文本串的第一个字符开始与模式串 `p` 的第一个字符进行比较，如果相等，则继续逐个比较后续字符，否则从文本串 `T` 的第二个字符起重新和模式串 `p` 进行比较。依次类推，直到模式串 `p` 中每个字符依次与文本串 `T` 的一个连续子串相等，则模式匹配成功。否则模式匹配失败。
-
-### 1.2 BF 算法步骤
-
-- 对于给定的文本串 `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.3 BF 算法动画演示
-
-### 1.4 BF 算法代码实现
-
-```Python
-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
-```
-
-### 1.5 BF 算法分析
-
-BF 算法非常简单，容易理解，但其效率很低。主要是因为在匹配过程中可能会出现回溯：当遇到一对字符不同时，模式串 `p` 直接回到开始位置，文本串也回到匹配开始位置的下一个位置，再重新开始比较。
-
-在回溯之后，文本串和模式串中一些部分的比较是没有必要的。由于这种操作策略，导致 BF 算法的效率很低。最坏情况是每一趟比较都在模式串的最后遇到了字符不匹配的情况，每轮比较需要进行 `m` 次字符对比，总共需要进行 `n - m + 1` 轮比较，总的比较次数为 `m * (n - m + 1) `。所以 BF 算法的最坏时间复杂度为 $O(m * n)$。
-
-在最理想的情况下（第一次匹配直接匹配成功），BF 算法的最佳时间复杂度是 $O(m)$。
-
-在一般情况下，根据等概率原则，平均搜索次数为 $\frac{(n + m)}{2}$，所以 BF 算法的平均时间复杂度为 $O(n + m)$。
-
-## 2. RK 算法（Rabin Karp）
-
-RK 算法的全称叫 **「Rabin-Karp 算法」**，是由它的两位发明者 Michael Oser Rabin 和 Richard Manning Karp 的名字来命名的。RK 算法是他们在 1987 年提出的、使用哈希函数以在文本中搜寻单个模式串的字符串搜索算法。
-
-### 2.1 RK 算法思想
+RK 算法的全称叫 **「Rabin Karp 算法」**，是由它的两位发明者 Michael Oser Rabin 和 Richard Manning Karp 的名字来命名的。RK 算法是他们在 1987 年提出的、使用哈希函数以在文本中搜寻单个模式串的字符串搜索算法。
 
 > **RK 算法思想**：对于给定文本串 `T` 与模式串 `p`，通过滚动哈希算快速筛选出与模式串 `p` 不匹配的文本位置，然后在其余位置继续检查匹配项。
 
-### 2.2 RK 算法步骤
+## 2. RK 算法步骤
 
-#### 2.2.1 RK 算法整体步骤
+### 2.1 RK 算法整体步骤
 
 - 对于给定的文本串 `T` 与模式串 `p`，求出文本串 `T` 的长度为 `n`，模式串 `p` 的长度为 `m`。
 - 通过滚动哈希算法求出模式串 `p` 的哈希值 `hash_p`。
@@ -69,7 +18,7 @@ RK 算法的全称叫 **「Rabin-Karp 算法」**，是由它的两位发明者
     - 如果当前子串和模式串的每个字符不相等，则说明两者不匹配，继续向后匹配。
 - 比较到末尾，如果仍未成功匹配，则说明文本串 `T` 中不包含模式串 `p`，方法返回 `-1`。
 
-#### 2.2.2 滚动哈希算法
+### 2.2 滚动哈希算法
 
 实现 RK 算法中一个重要步骤是 **「滚动哈希算法」**，通过滚动哈希算法，将每次计算子串哈希值的复杂度从 $O(m)$ 降到了 $O(1)$，从而提升了整个算法效率。
 
@@ -107,9 +56,7 @@ $\begin{align} Hash(ate) &= (Hash(cat) - c \times 26 \times 26) * 26 + e \times
 
 因为哈希值过大会造成溢出，所以我们在计算过程中还要对结果取模。取模的值应该尽可能大，并且应该是质数，这样才能减少哈希碰撞的概率。
 
-### 2.3 RK 算法动画演示
-
-### 2.4 RK 算法代码实现
+## 3. RK 算法代码实现
 
 ```Python
 # T 为文本串，p 为模式串，d 为字符集的字符种类数，q 为质数
@@ -143,7 +90,7 @@ def rabinKarp(T: str, p: str, d, q) -> int:
     return -1
 ```
 
-### 2.5 RK 算法分析
+## 4. RK 算法分析
 
 RK 算法可以看做是 BF 算法的一种改进。在 BF 算法中，每一个字符都需要进行比较。而在 RK 算法中，判断模式串的哈希值与每个子串的哈希值之间是否相等的时间复杂度为 $O(1)$。总共需要比较 `n - m + 1` 个子串的哈希值，所以 RK 算法的整体时间复杂度为 $O(n)$。跟 BF 算法相比，RK 算法的效率提高了很多。
 
@@ -152,8 +99,6 @@ RK 算法可以看做是 BF 算法的一种改进。在 BF 算法中，每一个
 ## 参考资料
 
 - 【书籍】数据结构与算法 Python 语言描述 - 裘宗燕 著
-- 【文章】[动画：什么是 BF 算法 ？- 吴师兄学编程](https://www.cxyxiaowu.com/560.html)
-- 【文章】[BF 算法（普通模式匹配算法）及 C 语言实现 - 数据结构与算法教程](http://data.biancheng.net/view/12.html)
 - 【文章】[字符串匹配基础（上）- 数据结构与算法之美 - 极客时间](https://time.geekbang.org/column/article/71187)
 - 【文章】[字符串匹配算法 - Rabin Karp 算法 - coolcao 的小站](https://coolcao.com/2020/08/20/rabin-karp/)
 - 【问答】[string - Python: Rabin-Karp algorithm hashing - Stack Overflow](https://stackoverflow.com/questions/22216948/python-rabin-karp-algorithm-hashing)
diff --git a/Contents/06.String/02.String-Single-Pattern-Matching/03.String-KMP.md b/Contents/06.String/02.String-Single-Pattern-Matching/03.String-KMP.md
@@ -0,0 +1,13 @@
+## 1. KMP 算法介绍
+
+KMP 算法的全叫做 **「Knuth Morris Pratt 算法」**，是由它的三位发明者 Donald Knuth、James H. Morris、 Vaughan Pratt 的名字来命名的。KMP 算法是他们三人在 1977 年联合发表的。
+
+> **KMP 算法思想**：对于给定文本串 `T` 与模式串 `p`，对模式串 `p` 进行预处理，记录下模式串的一些信息。当发现文本串 `T` 的某个字符与模式串 `p` 不匹配的时候，可以根据已知信息，避免将指针回退到所有这些已知的字符之前。
+
+## 2. KMP 算法步骤
+
+## 3. KMP 算法代码实现
+
+## 4. KMP 算法分析
+
+## 参考资料
diff --git a/...g-Single-Pattern-Matching/03.String-BM.md → ...Pattern-Matching/04.String-Boyer-Moore.md b/...g-Single-Pattern-Matching/03.String-BM.md → ...Pattern-Matching/04.String-Boyer-Moore.md