动画：什么是 BF 算法？

悠悠 2021-12-03 07:01 417阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640][]

本文是图解 **什么是** **BF算法**、**KMP算法**、**BM算法** 三部曲之一。

### 定义 ###

**B**rute-**F**orce算法，简称为 **BF算法**，是一种简单朴素的模式匹配算法，常用于在一个主串 S 内查找一个子串 T 的出现位置。

它的核心思想与操作是：

### 动画演示 ###

### 图片演示 ###

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 4]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 5]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 6]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 7]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 8]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 9]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 10]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 11]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 12]

### 代码描述 ###

int index( String S, String T, int pos ){    int i = pos;                        // i 表示主串 S 中当前位置下标    int j = 1;                            // j 表示子串 T 中当前位置下标    while( i <= S[0] && j <= T[0] ){    // i 或 j 其中一个到达尾部则终止搜索        if( S[i] == T[i] ){             // 若相等则继续进行下一个元素匹配            i++;            j++;        }else {                         // 若匹配失败则 j 回溯到第一个元素重新匹配            i = i - j + 2;              // 将 i 重新回溯到上次匹配首位的下一个元素            j = 1;        }    }    if( j > T[0] ){        return i - T[0];    }else {        return 0;    }}
        int i = pos;                        // i 表示主串 S 中当前位置下标
        int j = 1;                            // j 表示子串 T 中当前位置下标
    
        while( i <= S[0] && j <= T[0] ){    // i 或 j 其中一个到达尾部则终止搜索
            if( S[i] == T[i] ){             // 若相等则继续进行下一个元素匹配
                i++;
                j++;
            }else {                         // 若匹配失败则 j 回溯到第一个元素重新匹配
                i = i - j + 2;              // 将 i 重新回溯到上次匹配首位的下一个元素
                j = 1;
            }
        }
    
        if( j > T[0] ){
        
            return i - T[0];
        }else {
        
            return 0;
        }
    }

### 总结 ###

**BF算法** 在主串和字串匹配失败时，主串进行的回溯操作会影响效率，回溯之后，主串与字串有些部分比较是没有必要的。这种简单的丢弃前面的匹配信息是 **BF算法** 之所以效率低效的一个重要因素。

**KMP算法**、**BM算法** 将在后续分别进行详细介绍，敬请关注。

--------------------

**本文相关阅读推荐：**

[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[一道腾讯面试题：厉害了我的杯][Link 2]

[十大经典排序算法动画与解析，看我就够了][Link 3]

[这或许是东半球分析十大排序算法最好的一篇文章][Link 4]

[面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

--------------------

![640?wx\_fmt=png][640_wx_fmt_png]

##  ##

[640]: /images/20211203/a1e47ac80d3547198b321ce321dc5fb4.png
[640_wx_fmt_jpeg]: /images/20211203/e75ed156c0f94f82ab4e3b3bed13fa73.png
[640_wx_fmt_jpeg 1]: /images/20211203/e032b26900d5425abab73b828d3893e3.png
[640_wx_fmt_jpeg 2]: /images/20211203/66d84db1baf645d19bf5efd03ce8f168.png
[640_wx_fmt_jpeg 3]: /images/20211203/f11f5f225a074df6aedaeea3c1a91133.png
[640_wx_fmt_jpeg 4]: /images/20211203/b762607aa73e4ca19feed27a5ea51a51.png
[640_wx_fmt_jpeg 5]: /images/20211203/58ffacff8a84466c8e4dcedb78a030fe.png
[640_wx_fmt_jpeg 6]: /images/20211203/c890880f504741dab626865b73e0ce12.png
[640_wx_fmt_jpeg 7]: /images/20211203/960f93564bab47dc8939fe99ef7e2489.png
[640_wx_fmt_jpeg 8]: /images/20211203/e01963e533aa4ab188e4e40ceb0b4ddb.png
[640_wx_fmt_jpeg 9]: /images/20211203/3ef798952a2e43c19efaa07632800483.png
[640_wx_fmt_jpeg 10]: /images/20211203/53624f96a4e048b4bb671c1cd68c48de.png
[640_wx_fmt_jpeg 11]: /images/20211203/2b3f9eaa92b9421ba4b16abd1992e2c0.png
[640_wx_fmt_jpeg 12]: /images/20211203/e7a6b53fda1048f497f7d975d25bd3c0.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 3]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 4]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[640_wx_fmt_png]: /images/20211203/01ebbdf830974e9fb3b56318b550778e.png