【Java】BF算法（串模式匹配算法）

☀️ 什么是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==；

🌼算法代码：

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