【java数据结构与算法学习】BF算法

朱雀 2022-05-30 08:24 263阅读 0赞

BF算法(Brute-Force)，是一种最基本的模式匹配算法。

BF算法的实现思想很简单：

从目标串s 的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s的第二个字符起再重新和串t进行比较。

依此类推，直至串t 中的每个字符依次和串s的一个连续的字符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功。

该算法最坏情况下要进行M\*(N-M+1)次比较，时间复杂度为O(M\*N)。

//BF算法
    public class BF {
        public static void main(String[] args) {
            String target = "Iloveyou";
            String reg = "ve";
    
            if(target.length() < reg.length()){
                System.out.println("没有改子串！");
                return;
            }
            int i = 0; //主串索引
            int j = 0; //模式串索引
            while (i < target.length() && j < reg.length()){
                //比较字符，如果不相等，模式串索引回溯到0的位置，主串的索引变成i - j + 1
                if (target.charAt(i) != reg.charAt(j)){
                    i = i - j + 1; //回溯到主串将要比较的下一个位置 //主串比较成功的初始位置减去成功的次数加上1
                    j = 0;
                //如果相等，索引都加1，往下比较
                }else{
                    i++;
                    j++;
                }
            }
            //模式串到头，返回成功，否则失败
            if (j == reg.length()){
                System.out.println("字符串的位置："  + (i - j));
                System.out.println("success");
                return;
            }else {
                System.out.println("fail");
                return;
            }
        }
    }