Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（十一）：字符串匹配之 BF 算法

接下來的三篇教程，將由淺及深地給大家介紹三個(gè)常見的字符串匹配算法。

首先從最簡(jiǎn)單的字符串匹配算法 —— BF 算法說起，BF 是 Brute Force 的縮寫，中文譯作暴力匹配算法，也叫樸素匹配算法。

實(shí)現(xiàn)原理

BF 算法的原理很簡(jiǎn)單，在繼續(xù)介紹之前，我們先引入兩個(gè)術(shù)語(yǔ)：主串和模式串。簡(jiǎn)單來說，我們要在字符串 A 中查找子串 B，那么 A 就是主串，B 就是模式串。

作為最簡(jiǎn)單、最暴力的字符串匹配算法，BF 算法的思想可以用一句話來概括，那就是，如果主串長(zhǎng)度為 n，模式串長(zhǎng)度為 m，我們?cè)谥鞔袡z查起始位置分別是 0、1、2…n-m 且長(zhǎng)度為 m 的 n-m+1 個(gè)子串，看有沒有跟模式串匹配的。圖示如下：

結(jié)合上圖，具體來說，就是每次拿模式串和主串對(duì)齊，然后從左到右依次比較每個(gè)字符，如果出現(xiàn)不相等，則把模式串往后移一個(gè)位置，再次重復(fù)上述步驟，直到模式串每個(gè)字符與對(duì)應(yīng)主串位置字符都相等，則返回主串對(duì)應(yīng)下標(biāo)，表示找到，否則返回 -1，表示沒找到。

示例代碼

下面我們基于 BF 算法來實(shí)現(xiàn)一個(gè) Go 語(yǔ)言版的字符串查找函數(shù)：

package main

import "fmt"

// BF 算法實(shí)現(xiàn)函數(shù)
func bfSearch(s, p string) int {
    begin := 0
    i, j := 0, 0
    n, m := len(s), len(p)  // 主串、子串長(zhǎng)度
    for i = 0; i < n; begin++ {
        // 通過 BF 算法暴力匹配子串和主串
        for j = 0; j < m; j++ {
            if i < n && s[i] == p[j] {
                // 如果子串和主串對(duì)應(yīng)字符相等，逐一往后匹配
                i++
            } else {
                // 否則退出當(dāng)前循環(huán)，從主串下一個(gè)字符繼續(xù)開始匹配
                break
            }
        }
        if j == m {
            // 子串遍歷完，表面已經(jīng)找到，返回對(duì)應(yīng)下標(biāo)
            return i - j
        }
        // 從下一個(gè)位置繼續(xù)開始匹配
        i = begin
        i++
    }
    return -1
}

// 基于 BF 算法實(shí)現(xiàn)字符串查找函數(shù)
func strStrV1(haystack, needle string) int {
    // 子串長(zhǎng)度=0
    if len(needle) == 0 {
        return 0
    }
    //主串長(zhǎng)度=0，或者主串長(zhǎng)度小于子串長(zhǎng)度
    if len(haystack) == 0 || len(haystack) < len(needle) {
        return -1
    }
    // 調(diào)用 BF 算法查找子串
    return bfSearch(haystack, needle)
}

func main() {
    s := "Hello, 學(xué)院君!"
    p := "學(xué)院君"
    pos := strStrV1(s, p)
    fmt.Printf("Find \"%s\" at %d in \"%s\"\n", p, pos, s)
}

執(zhí)行上述代碼，打印結(jié)果如下：

性能分析

這個(gè)算法很好理解，因?yàn)檫@就是我們正常都能想到的暴力匹配，BF 算法的時(shí)間復(fù)雜度最差是 O(n*m)，意味著要模式串要移到主串 n-m 的位置上，并且模式串每個(gè)字符都要與子串比較。

盡管 BF 算法復(fù)雜度看起來很高，但是在日常開發(fā)中，如果主串和模式串規(guī)模不大的話，該算法依然比較常用，因?yàn)樽銐蚝?jiǎn)單，實(shí)現(xiàn)起來容易，不容易出錯(cuò)。另外，在規(guī)模不大的情況下，開銷也可以接受，畢竟 O(n*m) 是最差的表現(xiàn)，大部分時(shí)候，執(zhí)行效率比這個(gè)都要高。

但是對(duì)于對(duì)時(shí)間要求比較敏感，或者需要高頻匹配，數(shù)據(jù)規(guī)模較大的情況下，比如編輯器中的匹配功能、敏感詞匹配系統(tǒng)等，BF 算法就不適用了，后面我們將介紹更高級(jí)的字符串匹配算法來處理這些場(chǎng)景需求。