字符串模式匹配KMP算法的实现---------“strstr()”函数的实现

strstr()函数原型：extern char *strstr(char *str1, const char *str2);

作用：若str2是str1的子串，则返回str2在str1的首次出现的地址；如果str2不是str1的子串，则返回NULL。

如：

	char str1[]="ababcabcd",str2[]="abcabcd";
	char *s;
	s=strstr(str1,str2);
	if(s){
		while(*s)
		{
			printf("%c",*s++);
		}
	}

输出结果为：abcabcd

下面我们试着自己动手实现一个strstr()函数，使它能够完成相同的功能。

-------------------------------------------------------------------------------------------------------------

目前字符串的模式匹配有两种算法：

暴力匹配算法：

如图：

第一步：从str1和str2的第一个开始比较：

第二步：若指针str1和str2所指的字符相等，则先将str1当前的位置用一个指针（如s1）记录下来，再将str1和str2都往后挪一位继续进行比较，直到匹配失败或者str2指针遇到'\0'。

第三步：如果str2指针遇到'\0'则说明匹配成功，返回s1指针这时s1指针即指向str2在str1的首次出现的地址；

否则要将str1回溯到s1的下一位，str2回溯到首字符位置继续进行比较。直到匹配失败或者str2指针遇到'\0'。如图：

代码实现：

char *my_strstr(char *str1,const char *str2)
{
	assert(str1!=NULL);
	assert(str2!=NULL);
	char *s1=str1,*s2=(char *)str2;
	while(*str1)
	{
		s1=str1;
		while(*s1&&*s2&&*s1==*s2)
		{
			s1++;
			s2++;
		}
		if(!*s2)return str1;
		s2=str2;
		str1++;
	}
	return NULL;
}

这种方法简单暴力，但效率却很低，有没有一种效率更高的算法呢？这就是将要介绍的第二种算法：

KMP算法：

KMP算法和暴力匹配算法最根本的区别在于当匹配失败时，利用已经匹配的信息来有效地挪动str1指针和str2指针，而不是简单地回溯。

如图：

此时匹配失败，按照暴力匹配法，str1这时候要回溯，但是，观察str2字符串，发现没有与'a'相同的字符，所以说明str1和str2已匹配部分也不会有字符'a'存在,如图：

我们就没有必要再将str1回溯到字符'b'上面，这只会是做无用功，我们可以直接将str1指针不动，然后从str2的第一个字符开始和str1进行比较，如图:

这样一来将会省去许多次无用的比较，达到提高算法效率的目的。

那么问题来了，如何使计算机确定str2指针该往哪儿跳呢，这里就要引入一个next[]数组，这个next[]数组决定了如果匹配失败，str2和str1的挪动方法。

这里要引入一个字符串"前缀"和“后缀”的概念，前缀指一个字符串除了最后一个字符的所有长度的顺序组合，

如字符串“abc”，它的前缀分别为"a","ab".

如字符串“abcab”，它的前缀分别为"a","ab","abc","abca".

后缀概念和前缀相似，这里就不再叙述了。

而next[]数组就是根据前缀和后缀来求的，它存放了一个字符串的前缀和后缀相等的位数，这个标准不一，我们这里采用如果前缀和后缀没有相等的，则该next[i]存放-1,否则有一个相等的字符存放0，两个相等的字符存放1，以此类推，next[0]默认为-1。

如果next[i]等于-1，则说明指针str2之前没有与它的首字符相等的字符，这时候str1指针不动，str2指针直接回溯到首字符开始和str1比较；

如果next[i]不等于-1，则说明指针str2之前有与它的首字符相等的字符，这时候还有两种情况：

        一种是str1的首字符就和str2首字符不同，则此时str1要往后走一个，str2继续待在首字符处，再将他俩进行比较；

        另一种是str1和str2已经有部分匹配了，此时str1要不动，str2走到首字符地址+next[i]+2处，此处即为str2中与str2与str1已匹配部分相同的地方的下一位，至于为什么是+2，读者可以在纸上画一下就可以想清楚。

这就是KMP算法匹配失败时指针挪动的特别之处，有了next[i]数组的指引，两个指针都会跳到更加节省时间的部位再开始比较，从而大大提高了算法的效率。

代码如下：

#include<stdio.h>
char *my_strstr(char *str1,const char *str2)
{
	char *ret = (char *)str2;
	char *before,*behind;
	int i=0,n=0,nex,c=0;
	while(*str2++)
	{
		n++;
	}
	int next[n];
	next[0]=-1;
	for(i=1;i<n;i++)
	{
		nex=-1;
		before = ret;
		behind = before + 1;
		while(behind <= (ret+i))
		{
			if(*before==*behind)
			{
				nex++;
				before++;
				behind++;
			}
			else if(nex!=-1){
				nex=-1;
				behind++;
				if(before!=ret)behind--;
				before = ret;
			}
			else 
			{
				behind++;
				if(before!=ret)behind--;
				before = ret;
			}
		}
		next[i]=nex;
	}
	str2=ret;
	i=0;
	while(*str1&&*str2)
	{
		if(*str1==*str2)
		{
			str2++;
			c=0;
		}
		else if(next[i]==-1){
			str2=ret;
			i=-1;
			if(c==0)str1--;
			c=1;
		} 
		else {
			str2=ret+(next[i]+2);
			if(c==0)str1--;
			c=1;
		}
		i++;
		str1++;
	}
	if(!c&&!*str2)
	{
		printf("匹配！\n");
		return str1-n;
	}
	else 
	{
		printf("不匹配！\n");
		return NULL;
	}
	for(i=0;i<n;i++)
	{
		printf("%d ",next[i]);
	}
}

int main()
{
	char str1[]="ababcabcd",str2[]="abcabcd";
	char *s;
	s=my_strstr(str1,str2);
	if(s){
		while(*s)
		{
			printf("%c",*s++);
		}
	}
	return 0;
}

运行结果：