字符串匹配：BF算法和KMP算法

BF算法：朴素的模式匹配算法，用于在主串中定位字串首次出现的位置。

例如：string src="abcnicessa"; string des="nice";

一直用子串的首位与主串的各位相比，直到找到相等的位。

int BF(string src, string des,int pos)
{
	unsigned int i=pos, j=0;
	while (i < src.size() && j < des.size())
	{
		if (src[i] == des[j])//对应的位相等，同时++；
		{
			++i;
			++j;
		}
		else
		{
			i = i - j + 1;//不相等，说明当前次匹配失败，主串回到上次匹配开始的下一位。
			j = 0;//子串回到首位
		}
	}
	if (j >=des.size())//退出的条件是子串的匹配标志大于子串的长度
	{
		return i - des.size(); //返回子串在主串中首次出现的起始位置
	}
	else
	{
		return -1;//失败
	}
}

 

如果想找子串在主串中出现的所有匹配出现的次数，可以把首次出现的起始作为参数传给下一次匹配。

//求子串在主串中出现的位置数组：BF

vector<int> BF_Count_Str(string src, string des, int pos)
{
	vector<int>arr;

	pos = BF(src, des, pos);
	while (pos != -1)
	{
		arr.push_back(pos);
		pos = BF(src, des, pos + des.size());

	}
	return arr;
}

int main()
{
	string src,des;
	
	src = "aaahelloaaahellovvvhellodsf";
	
	des = "hello";

	cout << BF(src, des, 0) << endl;

	vector<int>arr = BF_Count_Str(src, des, 0);
	vector<int>::iterator it = arr.begin();
	for (; it != arr.end(); it++)
	{
		cout << *it << " ";
	}
	return 0;
}

KMP算法：较于朴素的BF算法，增加了子串每次回退的优化，减少了不必要的匹配。

 

下面来看next数组，

 

//串匹配：KMP算法

void get_next(string des,int *next)//获取next数组
{
   	int i, j;
	i = 1; j = 0;
	next[1] = 0;
	while (i < des.size())
	{
		if (j == 0 || des[i] == des[j])
		{
			i++;
			j++;
			next[i] = j;
		}
		else
		{
			j = next[j];
		}
	}
	
}

int KMP(string src, string des, int pos)
{
	char lendes = des.size();
	des = lendes + des;//将串的长度置于0号位置，src[0]存的是串长度。

	char lensrc = src.size();
	src = lensrc + src;

	int i = pos;
	int j = 1;
	
	
	int *next = (int *)malloc(des.size()*sizeof(int));
	get_next(des, next);

	while (i <= src[0] && j <= des[0])
	{
		if ((j==0)||src[i] == des[j])
		{
			++i;
			++j;		
		}
		else
		{
			j = next[j];
		}
	}

	if (j >des[0])
	{
		return i - des[0];
	}
	else
	{
		return -1;
	}
}

//求子串在主串中出现的位置数组：BF

vector<int> BF_Count_Str(string src, string des, int pos)
{
	vector<int>arr;

	pos = BF(src, des, pos);
	while (pos != -1)
	{
		arr.push_back(pos);
		pos = BF(src, des, pos + des.size());

	}
	return arr;
}

int main()
{
	string src,des;
	
	src = "aaahelloaaahellovvvhellodsf";
	
	des = "hello";

	cout << KMP(src, des, 0) << endl;

	vector<int>arr = KMP_Count_Str(src, des, 0);
	vector<int>::iterator it = arr.begin();
	for (; it != arr.end(); it++)
	{
		cout << *it << " ";
	}
	return 0;
}