☀️ 什么是BF算法
BF算法,即暴力算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个与模式串T的第一个字符串进行匹配,若相等,则继续比较S的第二个字符和T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果,BF算法是一种蛮力算法。
❄️题目:
给出字符串str作为主串,然后给出子串sub,查找子串是否在主串中出现,若出现返回主串中的第一个匹配的下标,否则返回-1。
⛄️图解演示:
假设:
主串:a b a b c a b c d a b c d e
子串:a b c d
给定i,j 记录字符串下标
🌏算法思想:
主串的第一个字符和子串的第一个字符进行匹配,若相等,继续匹配主串的第二个字符和子串的第二个字符,即i++,j++;若不想等,主串回溯到第一个字符的下一个字符,子串回溯到0,即i = i - j + 1,j = 0;依次进行,直到匹配成功,返回i - j ;若失败,返回==-1==;
文章来源:https://www.toymoban.com/news/detail-673981.html
🌼算法代码:
public class BF {
public static int bF(String str,String sub) {
if(str==null || sub == null) {
return -1;
}
int lenStr = str.length();
int lenSub = sub.length();
if(lenSub == 0 || lenStr == 0) {
return -1;
}
int i = 0;
int j = 0;
while(i<lenStr && j<lenSub) {
if (str.charAt(i) == sub.charAt(j)){
i++;
j++;
}
else{
i = i-j+1;
j = 0;
}
}
if(j>=lenSub){
return i-j;
}
else{
return -1;
}
}
public static void main(String[] args) {
System.out.println(bF("ababcabcdabcde","abcd"));
System.out.println(bF("ababcabcdabcde","abcdf"));
System.out.println(bF("ababcabcdabcde","abcde"));
}
}
运行结果
5
-1
9文章来源地址https://www.toymoban.com/news/detail-673981.html
到了这里,关于【Java】BF算法(串模式匹配算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!