今天介紹兩種基礎的字符串匹配算法，當然核心還是熟悉一下Go的語法，鞏固一下基礎知識

• BF(Brute Force)
• RK(Rabin Karp)

源字符串：src, 目標字符串:dest； 確認dest是否是src 的一部分。

BF算法很簡單暴力，維護兩個下標i,j，i控制src的遍歷順序, j控制dest遍歷順序。
記錄一下i的起始位置，當j和i所在的字符匹配的時候，j和i都移動，知道j達到末尾則直接返回匹配。
否則i 回到起始位置的下一個位置，j 回到起始位置，兩者重新進行匹配搜索。

由于比較簡單，直接看一下Go實現的代碼即可：

func Brute_force(str1 string, str2 string) bool{if len(str1) < len(str2){return  false}var (begin int = 0 // 維護src的起始位置i intj int)for i = 0; i < len(str1); begin++ {for j = 0;j < len(str2); j++ {if i < len(str1) && str1[i] == str2[j] {i++continue} else {break}}if j == len(str2) {return  true}i = begini++}return false
}

以上最壞的情況下是 主串是“aaaaa…aaaaaa”(省略號表示有很多重復的字符a)，模式串是“aaaaab”。我們每次都比 對m個字符，要比對n-m+1次，所以，這種算法的最壞情況時間復雜度是O(n*m)。
當然這種模式匹配在實際的軟件開發中還是比較常用的，主要有如下兩種原因：

• 實際的軟件開發中，大部分情況下，模式串和主串的長度都不會太長。而且每次模式串與主串中的子串匹配的時候，當中途遇到不能匹配的字符的時候， 就可以就停止了，不需要把m個字符都比對一下。所以，盡管理論上的最壞情況時間復雜度是O(n*m)，但是，統計意義上，大部分情況下，算法執行效率要比這 個高很多。
• 樸素字符串匹配算法思想簡單，代碼實現也非常簡單。簡單意味著不容易出錯，如果有bug也容易暴露和修復。

接下來看一下第二種算法，Rabin Karp。
這個算法的大體思路是：
過哈希算法對主串中的n-m+1個子串分別求哈希值，然后逐個與模式串的哈希值比較大小。如果某個子串的哈希值與模式串相 等，那就說明對應的子串和模式串匹配了。因為哈希值是一個數字，數字之間比較是否相等是非常快速的， 所以模式串和子串比較的效率就提高了。

為了提升效率，我們需要盡可能避免遍歷字符串中的每一個字符，否則就是僅僅提高了比較效率而已（數值的比較效率）。
hash函數的設計需要精巧一些，假設我們設置的字符集只包含k個字符，我們可以使用一個K進制的數來表示一個字符串，將這個 K進制轉化為10進制的值即可作為hash 值。

比如要處理的字符串包括a-z 26個字母，我們可以使用26進制表示一個字符串，同時將26進制轉化為一個10進制的值作為這個字符串的hash值。

對于字符串：“hjk”
h: (‘h’- ‘a’) *26^0
j: (‘j’ - ‘a’) * 26^1
j: (‘k’ - ‘a’) * 26^2

hash(“hjk”) = (‘h’- ‘a’) *26^0 + (‘j’ - ‘a’) * 26^1 + (‘k’ - ‘a’) * 26^2

為了減少遍歷源字符串中的字符 次數，我們可以看看如下規律:
源字符串“hjkl”,我們先取 “hjk”， 后取"jkl"

hash(“hjk”) = (‘h’- ‘a’) *26^0 +('j' - 'a') * 26^1 + ('k' - 'a') * 26^2
hash(“jkl”) = ('j' - 'a') * 26^0 + ('k' - 'a')* 26^1 + (‘l’ - ‘a’) * 26^2

依據此規律，我們可以總結出來兩個公式：
hash(i-1) = 26^0 * (s[i-1] - ‘a’) + 26^1 * (s[i] - ‘a’) + … + 26^(m-1) * (s[i+m-2] -‘a’)
hash(i) = 26^0 * (s[i] - ‘a’) + … + 26^(m-2) * (s[i + m - 2] - ‘a’) + 26^(m-1) * (s[i+m-2] -‘a’)

i表示源字符串的起始遍歷位置字符下標,m表示目標字符串的長度, s表示源字符串 src。

兩個公式進行運算：hash(i) - hash(i-1) / 26 = 26^(m-1) * (s[i+m-2] -‘a’) - (26^0 * (s[i-1] - ‘a’)) / 26
最終可以得到: hash(i) = (hash(i-1) - s[i-1] -‘a’ ) / 26 + 26^(m-1) * (s[i+m-2] -‘a’) 這樣的計算公式。

這個時候，我們只需要掃描一遍主串即能夠完成目標字符串的匹配， 主串的長度為n, 也就是我們需要O(n)的掃描復雜度。模式串的hash值 和每一個子串的hash值之間的比較是O(1) , 總共需要比較n-m+1個子串的哈希值，所以，這部分的時間復雜度也是O(n)。

所以，RK算法整體的時間復雜度就是O(n)，相比于BF的O(m*n)效率還是高了不少。

Go語言的完整實現如下：

// Calculate a string's hash function
func Hash(str string, m [] int) int {if len(str) == 0 {return 0}var (t intres int = 0)for i := 0; i < len(str); i ++ {t = m[i] * int(str[i] - 'a')res = res + t}return res
}// match the substring with hash function
// we can calculate the string's hash value with below formula
//
// 's' is source string, m is the length of the substring
// h(i-1) = 26^0 * (s[i-1] - 'a') +
// 			26^1 * (s[i] - 'a') + ... +
// 			26^(m-1) * (s[i+m-2] -'a')
//
// h(i) = 26^0 * (s[i] - 'a') + ... +
// 		  26^(m-2) * (s[i + m - 2] - 'a') +
// 		  26^(m-1) * (s[i+m-2] -'a')
//
// so
// h(i) = (h(i-1) - s[i-1] -'a' ) / 26 + 26^(m-1) * (s[i+m-2] -'a')
// we can use the formula to reduce the cpu's calculation
func Rabin_Karp_Hash(str1 string, str2 string) bool {if len(str1) < len(str2) {return false}var m []intvar t int = 1m = append(m,1)for i := 1; i < len(str2) + 1; i ++ {t = t*26m = append(m,t) // m store with 26^0, 26^1, 26^2 ... 26^(len(str2))}str2_hash := Hash(str2, m)fmt.Println(str2_hash)str1_hash := Hash(string([]byte(str1)[:len(str2)]),m)if str2_hash == str1_hash {return  true}for i := 1; i < len(str1) - len(str2) + 1; i ++ {new_hash := (str1_hash - int(str1[i-1]-'a')) / 26 +m[len(str2)-1] * int(str1[i+len(str2) -1] - 'a')if new_hash == str2_hash {return  true} else {str1_hash = new_hash}}return  false
}

總結

以上是生活随笔為你收集整理的Go 语言实现字符串匹配算法 -- BF(Brute Force) 和 RK(Rabin Karp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。