Java 算法篇-深入了解 BF 与 KMP 算法

🔥博客主页： 【小扳_-CSDN博客】

❤感谢大家点赞👍收藏⭐评论✍

文章目录

        1.0 BF 算法概述

        1.1 BF 算法实际使用

        2.0 KMP 算法概述

        2.1 KMP 算法实际使用

        2.2 相比于 BF 算法实现，KMP 算法的重要思想

        2.3 为什么要这样设计？

        2.4 next 数组

        2.4.1 创建 next 数组原理

        2.4.2 创建 next 数组过程

        2.5 KMP 算法的实现

        1.0 BF 算法概述

        是一种基本的暴力搜索算法，也称为穷举算法或暴力匹配算法。BF 算法通过遍历所有可能的解空间来寻找问题的解，虽然效率较低，但在一些简单的问题上仍然具有一定的实用性。

        尽管 BF 算法效率较低，但在一些简单的问题上，它仍然可以提供可行的解决方案。在一些小规模的问题、教学示例或者需要快速验证解的情况下，BF 算法可以作为一种简单且直观的解决方法。

        1.1 BF 算法实际使用

        举个例子：用 BF 算法来找到主串 str 中是否存在子串 sub，如果存在，那么子串在主串的具体那个位置。

        实现思路：为了实现一个比较严谨的程序，首先对 str 与 sub 进行判断是否为 null 或者长度为 0 。

        接着，用变量 i 来记录主串 str 索引下标，用变量 j 来记录子串 sub 索引下标，且用 strLen 来记录主串的长度，用 sunLen 来记录子串的长度。

        再接着，用 while 循环，循环比较 str 与 sub 中字符是否相同，如 str.charAt(i) 与 sub.charAt(j) 进行比较，如果两者相同，那么继续往后走 i++ ，j++  ；如果两者不相同，那么对于主串来说，i 需要回到 i = i - j + 1 位置，对于 j 来说， 就要回到原点 j = 0 。

如图：

        最后，判断是什么原因导致跳出了循环：

        有两个原因：（1）j >= subLen ，则说明了 j 已经比较完毕了，所以主串中存在子串，位置位于：（i - j）。（2）i > strLen ，则说明，即使 i 都走完了， j 还没走完，那么主串中不存在该子串。

代码如下：

public class demo1 {
    //暴力解法
    public static void main(String[] args) {
        String str = "abbccccfffrreytur";
        String sub = "tu";
        bf(str,sub);
    }
    public static void bf(String str, String sub){
        if (str == null || sub == null){
            System.out.println("对象为 null");
            return;
        }
        if (str.length() == 0 || sub.length() == 0){
            System.out.println("长度不合法！！！！");
            return;
        }
        //记录主串下标
        int i = 0;
        //主串长度
        int strLen = str.length();
        //记录子串下标
        int j = 0;
        //子串长度
        int subLen = sub.length();
        while (i