串的模式匹配算法 – BF算法详解

BF算法原理

BF算法是一种蛮力算法,其实现过程没有任何技巧,就是简单粗暴地拿一个串同另一个串中的字符一一比对,得到最终结果。

算法目的:确定主串中所含子串第一次出现的位置,这里的子串也称为模式串。

设计思想:
1, 主串和模式串逐个字符进行比较

串的模式匹配算法 – BF算法详解

2, 当出现字符不匹配(失配)时,主串的比较位置重置为起始位置的下一个字符位置,模式串的比较位置重置为起始字符
串的模式匹配算法 – BF算法详解

回溯关系的确定:i = i - j + 1; //主串指针回溯到比较起始位置的下一个字符位置
关键字:循环比较
第一次回溯
因为i=j=0都是从0开始,因此逐一比较时下标相等。回溯下标需要使i=1

第二轮回溯
经过第一次回溯,i的下标比j的下标大1,因此进行i=i-j+1=2,i指针又往前挪移一位

因此i-j是保留之前累积的i>j的差值,然后+1,利用循环便可以继续累加,达到指针不断向前移,回溯到比较起始位置的下一个字符位置的效果。
串的模式匹配算法 – BF算法详解

3, 匹配成功返回主串中匹配串的起始位置,否则返回错误代码串的模式匹配算法 – BF算法详解
简单理解返回位置,此时i=5为结束匹配时主串指针所指下标,j=3,为子串最后位置元素下标即子串长度,+1便表示位置而不是下标。

时间复杂度

设主串长度为m,子串长度为n
该算法最理想的时间复杂度 O(n),n 表示子串的长度,即第一次匹配就成功。

BF 算法最坏情况的时间复杂度为 O(n×m),即两个串每次匹配,都必须匹配至子串的最末尾才能判断匹配失败,因此运行了 n×m 次。

在对数据量大的串进行模式匹配时,算法的效率很低。因此BF 算法还可以改进,就是 KMP 算法,下次再写文章解释。

C++实现代码

int BF(const char* S, const char* T) 
{
	int i = 0, // i主串的起始下标
		j = 0; // j子串的起始下标
	while (i < strlen(S) && j < strlen(T)) 
	{
		if (S[i] == T[j]) 
		{
			i++;
			j++;
		}
		else 
		{
			i = i - j + 1;	//主串指针回溯到比较起始位置的下一个字符位置
			j = 0;			//子串回到起始字符
		}
	}

	//j=strlen(T),说明子串遍历完成,在主串中成功匹配
	if (j == strlen(T)) 
	{
		return i - strlen(T) + 1;
	}
	//跳过if运行到此,为i==strlen(B)的情况,说明已经遍历完主串,匹配失败
	return -1;
}

int main()
{
	int number = BF("aaaaabcaaaacac", "aaaac");
	cout << number;
	return 0;
}
  • 如有不足之处,还望指正
上一篇:服务器上jar启动脚本


下一篇:详细解析Redis中的布隆过滤器及其应用