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

一、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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

如有不足之处，还望指正 ¹。

---

1. 如果对您有帮助可以点赞、收藏、关注，将会是我最大的动力 ↩︎