BF算法（暴⼒算法）-- 模式匹配算法

太过爱你忘了你带给我的痛 2023-09-28 16:05 31阅读 0赞

## 引言 ##

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

## 暴⼒算法(BF算法) ##

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

![在这里插入图片描述][b1bd0cc0d65342079cb1cecd225b18df.png]

## 暴力求解法 ##

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

![在这里插入图片描述][e7160bde6cd3427e96009f42a607dc72.png]

## 模式匹配算法 ##

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

## 算法思想 ##

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

## 代码复杂度 ##

> 该算法最理想的`时间复杂度`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 所示：

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

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

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

![在这里插入图片描述][fcfa849570384553aefae09724b2a221.png_pic_center]  
由此，串 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);
        }
    }

![在这里插入图片描述][81e089d04afe42b9bb9c3b4103b21077.png]

## 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;
            }
        }

## 附属文章（String源码解析） ##

[\[ 点击查看String源码解析 \]][_String_]

## 关联算法文章： ##

> 这里有一些相关的文章，可以参考一下

1、[斐波那契数列的迭代算法和递归算法][Link 1]  
2、[埃氏筛法(埃氏算法)][Link 2]  
3、[BF算法（暴⼒算法）-- 模式匹配算法][BF_--]  
4、[数据结构：八大数据结构分类][Link 3]  
5、[JAVA中 常用七大排序算法][JAVA_]  
6、[Linked 链表反转 - 迭代 与 递归][Linked _ - _ _]

[b1bd0cc0d65342079cb1cecd225b18df.png]: https://img-blog.csdnimg.cn/b1bd0cc0d65342079cb1cecd225b18df.png
[e7160bde6cd3427e96009f42a607dc72.png]: https://img-blog.csdnimg.cn/e7160bde6cd3427e96009f42a607dc72.png
[134766336a6245a98550d6b6c72fcacb.png_pic_center]: https://img-blog.csdnimg.cn/134766336a6245a98550d6b6c72fcacb.png#pic_center
[9facd7cc9371464684d1974e374501a1.png_pic_center]: https://img-blog.csdnimg.cn/9facd7cc9371464684d1974e374501a1.png#pic_center
[694845d9e97f4737b7693ae01f1d9809.png_pic_center]: https://img-blog.csdnimg.cn/694845d9e97f4737b7693ae01f1d9809.png#pic_center
[fcfa849570384553aefae09724b2a221.png_pic_center]: https://img-blog.csdnimg.cn/fcfa849570384553aefae09724b2a221.png#pic_center
[81e089d04afe42b9bb9c3b4103b21077.png]: https://img-blog.csdnimg.cn/81e089d04afe42b9bb9c3b4103b21077.png
[_String_]: https://blog.csdn.net/GoodburghCottage/article/details/126639829
[Link 1]: https://blog.csdn.net/GoodburghCottage/article/details/125929088
[Link 2]: https://blog.csdn.net/GoodburghCottage/article/details/125912135
[BF_--]: https://blog.csdn.net/GoodburghCottage/article/details/125907253
[Link 3]: https://blog.csdn.net/GoodburghCottage/article/details/125681654
[JAVA_]: https://blog.csdn.net/GoodburghCottage/article/details/125594490
[Linked _ - _ _]: https://blog.csdn.net/GoodburghCottage/article/details/125597183