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