【字符串匹配算法——BF算法】

🌈个人主页: Aileen_0v0
🔥热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法
​💫个人格言:“没有罗马,那就自己创造罗马~”

BF算法

介绍及过程演示

• 字符串的暴力法（Brute Force Method）是一种用于字符串匹配的简单算法，也称为“朴素匹配算法”。它的核心思想是从目标字符串中逐个字符进行比对，直到找到一个匹配或遍历完目标字符串为止。
• 查找过程如下所示：
  
• • 上面第一行的是主串，第二行的是子串，我们要从主串中找到子串，找到后返回对应主串开始与子串进行匹配的位置的下标。
• • ①当主串和子串匹配时他们对应的下标分别进行加加。
• • ②当主串和子串不匹配时，主串回到原来查找的位置下标+1处，子串回到起始位置0处。
• • ③当主串遍历完时，说明找不到子串的字符。
• • ④当子串遍历完时，说明在主串中找到了对应的子串。

代码实现过程

• 对应算法的代码实现:

public class BF {// 实现暴力法字符串匹配的函数public static int myBF(String str, String sub) {// 获取主字符串和子字符串的长度int strlen = str.length();int sublen = sub.length();// 边界条件：如果主字符串或子字符串为null，或者它们的长度为0，直接返回-1，表示无效输入if (str == null || sub == null || strlen == 0 || sublen == 0) {return -1;}// 遍历主字符串中的每个字符// i表示主字符串的位置，j表示子字符串的位置for (int i = 0, j = 0; i < strlen && j < sublen;) {// 如果当前主字符串和子字符串的字符相等if (str.charAt(i) == sub.charAt(j)) {i++;  // 主字符串位置前进j++;  // 子字符串位置前进// 如果子字符串的所有字符都匹配完毕，返回匹配的起始位置if (j == sublen) {return i - j;  // 计算起始位置，i - j 是主字符串匹配到的位置}} else {// 如果字符不匹配，重新从主字符串的下一个字符开始匹配i = i - j + 1;  // i回退到下一次匹配的起始位置j = 0;          // 子字符串重置为从头开始匹配}}// 如果遍历完主字符串后仍未找到匹配，返回-1return -1;}public static void main(String[] args) {// 调用myBF函数查找"abcd"在"ababcabcdabcde"中的起始位置int result = myBF("ababcabcdabcde", "abcd");// 输出结果：如果result不等于-1，表示找到匹配，否则表示未找到if (result != -1) {System.out.println("找到了，其匹配的起始位置是：" + result);} else {System.out.println("没找到");}}
}

因为char是一个基本数据类型，所以只能用==进行值相等的比较,这就是今天通过BF算法进行字符串比较的内容，让我们下期再见~

下节预告

KMP算法

利用next数组存储子串中j回退的位置（k），每一个回退位置（k）需要手动求得。

• k的求解：
  • 1.子串中j回退的位置K，是从0下标开始一直找到以j-1下标字符结尾的字符中两个相等的真子串（不包含本身），eg：下图中j=5时与主串i=5时对应下标的字符不一致，此时我们就可以通过找到从0开始到j-1范围里面子串中与主串比较匹配的两个子串来确定j=5时，应该回退到前面两个匹配的真子串对应长度的值即j应该回退到k=2的这个位置。next [5] = 2（k值）。若从0下标开始到j-1下标找不到两个匹配的字符串那么就说明k为0。