串模式匹配之BF和KMP算法

本文简要谈一下串的模式匹配。主要阐述BF算法和KMP算法。力求讲的清楚又简洁。

一 BF算法

核心思想是：对于主串s和模式串t，长度令为len1,len2,   依次遍历主串s，即第一次从位置0开始len2个字符是否与t对应的字符相等，如果完全相等，匹配成功；否则，从下个位置1开始，再次比较从1开始len2个字符是否与t对应的字符相等。。。。

BF算法思路清晰简单，但是每次匹配不成功时都要回溯。

下面直接贴代码：

int BF_Match(char *s, char *t)
{
	int i=0,j=0;
	int k;
	while(i<StringLength(s)&&j<StringLength(t))
	{
		if(s[i]==t[j])
		{
			i++;
			j++;
		}
		else
		{
		i=i-j+1;
		j=0;
		}
	}
	if(j>=StringLength(t))
		k=i-StringLength(t)+1;//匹配成功，返回匹配位置
	else
		k=-1;
	return k;
}

它是一种改进的BF算法。主要消除了主串指针i的回溯，利用已经得到的部分匹配结果将模式串尽可能远的右滑再继续比较。使算法的时间复杂度有BF的O（len1*len2）变为O（len1+len2）.在kmp算法中，串指针i不回溯，由模式串指针j退到某一个位置k上，使模式串t中的k之前的k-1个字符与s中的i之前的k-1个字符相等，这样可以减少匹配的次数

从而提高效率。

当是s[i]!=t[j]  表示主串s的第是s[i-j+1]----->s[i]元素   与模式串t[0]----->t[j-1]元素对应相等；这时为了尽可能右移指针，应该从主串的i-j+1到i-1个子串当中由最后一个往前寻找到

一个最大子串完全匹配。也相当于在模式串的t[0]----->t[j-1]元素中寻找k最大值使前k个元素 与后k个元素对应相等。

下面用next[]数组保存每次比较时，模式串开始的位置。

下面以主串”ababcacabcabbab“和模式串”abcab“为例进行说明

开始时，从第一个元素开始比较，如果t所有元素都匹配到，匹配成功。否则，s[i] !=  t[j]，如果j==0 下一次比较位置 next[j]=-1，即从t[0]开始和s[i+1]比较。

如果k=next[j]不等于0,属于case1 则下一次比较，从t[k]与s[i]开始；如果k=0，case2，下次比较时直接从t[0]与s[i]比较 没有优化。

总之，比较过程中s的指针i一直在增加。模式串指针j可以根据上一次部分匹配结果优化。

下面直接贴代码：

//KMP算法，利用部分匹配结果将模式串右移尽可能远，减少比较次数
//GetNext用来保存每次比较模式串开始的位置
void GetNext(char *t,int *next)
{
	int j=0,k=-1;
	next[0]=-1;
	while(j<StringLength(t)-1)
	{
		if(k==-1||t[j]==t[k])
		{
			j++;k++;
			next[j]=k;
		}
		else
			k=next[k];
	}
}

int KMP_Match(char *s,char *t)
{
	int next[maximum];
	int i=0,j=0;
	int k;
	GetNext(t,next);


	while(i<StringLength(s)&&j<StringLength(t))
	{
		if(j==-1||s[i]==t[j])
		{
			i++;j++;
		}
		else
			j=next[j];
	}
	if(j>=StringLength(t))
		k=i-StringLength(t)+1;//匹配成功，返回匹配位置
	else
		k=-1;
	return k;
}	

void main()
{
	char *a="ababcacabcabbab";
	char *b="abcab";
	int next2[10];
	int i;
	printf("BF匹配位置:%d",BF_Match(a,b));
	printf("KMP匹配位置:%d",KMP_Match(a,b));

	GetNext(b,next2);
	printf("\nnext[]数组为:");
	for(i=0;i<5;i++)
		printf("%d ",next2[i]);
}