資料結構（串比對—BF算法）

BF算法

BF算法即暴風(Brute Force)算法，是普通的模式比對算法，BF算法的思想就是将目标串S的第一個字元與模式串T的第一個字元進行比對，若相等，則繼續比較S的第二個字元和 T的第二個字元;若不相等，則比較S的第二個字元和T的第一個字元，依次比較下去，直到得出最後的比對結果。BF算法是一種蠻力算法。

BF算法（樸素算法） 思想簡單 效率比較低下

時間複雜度：O(n*m)

n：為S串的長度

m：為P串的長度

具體的過程如圖所示

上圖的主要意思為

定義i，j；讓i來充當S串的下标，j來充當P串的下标，讓S串和P串一個一個比較，如果失配了，則從開始比較的S串的後一位重新與P串一個一個的進行比較，效率較為低下

BF算法過程：

首先判斷

文本串S和模式串P不能為空

S串的長度大于等于P串的長度

如果比較過程失配：i = i-j+1 ; j = 0;

如果j超過P串的長度，則在S串中找到了與P串完全相等的字串，就可以傳回i-j位置（S串中與P串相等的子串的起始位置）

如果整個過程j始終沒有越界，而是最後i越界了，說明沒有找的相等的子串，則傳回-1

參考代碼

#include <stdio.h>
#include <string.h>

int BFAlgorithm(const char *s,const char *p,int pos)     //BF算法   pos為從S串的某一位置開始查找
{
	if(s == NULL || p == NULL)         //s，p不能為空
	{
		return -1;
	}

	int len1 = strlen(s);        //獲得S串長度
	int len2 = strlen(p);        //獲得P串長度

	if(len1<len2)         //s的長度要大于等于p的長度
	{
		return -1;
	}

	int i,j;
	i = pos;
	j = 0;

	while(i<len1)
	{
		if(s[i] == p[j])
		{
			i++;
			j++;
		}
		else
		{
			i = i-j+1;
			j = 0;
		}

		if(j>=len2)
		{
			return i-j;
		}
	}

	return -1;
}

int main()
{
	char *s = "aababcabcdabcde";
	char *p = "abcd";
	printf("%d\n",BFAlgorithm(s,p,11));
	return 0;
}