經典算法—BF算法（字元串比對）

前言

字元串的比對算法也是很經典的一個算法，在面試的時候常常會遇到，而BF算法是字元串模式比對中的一個簡單的算法

1，什麼是BF算法

BF算法，即暴力(Brute Force)算法，是普通的模式比對算法，思想簡單，代碼結構也簡單

BF算法的思想就是将目标串S的第一個字元與模式串T的第一個字元進行比對，若相等，則繼續比較S的第二個字元和 T的第二個字元；若不相等，則比較S的第二個字元和T的第一個字元，依次比較下去，直到得出最後的比對結果。

2，代碼實作

分析：

要完成對于所有字元的比對工作，可以周遊母串，并逐個與子串比較，若相同，則字串比對位後移，若不成功，歸零，當比對成功長度等于字串長度，結束周遊，傳回結果

代碼：

void Get(string a,string b)
{
    int i,j=0;
    for(i=0;i<a.length();i++)
    {
        if(a[i]==b[j])  //若比對成功，則字串比對字元後移一位
        	j++;  
        else        //若不成功，字串重新從第一個開始，母串回溯
       	{
       		i=i-j+1;
       		j=0;
       	}	        
        if(j==b.length())   
        {
            cout<<"Yes Ok";
            return;
        }
    }
    if(j!=b.length()) cout<<"Sorry"
}
           

3，算法的複雜度

若母串長度位m，字串長度位n，則：

最好情況平均時間複雜度位：O(m+n)

最壞情況平均時間複雜度位：O(m*n）