BF算法（暴⼒算法）-- 模式匹配算法-蒲公英云

引言

BF算法 的实现过程很 “无脑”，不包含任何技巧，在对数据量大的串进行模式匹配时，算法的效率很低。

暴⼒算法(BF算法)

暴力(BruteForce)算法：是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。

在这里插入图片描述

暴力求解法

暴力求解法 ：又名直接带入法（Directly Calculating）它是已知最古老的算法之一，与”直观目测法”，”心灵感应法”并称世界三大不可思议数学计算法则，其可追溯至3200年前，古老的埃及人便开始使用象形文字进行复杂的数学演算。

在这里插入图片描述

模式匹配算法

模式匹配算法：是数据结构中字符串的⼀种基本运算，给定⼀个⼦串，要求在某个字符串中找出与该⼦串相同的所有⼦串，这就是模式匹配。
⽤途：搜索引擎、拼写检查、语⾔翻译、数据压缩等。

算法思想

普通模式匹配算法，其实现过程没有任何技巧，就是简单粗暴地拿一个串同另一个串中的字符一一比对，得到最终结果。

代码复杂度

该算法最理想的时间复杂度O(n)，n 表示串 A 的长度，即第一次匹配就成功。 BF 算法最坏情况的时间复杂度为 O(n *m)，n 为串 A 的长度，m 为串 B 的长度。例如，串 B 为 “0000000001”，而串 A 为 “01”，这种情况下，两个串每次匹配，都必须匹配至串 A 的最末尾才能判断匹配失败，因此运行了 n *m 次。
时间复杂度太高，往往不推荐。

例如，使用普通模式匹配算法判断串 A（“abcac”）是否为串 B（“ababcabacabab”）子串的判断过程如下：
首先，将串 A 与串 B 的首字符对齐，然后逐个判断相对的字符是否相等，如图 1 所示：

在这里插入图片描述
图 1 中，由于串 A 与串 B 的第 3 个字符匹配失败，因此需要将串 A 后移一个字符的位置，继续同串 B
匹配，如图 2 所示：

在这里插入图片描述
图 1 中，由于串 A 与串 B 的第 3 个字符匹配失败，因此需要将串 A 后移一个字符的位置，继续同串 B 匹配，如图 2 所示：

在这里插入图片描述
图 3 中，两串的模式匹配失败，串 A 继续移动，一直移动至图 4 的位置才匹配成功：

在这里插入图片描述
由此，串 A 与串 B 以供经历了 6 次匹配的过程才成功，通过整个模式匹配的过程，证明了串 A 是串 B 的子串（串 B 是串 A 的主串）。

BF算法实现（JAVA 语言版）

public static void main(String[] args) {
    String strA ="ababcabcacabacabab";
    String strB ="abcac";
    int lastInde1=strA.lastIndexOf("abcac");//字符串第一个字符最后出现的下标
    if(lastInde1==-1) {
        System.out.println("不存在字符串 "+strB);
    }else {
        System.out.println("字符串"+strB+"最后一次出现的位置："+lastInde1);
    }
}

在这里插入图片描述

String 中 lastIndexOf 源码分析

/**
     * @param   ch   ⼀个字符
     * @return   返回指定字符的最后⼀次出现的字符串中的索引
     */
    public int lastIndexOf(int ch) {
        return lastIndexOf(ch, value.length - 1);
    }
    /**
     * 
     * @param   ch   ⼀个字符
     * @param   fromIndex 开始搜索的索引
     * @return   从fromIndex索引开始最后⼀次出现ch字符的索引
     */
    public int lastIndexOf(int ch, int fromIndex) {
        //⼀般ch都是从0到0xFFFF
        if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
            final char[] value = this.value;
            //⽐较fromIndex和字符串最后⼀个字符的索引
            //取较⼩值
            //防⽌fromIndex越界
            int i = Math.min(fromIndex, value.length - 1);
            //从最后⼀个索引位置开始向前查找
            for (; i >= 0; i--) {
                //逐⼀判断相等即返回当前索引
                if (value[i] == ch) {
                    return i;
                }
            }
            //找不到即返回-1
            return -1;
        } else {
            //⽬前不做深究
            return lastIndexOfSupplementary(ch, fromIndex);
        }
    }
    / * @param   source       源字符串的数组.
     * @param   sourceOffset  源字符串的偏移量.
     * @param   sourceCount   源字符串的长度.
     * @param   target       ⼦串的数组.
     * @param   targetOffset ⼦串偏移量.
     * @param   targetCount  ⼦串的长度
     * @param   fromIndex    开始索引的位置
     * @return 返回指定⼦字符串最后⼀次出现的字符串中的索引。
     */
     static int lastIndexOf(char[] source, int sourceOffset, int sourceCount,
           char[] target, int targetOffset, int targetCount,int fromIndex) {
        //因为sourceOffset和targetOffset 都为0 
        //查看源码调⽤此⽅法时的参数都为0
        //所以最右侧索引位为元字符长度-字串长度
        int rightIndex = sourceCount - targetCount;
        int rightIndex = sourceCount - targetCount;
        //开始索引位置⼩于0则说明找不到
        //因为这是从后⾯往前找的
        if (fromIndex < 0) {
            return -1;
        }
        //因为索引位置⼤于rightIndex肯定找不到
        //所以开始索引位置⼤于rightIndex就从rightIndex查找
        if (fromIndex > rightIndex) {
            fromIndex = rightIndex;
        }
        //⼦串长度为0，则返回源字符串最后⼀个字符位置的索引
        if (targetCount == 0) {
            return fromIndex;
        }
        //⼦串最后⼀个字符索引位
        int strLastIndex = targetOffset + targetCount - 1;
        //获取⼦串最后⼀个字符
        char strLastChar = target[strLastIndex];
        //因为⼦串和源字符串⽐较是从⼦串的最后⼀个位置向前⽐较
        //min为源字符串source最后⼀个字符的最⼩索引位置
        int min = sourceOffset + targetCount - 1;
        //因为有fromIndex ,所以源字符串source的最⼩索引为min+fromIndex
        int i = min + fromIndex;
        //此时i为源字符串source的最后⼀个位置最⼤索引位置
        startSearchForLastChar:
        while (true) {
            //循环找到最后⼀个字符相等的位置
            while (i >= min && source[i] != strLastChar) {
                i--;
            }
            //如果i<min说明找不到返回-1
            if (i < min) {
                return -1;
            }
            //最后⼀个字符相等的索引找到后
            //获取源字符串source倒第⼆个字符索引位置
            int j = i - 1;
            //⾸先明⽩是倒着⽐较的
            //start为计算源字符串source个字符索引位置的最后⼀个位置的前⼀个索引位置
            int start = j - (targetCount - 1);
            //k为字串倒第⼆个字符索引位置
            int k = strLastIndex - 1;
            while (j > start) {
            //依次向前⽐较所有字符
                if (source[j--] != target[k--]) {
                //如果不想等则向前继续查找倒数第⼀个字符相等的索引
                    i--;
                    continue startSearchForLastChar;
                }
            }
            //找到了返回
            //为什么+1
            //引⽂start为计算源字符串source个字符索引位置的最后⼀个位置的前⼀个索引位置
            return start - sourceOffset + 1;
        }
    }