Go 数据结构和算法篇（十一）：字符串匹配之 BF 算法

Go语言中文网 前天以下文章来源于xueyuanjun ，作者xueyuanjun

xueyuanjun学院君的订阅号，我会在这里持续更新优质全栈编程技术教程，包括但不限于 Golang、PHP、JavaScript 以及计算机底层技术。关注我，学习更多编程知识！

接下来的三篇教程，将由浅及深地给大家介绍三个常见的字符串匹配算法。首先从最简单的字符串匹配算法 —— BF 算法说起，BF 是 Brute Force 的缩写，中文译作暴力匹配算法，也叫朴素匹配算法。实现原理BF 算法的原理很简单，在继续介绍之前，我们先引入两个术语：主串和模式串。简单来说，我们要在字符串 A 中查找子串 B，那么 A 就是主串，B 就是模式串。作为最简单、最暴力的字符串匹配算法，BF 算法的思想可以用一句话来概括，那就是，如果主串长度为 n，模式串长度为 m，我们在主串中检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。图示如下：

BF算法图示结合上图，具体来说，就是每次拿模式串和主串对齐，然后从左到右依次比较每个字符，如果出现不相等，则把模式串往后移一个位置，再次重复上述步骤，直到模式串每个字符与对应主串位置字符都相等，则返回主串对应下标，表示找到，否则返回 -1，表示没找到。示例代码下面我们基于 BF 算法来实现一个 Go 语言版的字符串查找函数：package mainimport "fmt"// BF 算法实现函数func bfSearch(s, p string) int {begin := 0i, j := 0, 0n, m := len(s), len(p)  // 主串、子串长度for i = 0; i < n; begin++ {// 通过 BF 算法暴力匹配子串和主串for j = 0; j < m; j++ {if i < n && s[i] == p[j] {// 如果子串和主串对应字符相等，逐一往后匹配i++} else {// 否则退出当前循环，从主串下一个字符继续开始匹配break}}if j == m {// 子串遍历完，表面已经找到，返回对应下标return i - j}// 从下一个位置继续开始匹配i = begini++}return -1}// 基于 BF 算法实现字符串查找函数func strStrV1(haystack, needle string) int {// 子串长度=0if len(needle) == 0 {return 0}//主串长度=0，或者主串长度小于子串长度if len(haystack) == 0 || len(haystack) < len(needle) {return -1}// 调用 BF 算法查找子串return bfSearch(haystack, needle)}func main() {s := "Hello, 学院君!"p := "学院君"pos := strStrV1(s, p)fmt.Printf("Find \"%s\" at %d in \"%s\"\n", p, pos, s)}执行上述代码，打印结果如下：

性能分析这个算法很好理解，因为这就是我们正常都能想到的暴力匹配，BF 算法的时间复杂度最差是 O(n*m)，意味着要模式串要移到主串 n-m 的位置上，并且模式串每个字符都要与子串比较。尽管 BF 算法复杂度看起来很高，但是在日常开发中，如果主串和模式串规模不大的话，该算法依然比较常用，因为足够简单，实现起来容易，不容易出错。另外，在规模不大的情况下，开销也可以接受，毕竟 O(n*m) 是最差的表现，大部分时候，执行效率比这个都要高。但是对于对时间要求比较敏感，或者需要高频匹配，数据规模较大的情况下，比如编辑器中的匹配功能、敏感词匹配系统等，BF 算法就不适用了，后面我们将介绍更高级的字符串匹配算法来处理这些场景需求。（本文完）推荐阅读Go 数据结构和算法篇（十）：二分查找的变形版本福利我为大家整理了一份从入门到进阶的Go学习资料礼包，包含学习建议：入门看什么，进阶看什么。关注公众号 「polarisxu」，回复 ebook 获取；还可以回复「进群」，和数万 Gopher 交流学习。阅读原文阅读 596赞4在看3收藏此内容的人还喜欢写 Node.js 代码，从学会调试开始写 Node.js 代码，从学会调试开始...赞 13前端试炼不喜欢不看的原因确定内容质量低不看此公众号写下你的留言精选留言

打家劫舍2等一波KMP算法和RK算法

火山灰编辑器中的匹配功能通常用什么匹配算法？

赤蛇还有Sunday算法