【資料結構】串-模式匹配BF演算法(動態圖解、c++、java)

語言: CN / TW / HK

本文已參與「新人創作禮」活動,一起開啟掘金創作之路。

GitHub同步更新(已分類)Data_Structure_And_Algorithm-Review

公眾號:URLeisure 的複習倉庫 (點選可見公眾號二維碼)

提示:以下是本篇文章正文內容,下面案例可供參考


什麼是模式匹配?

  • 字串的定位運算稱為串的模式匹配串匹配

  • 假設有兩個串 S、T,設 S 為主串,也稱正文串;T 為子串,也稱模式。

  • 在主串S中查詢與模式T相匹配的子串,如果查詢成功,返回匹配的子串第一個字元在主串中的位置。

  • 最笨的辦法就是窮舉S的所有子串,判斷是否與T匹配,該演算法稱為BF(Brute Force)演算法

模式匹配 BF 演算法步驟(動圖)

  1. 從 S 第0個字元開始,與T第0個字元比較。 如果相等,繼續比較下一個字元,否則跳轉向下一步;
  2. 從 S 第1個字元開始,與T第0個字元比較。 如果相等,繼續比較下一個字元,否則跳轉向下一步;
  3. 從 S 第2個字元開始,與T第0個字元比較。 如果相等,繼續比較下一個字元,否則跳轉向下一步; ...

  1. 如果 T 比較完畢,則返回 T 在 S 中第一個字元出現的索引(從零開始);
  2. 如果 S 比較完畢,則返回 -1,說明 T 在 S 中未出現。

設,S = “abcabdcababdcabeac”,T = “abdcabe”,求子串 T 在主串 S 中位置。

先來一遍文字說明,再上圖解。

  1. S[0] == T[0] , S[1] == T[1] , S[2] != T[2] , 跳轉下一步;
  2. S[1] != T[0] , 跳轉下一步;
  3. S[2] != T[0] , 跳轉下一步;
  4. S[3] == T[0] , S[4] == T[1] , S[5] == T[2] , S[6] == T[3] , S[7] == T[4] , S[8] == T[5] , S[9] != T[6] 跳轉下一步;
  5. S[4] != T[0] , 跳轉下一步;
  6. S[5] != T[0] , 跳轉下一步;
  7. S[6] != T[0] , 跳轉下一步;
  8. S[7] == T[0] , S[8] == T[1] , S[9] != T[2] , 跳轉下一步;
  9. S[8] != T[0] , 跳轉下一步;
  10. S[9] == T[0] , S[10] == T[1] , S[11] == T[2] , S[12] == T[3] , S[13] == T[4] , S[14] == T[5] , S[15] == T[6] ;
  11. T 比較完畢,返回 9。

BF

簡單的匹配程式碼

從演算法步驟部分不難看出:

  1. i 的回退位置為 i - j + 1
  2. j 的回退位置為 0

c++程式碼如下(示例):

```cpp int Index_BF(string s, string t) { int i = 0, j = 0; int lens = s.length(); int lent = t.length(); while (i < lens && j < lent) { if (s[i] == t[j]) { i++, j++; continue; } else { i = i - j + 1; j = 0; } }

if (j == lent) {
    return i - j;
}
return -1;

} ```

java程式碼如下(示例):

java public static int index_bf(String s, String t){ int i = 0; int j = 0; while (i < s.length() && j < t.length()) { if (s.charAt(i) == t.charAt(j)) { i++; j++; } else { j = 0; i = i - j + 1; } } if (j == t.length()) { return i - j; } return -1; }

BF 演算法複雜度分析

1. 最好情況:

例如:S = "abcdefg" ,T = “def”。

此時,在匹配時,i 、j 都不需要回退。

平均時間複雜度為 $O(n + m)$

2. 最壞情況:

例如:S = "aaaab" ,T = “ab”。

此時,在最後一次匹配前,i、j 一直在回退。

平均時間複雜度為 $O(n × m)$


總結

  • 在示例比較中,其中一步為: 示例
  • 通過模式匹配BF演算法,i、j 回退為: BF
  • 但通過觀察,我們可以發現,我們完全可以直接這麼比較:

KMP * i 不回退,只 j 回退,這樣時間複雜度就減少一些。( 注:j 前串已和 i 前串相等

此方法便是 KMP演算法


本來打算明天發 KMP 的,但是有些事情需要處理一下,明天更不了 KMP 了 。

只能先發一篇存稿了,下下一篇絕對 KMP。


關注公眾號,感受不同的閱讀體驗

下期預告:資料的順序儲存