串匹配算法——BF算法

相当于枚举，用主串S的每一个字符作为起始位置，和子串P进行比对。如果在S串中找到了和P串相等的，则返回本次查找的起始位置。当S[i] = P[j]，i和j都向后走，即i++,j++，再判断你S[i] 和P[j]是否匹配，如果匹配继续i++，j++，如果不匹配，i回到第一个和j匹配的字符的后一个字符的位置 。即如下图，此时S[i] == P[j]，i和j都向后走，i一直走到下一个a，j走到d，发现S[i] != P[j]，所以i回到a的字符后面，即b位置（i-j+1），j回到下标0位置。

// s是主串 p是子串 pos是从s的pos位置开始查找
// 时间复杂度： O(n*m)
int BF(char* s, char* p, int pos)
{
	if (s == NULL || p == NULL || pos < 0) return -1;
	
	int lens = strlen(s);
	int lenp = strlen(p);
	if (lens - pos < lenp) return -1;// s串从pos到结尾的长度如果小于p串的长度，则s串中不可能有p串

	int i = pos;//s串下标 
	int j = 0;//p串下标
	while (i < lens && j < lenp)
	{
		if (s[i] == p[j])
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1;
			j = 0;
		}
	}
	// 上面的循环已经将p串遍历了一遍，在s串中找到了p串
	if (j == lenp)//说明在s串中找到了p串
	{
		return i - j;//匹配串的第一个字符的下标
	}
	return -1;
}