经典算法-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）