File tree Expand file tree Collapse file tree 1 file changed +8
-8
lines changed
Contents/06.String/02.String-Single-Pattern-Matching Expand file tree Collapse file tree 1 file changed +8
-8
lines changed Original file line number Diff line number Diff line change 22
33> ** Brute Force 算法** :简称为 BF 算法。中文意思是暴力匹配算法,也可以叫做朴素匹配算法。
44>
5- > - ** BF 算法思想** :对于给定文本串 ` T ` 与模式串 ` p ` ,从文本串的第一个字符开始与模式串 ` p ` 的第一个字符进行比较,如果相等,则继续逐个比较后续字符,否则从文本串 ` T ` 的第二个字符起重新和模式串 ` p ` 进行比较。依次类推,直到模式串 ` p ` 中每个字符依次与文本串 ` T ` 的一个连续子串相等,则模式匹配成功。否则模式匹配失败。
5+ > - ** BF 算法思想** :对于给定文本串 $T$ 与模式串 $p$ ,从文本串的第一个字符开始与模式串 $p$ 的第一个字符进行比较,如果相等,则继续逐个比较后续字符,否则从文本串 $T$ 的第二个字符起重新和模式串 $p$ 进行比较。依次类推,直到模式串 $p$ 中每个字符依次与文本串 $T$ 的一个连续子串相等,则模式匹配成功。否则模式匹配失败。
66
77![ ] ( https://qcdn.itcharge.cn/images/20220205003716.png )
88
99## 2. Brute Force 算法步骤
1010
11- 1 . 对于给定的文本串 ` T ` 与模式串 ` p ` ,求出文本串 ` T ` 的长度为 ` n ` ,模式串 ` p ` 的长度为 ` m ` 。
12- 2 . 同时遍历文本串 ` T ` 和模式串 ` p ` ,先将 ` T[0] ` 与 ` p[0] ` 进行比较。
13- 1 . 如果相等,则继续比较 ` T[1] ` 和 ` p[1] ` 。以此类推,一直到模式串 ` p ` 的末尾 ` p[m - 1] ` 为止。
14- 2 . 如果不相等,则将文本串 ` T ` 移动到上次匹配开始位置的下一个字符位置,模式串 ` p ` 则回退到开始位置,再依次进行比较。
15- 3 . 当遍历完文本串 ` T ` 或者模式串 ` p ` 的时候停止搜索。
11+ 1 . 对于给定的文本串 $T$ 与模式串 $p$ ,求出文本串 $T$ 的长度为 $n$ ,模式串 $p$ 的长度为 $m$ 。
12+ 2 . 同时遍历文本串 $T$ 和模式串 $p$ ,先将 $ T[ 0] $ 与 $ p[ 0] $ 进行比较。
13+ 1 . 如果相等,则继续比较 $ T[ 1] $ 和 $ p[ 1] $ 。以此类推,一直到模式串 $p$ 的末尾 $ p[ m - 1] $ 为止。
14+ 2 . 如果不相等,则将文本串 $T$ 移动到上次匹配开始位置的下一个字符位置,模式串 $p$ 则回退到开始位置,再依次进行比较。
15+ 3 . 当遍历完文本串 $T$ 或者模式串 $p$ 的时候停止搜索。
1616
1717## 3. Brute Force 算法代码实现
1818
@@ -37,9 +37,9 @@ def bruteForce(T: str, p: str) -> int:
3737
3838## 4. Brute Force 算法分析
3939
40- BF 算法非常简单,容易理解,但其效率很低。主要是因为在匹配过程中可能会出现回溯:当遇到一对字符不同时,模式串 ` p ` 直接回到开始位置,文本串也回到匹配开始位置的下一个位置,再重新开始比较。
40+ BF 算法非常简单,容易理解,但其效率很低。主要是因为在匹配过程中可能会出现回溯:当遇到一对字符不同时,模式串 $p$ 直接回到开始位置,文本串也回到匹配开始位置的下一个位置,再重新开始比较。
4141
42- 在回溯之后,文本串和模式串中一些部分的比较是没有必要的。由于这种操作策略,导致 BF 算法的效率很低。最坏情况是每一趟比较都在模式串的最后遇到了字符不匹配的情况,每轮比较需要进行 ` m ` 次字符对比,总共需要进行 ` n - m + 1 ` 轮比较,总的比较次数为 ` m * (n - m + 1) ` 。所以 BF 算法的最坏时间复杂度为 $O(m \times n)$。
42+ 在回溯之后,文本串和模式串中一些部分的比较是没有必要的。由于这种操作策略,导致 BF 算法的效率很低。最坏情况是每一趟比较都在模式串的最后遇到了字符不匹配的情况,每轮比较需要进行 $m$ 次字符对比,总共需要进行 $ n - m + 1$ 轮比较,总的比较次数为 $m \times (n - m + 1) $ 。所以 BF 算法的最坏时间复杂度为 $O(m \times n)$。
4343
4444在最理想的情况下(第一次匹配直接匹配成功),BF 算法的最佳时间复杂度是 $O(m)$。
4545
You can’t perform that action at this time.
0 commit comments