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;
}原文地址：https://blog.csdn.net/2301_76161469/article/details/142879154
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！