引言

本文主要介紹了BF算法的主要思想、具體流程、C語言代碼實現以及自己對該算法的一些感悟

專注于為中小企業(yè)提供網站設計、做網站服務,電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)五大連池免費做網站提供優(yōu)質的服務。我們立足成都，凝聚了一批互聯網行業(yè)人才，有力地推動了上千企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網站建設實現規(guī)模擴充和轉變。

ps：第一次寫博客，如有不妥之地，還望各位大佬指正。

BF算法的介紹 簡介

BF算法，即暴力（Brute Force）算法，是普通的模式匹配算法。

主要思想

其主要思想為將目標串S（以下簡稱S）和模式串T（以下簡稱T）里的字符一一對比尋找（一般從第一個字符開始），如果相同，則比較下一個字符，如果不同，則從S的第二個字符與T的第一個字符開始比較，以此類推，直至最終得到結果。

如果可以在S中尋找到T，我們返回的是相匹配字符串中第一個字符在S串里的下標索引值；如果找不到，我們通常設置為返回-1。

圖解

如： S串為a b a c a d b
? ? ? T串為a c a

我們用i來遍歷S j來遍歷T
則實現過程如下（綠色代表相同，紅色代表不同）：

aba c a d b
aca
此時i = 1，j = 1，匹配失敗，則 j 返回0，i 返回i - j + 1= 1

ps：注意思考為什么i返回的是 i - j + 1

aba c a d b
?ac a
此時 i = 1，j = 0，匹配失敗，則 j 繼續(xù)返回0，i 返回i - j + 1= 2

a ba c ad b
? ??a c a
此時匹配成功，i = 4，j = 2，因此我們需要返回匹配的第一個字符下標索引值 即 returni - j? 即2

另外，我們再用一張圖來舉個例子，加深理解? 如下：

圖中的A串即為我們的T串，B串即為我們的S串。
ps：圖片來源于其他博友

時間復雜度

最理想的情況下? 該算法的時間復雜度為O(n)? 其中n為T串的長度，即一次遍歷就在S中找到了T

最壞的情況下? 該算法的時間復雜度為O(n*m)? 其中 m 和 n
分別為 S 和 T 的長度，即前面每次匹配都不成功，直至到 S 的最后一個字符才與之匹配。

代碼復現 相關代碼

int BF(char* S, char* T)  //S為主串  T為子串
{if (S == NULL || T == NULL) return -1; //保證 S和 T都不為空
	int s = strlen(S);  //計算S串長度
	int t = strlen(T);  //計算T串長度
	int i = 0;  //主串下標
	int j = 0;  //子串下標
	while (i< s && j< t) {if (S[i] == T[j]) {//對應字符相同
			i++;            //i、j往后移位
			j++;
		}
		else {	i = i - j + 1;   //i返回到 i-j+1 的位置
			j = 0;          
		}
	}
	if (j == t)  return i - j; // j == t 說明子串已經全部遍歷 即已經找到與 T相匹配的字符串
	                           // 返回相匹配的第一個字符下標
	return -1;    //沒有匹配結果時 返回-1
}

運行結果

找到的情況

int main()
{printf("%d\n", BF("abacadb", "aca")); //可以找到 返回值應該為2
	
	return 0;
}

運行結果

找不到的情況

int main()
{printf("%d\n", BF("abacadb", "abc"));  //找不到  返回-1
	
	return 0;
}

運行結果

算法的自我總結

BF是一種簡單暴力的算法，通過將兩個字符串內的字符一一比較來得到最終結果。
因為是一種暴力算法，比較無腦，所以實現過程比較簡單，邏輯也不難
適合應用于兩個數據量較小的串之間的匹配。
但如果兩個字符串S和T的數據量過大或者里面的字符比較相似時，由于程序要進行一一比較，所以運算會很多且復雜，效率不高。

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網頁標題：BF算法詳解（C語言實現）-創(chuàng)新互聯
文章出自：http://chinadenli.net/article16/shigg.html

成都網站建設公司_創(chuàng)新互聯，為您提供品牌網站制作、App設計、響應式網站、定制網站、虛擬主機、商城網站

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯