Skip to content

Commit 6ab06b4

Browse files
committed
Update 01.String-Brute-Force.md
1 parent 2969ced commit 6ab06b4

File tree

1 file changed

+8
-8
lines changed

1 file changed

+8
-8
lines changed

Contents/06.String/02.String-Single-Pattern-Matching/01.String-Brute-Force.md

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -2,17 +2,17 @@
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

0 commit comments

Comments
 (0)