BF 算法

目录

BF算法

算法思路

完整代码

时间复杂度

查找所有起始位置

---

BF算法

BF算法：即暴力(Brute Force)算法，是一种模式匹配算法，将目标串 S 的第一个字符与模式串 T 的第一个字符进行匹配，若相等，则继续比较 S 的第二个字符和 T 的第二个字符；若不相等，则比较 S 的第二个字符和 T 的第一个字符，依次比较下去，直到得出最后的匹配结果

例如：

给定字符串S ："abcdef" 作为主串，给定字符串T： "cd" 作为子串，此时，就需要在主串中查找是否出现子串，若出现，则返回主串中第一个匹配字符的下标；若未出现，则返回 -1

接下来，我们就来看 BF 算法是如何在主串中查找子串的，也就是 BF 算法的思路

算法思路

我们通过一个具体的例子来看：

定义 i 指向主串的 0 下标，j 指向子串的 0 下标

以主串的 0 下标位置作为起始位置开始匹配：

判断 i 位置的字符是否和 j 位置的字符相等， i 位置和 j 位置字符都为 a，相等，则这两个字符匹配成功，i 和 j 向后移动，继续匹配

继续判断 i 位置字符 是否与 j 位置字符相等， i 位置和 j 位置字符都为 b，相等，这两个字符也匹配成功，i 和 j 继续向后移动，进行匹配

继续判断 i 位置字符 是否与 j 位置字符相等，i 位置字符为 c，j 位置字符为 e，不相等，说明以 a（0 下标位置） 为起始位置匹配子串匹配失败

此时，需要将 i 进行回退，由于 a（0下标）作为起始位置匹配失败，因此，继续以 b （1下标）作为起始位置开始尝试匹配，也就是以 原起始位置 + 1 作为新的起始位置开始重新匹配

同样，j 也需要回退，需要将 j 回退到 0 下标位置，与下一个起始位置重新开始匹配

 由于 i 向前移动，当匹配失败时，我们该如何确定起始位置呢？

 由于当 i 和 j 匹配成功时，两者会同时向后移动，因此，通过 j 就可以知道 i 向前移动了多少步

 i - j 就是本次匹配的起始位置，而 i - j + 1 也就是新的起始位置

以 1 下标为起始位置继续匹配：

 i 位置字符为 b，j 位置字符为 a，不相等，说明以 b 为起始位置匹配子串匹配失败，再次回退，由于 i = 1，j = 0，因此，新的起始位置为 2，j 的位置为 0 

继续匹配，  i 位置字符为 c，j 位置字符为 a，不相等，说明以 c 为起始位置匹配子串匹配失败，再次回退，由于 i = 2，j = 0，因此，新的起始位置为 3，j 的位置为 0 

继续匹配， i 位置和 j 位置字符都为 a，相等，这两个字符匹配成功，i 和 j 向后移动

继续匹配， i 位置和 j 位置字符都为 b，相等，这两个字符也匹配成功，i 和 j 向后移动

 继续匹配， i 位置和 j 位置字符都为 e，相等，这两个字符也匹配成功，i 和 j 向后移动 

此时，子串已经遍历完了，也就说明 子串 中的所有字符都与 主串 中的字符相匹配，在主串中找到了子串，此时，就可以直接返回主串中本次匹配的起始位置，也就是 i - j

而若是主串先遍历完成，也就说明 主串 中没有与 子串 中字符完全匹配的字符串，找不到，此时，就需要返回 -1

总结一下上述过程：

1. 定义 i 指向主串的 0 下标，j 指向子串的 0 下标

2. 判断 i 位置字符与 j 位置字符是否相同，若相同，i 和 j 同时向后移动（i++ 且 j++）；若不同，则i 和 j 都需要进行回退（i = i - j + 1，j = 0）

3. 重复 2 过程，直到遍历完 主串 或 子串，若子串先遍历完，说明在主串中找到了子串，匹配成功，返回起始位置（i - j）；若主串先遍历完，说明主串中找不到子串，匹配失败，返回 -1

在分析了 BF 算法的思路之后，我们就来尝试编写代码

完整代码

    /*** 判断主串中是否含有子串* @param str 主串* @param target 子串* @return 主串中含有子串，返回主串中子串第一次出现的起始下标；若不含有，返回 -1*/public int BF(String str, String target) {// 处理特殊情况if (str == null || target == null) {return -1;}int strLen = str.length();int targetLen = target.length();if (strLen == 0 || strLen < targetLen) {return -1;}// 开始判断int i = 0, j = 0;while (i < strLen && j < targetLen) {// 判断 str 中 i 位置字符是否与 target 中j 位置字符相同if (str.charAt(i) == target.charAt(j)) {// 相同，i 和 j 都向后移动i++;j++;} else {// 不相同，i 和 j 都进行回退i = i - j + 1;j = 0;}}// 子串先遍历完if (j >= targetLen) {return i - j;} else {// 主串先遍历完return -1;}}

接下来，我们来分析 BF 算法的时间复杂度

时间复杂度

假设主串长度为 M，子串长度为 N

在最坏情况下，

在主串的前 M - N 个位置，每一次匹配时，都要比较到子串的最后一个字符（比较 N 次），才发现匹配不成功，然后再将 i 和 j 退回，继续比较，一共比较了 （M - N） * N

在 主串的最后 N 个位置，也分别匹配了 N、N - 1、N - 2...次，也就是 (N + 1)(N) / 2

因此，时间复杂度为 O（M*N）

上述我们查找的是主串中子串第一次出现时的起始位置，那么， 若我们想要查找主串中与子串相同的字符串的所有起始位置，该如何实现呢？

查找所有起始位置

与查找 主串中子串第一次出现的起始位置 思路相同

但是，当我们找到第一个起始位置（也就是 j 第一次遍历完子串时）时，不能直接返回，而是要继续在主串中查找

例如：

j 第一次遍历完子串：

以 0 下标为起始的字符串与子串匹配成功，将 0 下标存储起来，然后继续查找 

此时，以 i + 1 为起始位置的字符串可能与字符相同，因此需要将 i 进行回退，继续查找

同时，也需要将 j 回退到 0 下标位置，重新开始匹配

 

总结一下上述过程：

1. 定义 i 指向主串的 0 下标，j 指向子串的 0 下标

2. 判断 i 位置字符与 j 位置字符是否相同，若相同，i 和 j 同时向后移动（i++ 且 j++）；若不同，则i 和 j 都需要进行回退（i = i - j + 1，j = 0）

3. 判断 j 是否遍历完子串，若遍历完，则存储起始位置（i - j），再将 i 和 j 进行回退（i = i - j + 1，j = 0）

4. 重复 2、3 直到主串遍历完成

 代码实现：

    /*** 查找主串中与子串相同的字符串的所有起始位置* @param str 主串* @param target 子串* @return 查询结果集*/public List<Integer> BF(String str, String target) {List<Integer> ret = new ArrayList<>();// 处理特殊情况if (str == null || target == null) {return ret;}int strLen = str.length();int targetLen = target.length();if (strLen == 0 || strLen < targetLen) {return ret;}// 开始判断int i = 0, j = 0;while (i < strLen) {// 判断 str 中 i 位置字符是否与 target 中j 位置字符相同if (str.charAt(i) == target.charAt(j)) {// 相同，i 和 j 都向后移动i++;j++;} else {// 不相同，i 和 j 都进行回退i = i - j + 1;j = 0;}// 判断子串是否遍历完成if (j >= targetLen) {ret.add(i - j);i = i - j + 1;j = 0;}}return ret;}