字符串与BF算法

1.定义:

BF算法，即暴力 (Brute Force)算法，是普通的 模式匹配 算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个 字符 进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。

2.BF算法思想

相等则继续比较，不相等即查找失败则回退，回退是i（主串的下标），退回到刚才的位置的下一个，j推到0

//成功返回字符串在主串中的下标，失败返回-1

pos:开始查找的主串下标；

3.BF算法的实现

//在主串str的pos位置查找子串sub,找到返回下标，未找到返回-1
//BF(朴素查找算法)

#include<stdio.h>
#include<string.h>
#include<assert.h>


int BF(const char* str, const char* sub, int pos)
{
	assert(str != NULL);
	if (str == NULL || sub == NULL)
		return -1;
	if (pos > strlen(str)||pos<0)
		return -1;
	if (strlen(sub) > strlen(str))
		return -1;
	int lenstr = strlen(str);
	int lensub = strlen(sub);
	int i = pos;
	int j = 0;
	while (i < lenstr && j < lensub)
	{
		if (str[i] == sub[j])
		{
			i++;
			j++;
		}
		/*else
		{
			pos++;
			i = pos;
			j = 0;
		}*/
		else
		{
			i = i - j + 1;
			j = 0;
		}
	}
	//if (sub[j] == '\0')
	//	return pos;
	if (j = lensub)
		return i - j;
	else
		return -1;

}


int main()
{
	const char* str1 = "ababcabcdabcde";
	const char* str2 = "abcd";
	const char* str3 = "abc";


	printf("%d  ", BF(str1, str2, 0));
	printf("%d  ", BF(str1, str2, 5));
	printf("%d  ", BF(str1, str2, 9));

	return 0;
}

4.总结

（1）在主串str的pos位置查找子串sub，找到返回下标，未找到返回-1

（2）思想：相等继续比较，不相等回退，回退时i推到刚才的位置的下一个（i-j+1）

j退到0

（3）利用子串是否遍历完成，来判断查找是否成功，注：不能利用主串来判断

（4）算法时间复杂度BF:O(n*m)