[数据结构与算法] BF算法（Brute-Force）算法原理及C++实现

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> BF算法（Brute-Force）算法原理及C++实现 -> 正文阅读

[数据结构与算法]BF算法（Brute-Force）算法原理及C++实现

BF算法的概念

? 现在有两个串，主串（文本串）M，子串（模式串）P。串的模式匹配就是在主串M中寻找子串的位置，就是子串的定位运算。

? BF算法是串的暴力匹配算法，它的时间复杂度是很高的，也就是采用穷举的方法一个一个检查主串中是否能匹配到子串。

BF算法的原理

??从文本串的指定位置与模式串的第一个位置开始逐个比较字符是否相同。可以设置两个指针i、j分别指向串M、串P的起始位置，比较M[i]和P[j]，如果两个字符相等，i、j都加一（即串M和串P右移一格）；如果M[i]!=P[j]，则将i加一，j=0，进行文本串的下一次比较。

C++代码实现

int Index_BF(string M,string P,int position=0)
{//返回模式串P在主串中第position个字符开始第一次出现的位置。如果不存在,返回-1 
//其中，P非空，0<=position<=M.length 
	int i=position,j=0;
	//初始化，i是M的指针，j是P的指针 
	while(i<M.length()&&j<P.length())
	{
		if(M[i]==P[j])
		{
			++i;
			++j;
		}
		else
		{
			i=i-j+1;
			j=0;
		}
	} 
	//指针成功完成所有比对，匹配成功 
	if(j>=P.length())
		return i-P.length();
    //匹配失败，说明文本串中不存在模式串，返回-1
	else
		return -1;
}