Go 數據結構和算法篇：字符串匹配之 BF 算法

首先從最簡單的字符串匹配算法 —— 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 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 算法就不適用了，後面我們將介紹更高級的字符串匹配算法來處理這些場景需求。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/C3mfdaGwTDPREw9cn9eF0A