文章目錄

• BF
• • 思路
  • 實現(xiàn)
• RK
• • 思路
  • 實現(xiàn)

---

字符串匹配是計算機(jī)科學(xué)中最古老、研究最廣泛的問題之一。一個字符串是一個定義在有限字母表∑上的字符序列。例如，ATCTAGAGA是字母表∑ = {A,C,G,T}上的一個字符串。字符串匹配問題就是在一個大的字符串T中搜索某個字符串P的所有出現(xiàn)位置。

為了方便后面講解，在這里先提出幾個概念。

• 主串和模式串，主串即字符串的本體，模式串即用于比對的子串，即我們將要在主串中查找模式串。例如我們要在字符串A中查找字符串B，則A為主串，B為模式串。
• 單模式匹配算法：即在一個主串中匹配一個模式串，例如BF、RK、BM、KMP等算法就是單模式
• 多模式匹配算法：即在一個主串中匹配多個字符串，例如之前講過的Trie樹，以及之后會寫的AC自動機(jī)。

---

BF

思路

BF算法是Brute Force的縮寫，中文名叫做暴力匹配算法，故名思意，其算法簡單粗暴，但對應(yīng)的性能也不高，算法邏輯如下。

如上圖，BF算法的思路就是從主串的每一個位置進(jìn)行對比，如果當(dāng)前位置模式串無法匹配，就移動到下一個位置，繼續(xù)匹配

實現(xiàn)

該算法的實現(xiàn)十分簡單，代碼如下

#include<string> #include<iostream>using namespace std;int bruteForce(const string& str, const string& pattern) {//不滿足條件則直接返回falseif(str.empty() || pattern.empty() || str.size() < pattern.size()){return -1;}int i = 0, j = 0;int len1 = str.size(), len2 = pattern.size();while(i < str.size()){while(j < pattern.size()){//如果當(dāng)前不匹配if(str[i + j] != pattern[j]){i++; //主串移動到下一個位置j = 0; //模式串回到起始位置break;}j++; //如果模式串當(dāng)前位置匹配，則繼續(xù)匹配下一個位置}//如果模式串全部匹配，則返回匹配的位置if(j == pattern.size()){return i;}}return -1; }

可以看出，這種算法存在著大量無意義的匹配，在最壞的情況下，我們需要依次匹配完主串中的所有位置，因此其時間復(fù)雜度高達(dá)O(N * M) N為主串長度，M為模式串長度。

---

RK

思路

那么有什么方法可以減少那些不必要的匹配，提高效率呢？這時候就可以巧妙地借助哈希算法來完成這個任務(wù)。

如果對于哈希不了解的可以查看我往期的博客
高級數(shù)據(jù)結(jié)構(gòu)與算法 | 哈希 ：哈希沖突、負(fù)載因子、哈希函數(shù)、哈希表、哈希桶

RK算法的全稱是RabinKarp，是Rabin 和 Karp這兩位科學(xué)家在BF算法的基礎(chǔ)上，加上了哈希的思想后是實現(xiàn)的。

BF算法的主要缺陷在于模式串會去嘗試匹配主串的任何一個位置，并且其中每次的匹配都會去一個一個字符進(jìn)行對比，導(dǎo)致效率的下降。

而RK算法則想到了一個好方法，可以先進(jìn)行一個預(yù)匹配，即哈希值的匹配，如果哈希值不同則說明字符串不同，沒有比較的意義，而當(dāng)哈希值相同時，為了避免哈希沖突的情況，再進(jìn)行字符串的匹配即可。

由于哈希值只是一個整型，其比較起來的代價比起字符串大大的降低了

不過，哈希值的計算也需要通過遍歷字符串來獲得，那么效率不是又變低了嗎？這時，就可以通過合理的設(shè)計哈希函數(shù)，來解決這個問題。

在這里，我選擇使用最簡單的按位相加來進(jìn)行舉例

首先，我們將模式串以及主串中第一個用來匹配的子串的哈希值計算出來，進(jìn)行比較。

int hashFunc(const string& str) {int hashCode = 0;for(int i = 0; i < str.size(); i++){hashCode += (str[i] - 'a');}return hashCode; }

當(dāng)其不匹配時，我們需要匹配主串的下一個位置，由于字符串發(fā)生變化，哈希值也應(yīng)該發(fā)生變化。

考慮到匹配子串的變化起始就是從主串中向后移動一位，也就是刪除了最高位，增加了最低位，所以我們可以借助這個性質(zhì)，進(jìn)行增量計算，即減去首位的哈希值，加上末尾的哈希值，就可以避免每次都要重復(fù)計算哈希值的問題。

//獲取移動到下一個位置后的字符串哈希值，即減去開頭的哈希值，加上末尾的哈希值 int nextHash(const string& str, int hash, int begin, int end) {hash -= (str[begin] - 'a');hash += (str[end] - 'a');return hash; }

上面這種哈希算法的計算十分簡單，但是也存在著大量的哈希沖突，所以選擇一個合理的哈希算法，對效率的提升有很大的幫助，但是每種哈希算法也存在著一定的缺陷，例如26進(jìn)制，雖然其幾乎避免了哈希沖突，但是在字符串過長時會導(dǎo)致哈希值的溢出，所以要結(jié)合使用場景對哈希函數(shù)進(jìn)行選擇。
由于這里只是算法的一個介紹，就直接使用這種最簡單的哈希函數(shù)。

此時，整個RK算法就包含兩個部分，第一部分是進(jìn)行哈希值的計算，時間復(fù)雜度為O(N)，第二部分就是進(jìn)行字符串的匹配，因為哈希值的比較的時間復(fù)雜度為O(1)，而哈希值的更新也只是簡單的增量計算，也是O(1)，所以整個算法的時間復(fù)雜度為O(N)，但是在最壞情況下，如存在大量的哈希沖突時，每次都需要將進(jìn)行字符串的對比，這時的時間復(fù)雜度就會退化回O(N * M)

實現(xiàn)

算法實現(xiàn)如下

#include<string> #include<iostream>using namespace std;//字符串哈希函數(shù)，這里使用的是最簡單的按位相加 int hashFunc(const string& str) {int hashCode = 0;for(int i = 0; i < str.size(); i++){hashCode += (str[i] - 'a');}return hashCode; }//獲取移動到下一個位置后的字符串哈希值，即減去開頭的哈希值，加上末尾的哈希值 int nextHash(const string& str, int hash, int begin, int end) {hash -= (str[begin] - 'a');hash += (str[end] - 'a');return hash; }int rabinKarp(const string& str, const string& pattern) {//不滿足條件則直接返回falseif(str.empty() || pattern.empty() || str.size() < pattern.size()){return -1;}int len1 = str.size(), len2 = pattern.size();int patternHash = hashFunc(pattern);int subHash = hashFunc(str.substr(0, len2));for(int i = 0; i < (len1 - len2 + 1); i++){//如果當(dāng)前的哈希值相同，則遍歷比較字符串是否也相同，如果不同則沒有必要進(jìn)行比較if(patternHash == subHash && pattern == str.substr(i, len2)){return i; //如果當(dāng)前匹配，則返回匹配主串的起始位置}//如果主串中剩余字符還能與模式串進(jìn)行對比，則更新哈希值if(len1 - i > len2){subHash = nextHash(str, subHash, i, i + len2);}}return -1; }

總結(jié)

以上是生活随笔為你收集整理的字符串匹配算法(一)：BF(BruteForce)算法和RK(RabinKarp)算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。