本文参考：《数据结构教程》第 5 版 李春葆 主编
更多数据结构与算法的相关知识可以查看数据结构与算法这一专栏。

有关字符串模式匹配的其它算法：
【算法】Boyer-Moore 算法
【算法】KMP 算法
【算法】Rabin-Karp 算法

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 = 1，j 置为 0：

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

• i = 2，j = 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)，也就是说，该算法的平均时间性能接近最坏的情况。有关 BF 算法的改进可参考【算法】KMP 算法这篇文章。