专业网站发展趋势,wordpress使用用户字体,html网站登陆注册怎么做,wordpress 文章型目录
BF算法的介绍
图解 JAVA语言实现
BF算法的时间复杂度 BF算法的介绍 BF算法#xff0c;即暴力(Brute Force)算法#xff0c;是普通的模式匹配算法#xff0c;BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配#xff0c;若相等#xff0c;则继…目录
BF算法的介绍
图解 JAVA语言实现
BF算法的时间复杂度 BF算法的介绍 BF算法即暴力(Brute Force)算法是普通的模式匹配算法BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配若相等则继续比较S的第二个字符和 T的第二个字符若不相等则比较S的第二个字符和T的第一个字符依次比较下去直到得出最后的匹配结果。BF算法是一种蛮力算法。 如果可以在S中寻找到T我们返回的是相匹配字符串中第一个字符在S串里的下标索引值如果找不到我们通常设置为返回-1。 图解 我们用i来遍历S j来遍历T 则实现过程如下
1i0,j0 aabcda da 匹配失败则 j 赋值 0 i 赋值 i - j 1 1 (2)i1j0aabcda da 匹配失败则 j 赋值 0 i 赋值 i - j 1 2 3i2,j0和i3,j0同理 匹配失败
4i4,j0 aabcda da 匹配成功则 i,j (5)i5,j1 aabcda da 匹配成功返回的是相匹配字符串中第一个字符在S串里的下标索引值,4 JAVA语言实现
public class BF {public static int bf(String str,String sub){if(strnull||subnull){return -1;}int strlenstr.length();int sublensub.length();if(strlen0||sublen0){return -1;}int i0,j0;while (istrlenjsublen){if(str.charAt(i)sub.charAt(j)){i;j;}else {ii-j1;j0;}}if(jsublen){return i-j;}return -1;}
}
测试
public static void main(String[] args) {System.out.println(bf(aabcda,da));}
结果4 BF算法的时间复杂度 1最理想的情况下 该算法的时间复杂度为O(n) 其中n为T串的长度即一次遍历就在S中找到了T 2最坏的情况下 该算法的时间复杂度为O(n*m) 其中 m 和 n 分别为 S 和 T 的长度即前面每次匹配都不成功直至到 S 的最后一个字符才与之匹配。 以上为我个人的小分享如有问题欢迎讨论
都看到这了不如关注一下给个免费的赞
