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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了串的模式匹配算法 – BF算法详解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1776字，纯文字阅读大概需要3分钟。

内容图文

BF算法原理

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

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

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

2， 当出现字符不匹配（失配）时，主串的比较位置重置为起始位置的下一个字符位置，模式串的比较位置重置为起始字符

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

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

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

3， 匹配成功返回主串中匹配串的起始位置，否则返回错误代码
简单理解返回位置，此时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;
}

• 如有不足之处，还望指正

内容总结

以上是互联网集市为您收集整理的串的模式匹配算法 – BF算法详解全部内容，希望文章能够帮你解决串的模式匹配算法 – BF算法详解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---