【算法】Brute-Force 算法

本文参考：
《数据结构教程》第 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 = "s₀s₁…s_n-1"的第一个字符开始和模式串 t = "t₀t₁…t_m-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 = 1j 置为 0：

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

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

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)也就是说该算法的平均时间性能接近最坏的情况。