【算法】Brute-Force 算法

我就是我 2023-10-07 23:07 1阅读 0赞

#### 目录 ####

*  1.概述
 *  2.代码实现

> 本文参考：  
> 《数据结构教程》第 5 版 李春葆 主编

## 1.概述 ##

（1）设有两个串 s 和 t，串 t 的定位就是要在串 s 中找到一个与 t 相等的子串。通常把 s 称为**目标串(target string)**，把 t 称为**模式串(pattern string)**，因此串定位查找也称为**模式匹配(pattern maching)**。模式匹配成功是指在目标串 s 中找到了一个模式串 t；不成功则指目标串 s 中不存在模式串 t。

（2）Brute-Force（暴力）简称为 BF 算法，也称**简单匹配算法**，采用穷举方法，其基本思路是：

*  从目标串 s = "s0s1…sn-1"的第一个字符开始和模式串 t = "t0t1…tm-1"中的第一个字符比较，若相等，则继续逐个比较后续字符；否则从目标串 s 的第二个字符开始重新与模式串 t 的第一个字符进行比较。
 *  依此类推，若从模式串 s 的第 i 个字符开始，每个字符一次和目标串 t 中的对应字符相等，则匹配成功，该算法返回位置 i（表示此时 t 的第一个字符在 s 中出现的下标）；否则，匹配失败，即 t 不是 s 的子串，算法返回 -1。

（3）例如，设目标串 s = “aaaaab”，模式串 t = “aaab”。s 的长度为 n (n = 6)，t 的长度为 m (m = 4)。BF 算法的匹配过程如下：

*  初始时，i = j = 0，在匹配过程中，当 i = j = 3 时，s\[i\] != t\[j\]，此时 i 回退为 i - j + 1 = 1，j 置为 0：

![在这里插入图片描述][3966aa2f06c0467b9af835f92b778cb4.png]

*  i = 1，j = 0，继续匹配，当 i = 4，j = 3 时，s\[i\] != t\[j\]，同理 i 回退为 i - j + 1 = 1，j 置为 0：

![在这里插入图片描述][a1abe04e520b4fdcab6e2bc8b646d961.png]

*  i = 2，j = 0，继续匹配，停止匹配时 j >= t.length()，已经匹配成功，返回 t 的第一个字符在 s 中出现的下标，即返回 i - t.length()：

![在这里插入图片描述][f7973732c6a247fe809234377378a733.png]

## 2.代码实现 ##

（1）BF 算法的代码实现如下：

class Solution {
        
        public int bruteForce(String s, String t) {
        
            //定义分别指向 s 和 t 的双指针
            int i = 0;
            int j = 0;
            while (i < s.length() && j < t.length()) {
        
                if (s.charAt(i) == t.charAt(j)) {
        
                    //依次比较后续的两个字符，故 i 和 j 均向后移动
                    i++;
                    j++;
                } else {
        
                    // i 回退
                    i = i - j + 1;
                    //子串从头开始匹配，即j 重新指向 t 的首字符
                    j = 0;
                }
            }
            if (j >= t.length()) {
        
                // j >= t.length() 表示 t 是 s 的子串，此时返回 t 的第一个字符在 s 中出现的下标
                return i - t.length();
            } else {
        
                //模式匹配失败，返回 -1
                return -1;
            }
        }
    }

（2）BF 算法简单且易于理解，但**效率不高**，主要原因是主串指针 i 在若干个字符比较相等后，若有一个字符比较不相等，就需要回溯 (i = i - j + 1)。该算法在最好情况下的时间复杂度为 O(m)，即主串的前 m 个字符正好等于模式串的 m 个字符。在最坏情况下的时间复杂度为 O(n \* m)。可以证明其平均时间复杂度也是 O(n \* m)，也就是说，**该算法的平均时间性能接近最坏的情况**。有关 BF 算法的改进可参考[【算法】KMP 算法][KMP]这篇文章。

[3966aa2f06c0467b9af835f92b778cb4.png]: https://img-blog.csdnimg.cn/3966aa2f06c0467b9af835f92b778cb4.png
[a1abe04e520b4fdcab6e2bc8b646d961.png]: https://img-blog.csdnimg.cn/a1abe04e520b4fdcab6e2bc8b646d961.png
[f7973732c6a247fe809234377378a733.png]: https://img-blog.csdnimg.cn/f7973732c6a247fe809234377378a733.png
[KMP]: https://blog.csdn.net/weixin_43004044/article/details/128839508