接下来的三篇(本篇、次篇、再篇)教程中,将由浅及深地给大家介绍三个常见的字符串匹配算法。
首先从最简单的字符串匹配算法 —— BF 算法说起,BF 是 Brute Force 的缩写,中文译作暴力匹配算法,也叫朴素匹配算法。
BF 算法的原理很简单,在继续介绍之前,我们先引入两个术语:主串和模式串。简单来说,我们要在字符串 A 中查找子串 B,那么 A 就是主串,B 就是模式串。
作为最简单、最暴力的字符串匹配算法,BF 算法的思想可以用一句话来概括,那就是,如果主串长度为 n,模式串长度为 m,我们在主串中检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串,看有没有跟模式串匹配的。图示如下:
结合上图,具体来说,就是每次拿模式串和主串对齐,然后从左到右依次比较每个字符,如果出现不相等,则把模式串往后移一个位置,再次重复上述步骤,直到模式串每个字符与对应主串位置字符都相等,则返回主串对应下标,表示找到,否则返回 -1,表示没找到。
下面我们基于 BF 算法来实现一个 Go 语言版的字符串查找函数:
package main
import "fmt"
// BF 算法实现函数
func bfSearch(s, p string) int {
begin := 0
i, j := 0, 0
n, 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 = begin
i++
}
return -1
}
// 基于 BF 算法实现字符串查找函数
func strStrV1(haystack, needle string) int {
// 子串长度=0
if 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 算法就不适用了,后面我们将介绍更高级的字符串匹配算法来处理这些场景需求。