没有网站做淘宝客,吉林市市政建设集团网站,网页设计素材文字,南昌建设工程质量监督网站目录
BF算法
算法思路
完整代码
时间复杂度
查找所有起始位置 BF算法
BF算法#xff1a;即暴力(Brute Force)算法#xff0c;是一种模式匹配算法#xff0c;将目标串 S 的第一个字符与模式串 T 的第一个字符进行匹配#xff0c;若相等#xff0c;则继续比较 S 的第二…目录
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 位置字符为 cj 位置字符为 e不相等说明以 a0 下标位置 为起始位置匹配子串匹配失败
此时需要将 i 进行回退由于 a0下标作为起始位置匹配失败因此继续以 b 1下标作为起始位置开始尝试匹配也就是以 原起始位置 1 作为新的起始位置开始重新匹配
同样j 也需要回退需要将 j 回退到 0 下标位置与下一个起始位置重新开始匹配 由于 i 向前移动当匹配失败时我们该如何确定起始位置呢 由于当 i 和 j 匹配成功时两者会同时向后移动因此通过 j 就可以知道 i 向前移动了多少步 i - j 就是本次匹配的起始位置而 i - j 1 也就是新的起始位置 以 1 下标为起始位置继续匹配 i 位置字符为 bj 位置字符为 a不相等说明以 b 为起始位置匹配子串匹配失败再次回退由于 i 1j 0因此新的起始位置为 2j 的位置为 0 继续匹配 i 位置字符为 cj 位置字符为 a不相等说明以 c 为起始位置匹配子串匹配失败再次回退由于 i 2j 0因此新的起始位置为 3j 的位置为 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 1j 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
因此时间复杂度为 OM*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 1j 0 3. 判断 j 是否遍历完子串若遍历完则存储起始位置i - j再将 i 和 j 进行回退i i - j 1j 0 4. 重复 2、3 直到主串遍历完成 代码实现 /*** 查找主串中与子串相同的字符串的所有起始位置* param str 主串* param target 子串* return 查询结果集*/public ListInteger BF(String str, String target) {ListInteger 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;}
