当前位置：首页 > news >正文

【BF算法】

news 来源：原创 2024/7/3 14:57:51

BF 算法

BF 算法精讲

在学习到字符串的匹配问题时，了解到了BF算法和KMP算法。
对比这两个算法，先了解BF算法；

字符串匹配问题，比如说：有一个主串 “abbbcdef” ，子串 “bbc”，该问题就是在主串中查找子串。

肉眼可见，主串中的确存在子串bbc，返回值是子串在主串中第一次出现的首位置下标，也就是返回2.

BF

首先来看一下下图

在这里插入图片描述
以上面的例子为例：
i指向位置和j所指向位置不相等，那么i就往后移一位
如下图：

此时i 和 j 所指位置相等，相等，i 和 j 都后移一位。再比较，相等，继续后移，此时到了下图的位置：

在这个地方不再相等了，所以 j 应该回退到初始位置，那么 i 应该回退到哪里呢？其实很简单， i 和 j 是一起移动的， j 移动了多少位，i 就移动多少位，所以 i 回退的位置应该是 i - j +1
即 i = i - j +1 ，i - j 是 i 和 j 一起移动的长度，再 +1，就是i 从开始的位置往后移了一位。
如下图：
在这里插入图片描述
从该位置再继续开始匹配，第一次相同，第二次也相同，第三次也相同，这个过程就是

if (str[i] == sub[j]) str是主串，sub是子串
{
	i++;
	j++;
}

当j移动到 '\0’的位置时，表明已经匹配成功,
如下图：

在这里插入图片描述
匹配成功，则返回 子串在主串中第一次出现的起始位置 ，
也就是 return i - j;

到了这里， BF 算法的核心就结束了

BF算法其实就是一个个地往下匹配，不相等时主串的 i 走到下一位，子串回到初始位置，也就是朴素的匹配算法。

下面看代码：

int BF(const char* str, const char* sub)
{
	assert(str && sub);
	int i = 0;//记录主串
	int j = 0;//记录子串
	size_t len_dest = strlen(str);//strlen 返回值是size_t
	size_t len_src = strlen(sub);
	if (len_src == 0)
	{
		return 0;//子串为空，返回主串起始位置
	}
	while (i<len_dest)
	{
		while (str[i] == sub[j])
		{     
			i++;
			j++;
		}
		if (j >= len_src )// 子串到了'\0'位置了
		{
			return i - j;//找到了
		}
		//不相等就往下继续匹配
		i = i - j + 1;
		j = 0;
	}
	//退出该循环，说明找完主串都找不到，不存在该子串
	return -1;
}

int main()
{
	printf("%d\n", BF("abbbcdef", "bbc"));
	printf("%d\n", BF("abbbcdef", "bcd"));
	printf("%d\n", BF("abcdef", ""));
	return 0;
}