🌈个人主页: 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;          // 子字符串重置为从头开始匹配
            }
        }
        // 如果遍历完主字符串后仍未找到匹配，返回-1
        return -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。