經典演算法—BF演算法（字元串匹配）

• 2020 年 11 月 30 日
• 筆記
• 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）