寫在前面：博主是一位普普通通的19屆雙非軟工在讀生，平時最大的愛好就是聽聽歌，逛逛B站。博主很喜歡的一句話花開堪折直須折，莫待無花空折枝：博主的理解是頭一次為人，就應該做自己想做的事，做自己不后悔的事，做自己以后不會留有遺憾的事，做自己覺得有意義的事，不浪費這大好的青春年華。博主寫博客目的是記錄所學到的知識并方便自己復習，在記錄知識的同時獲得部分瀏覽量，得到更多人的認可，滿足小小的成就感，同時在寫博客的途中結交更多志同道合的朋友，讓自己在技術的路上并不孤單。

目錄:
1.BF算法原理
2.BF算法代碼實現
3.BF算法的時間復雜度

1.BF算法原理

BF算法是串的模式匹配算法，通俗地理解，是一種用來判斷兩個串之間是否具有"主串與子串"關系的算法

普通模式匹配算法，其實現過程沒有任何技巧，就是簡單粗暴地拿一個串同另一個串中的字符一一比對，得到最終結果。例如，使用普通模式匹配算法判斷串 A（“abcac”）是否為串 B（“ababcabacabab”）子串的判斷過程如下：首先，將串 A 與串 B 的首字符對齊，然后逐個判斷相對的字符是否相等，如圖 所示：

上圖第一次匹配失敗是由于串 A 與串 B 的第 3 個字符匹配失敗，因此需要將串 A 后移一個字符的位置，繼續同串 B 匹配：

上圖第二次匹配失敗，串 A 繼續向后移動一個字符的位置：

兩串的模式匹配失敗，串 A 繼續移動，最終到下圖：

由此，串 A 與串 B 以供經歷了 6 次匹配的過程才成功，通過整個模式匹配的過程，證明了串 A 是串 B 的子串（串 B 是串 A 的主串）。

2.BF算法代碼實現

#include <stdio.h> #include <string.h> //串普通模式匹配算法的實現函數，其中 B是偽主串，A是偽子串 int mate(char * B,char *A){int i=0,j=0;while (i<strlen(B) && j<strlen(A)) {if (B[i]==A[j]) {i++;j++;}else{i=i-j+1;j=0;}}//跳出循環有兩種可能，i=strlen(B)說明已經遍歷完主串，匹配失敗；j=strlen(A),說明子串遍歷完成，在主串中成功匹配if (j==strlen(A)) {return i-strlen(A)+1;}//運行到此，為i==strlen(B)的情況return 0; } int main() {int number=mate("ababcabcacbab", "abcac");printf("%d",number);return 0; } 運行結果：6

3.BF算法的時間復雜度

該算法最理想的時間復雜度 O(n)，n 表示串 A 的長度，即第一次匹配就成功。
BF 算法最壞情況的時間復雜度為 O(nm)，n 為串 A 的長度，m 為串 B 的長度。例如，串 B 為 “0000000001”，而串 A 為 “01”，這種情況下，兩個串每次匹配，都必須匹配至串 A 的最末尾才能判斷匹配失敗，因此運行了 nm 次。

總結

以上是生活随笔為你收集整理的解析BF(普通串模式匹配算法)算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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