kmp算法

---

一、kmp算法的核心思想

KMP算法的想法是，设法利用某些已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。

二、具体实现

具体的算法实现不说了，书上都有，很详细。
下面贴上做了对于长连续串next数组的优化的代码

int kmp(const char *src,const char *dst)
{
	int i=0;//记录源串信息
	int j=0;//记录子串信息
	int n=strlen(src);
	int m=strlen(dst);
	//next数组存的是，如果匹配失败，j回到next[j]，i不变，继续比较、
	while(i<n && j<m)//当字符没有到底，进行比较
	{
		if (j==-1 || src[i]==dst[j])//如果当前字符相等，后移继续比较，若不等，取next数组中值，开始比较
		{
			i++; j++;
		}
		else
			j=next[j];
	}
	if (j>=m)
		return i-m;	//返回
	else
		return -1;  //没有找到
}
void GetNext(const char *str)
{
	int m=strlen(str);

	int j=0;int k=-1;
	next[0]=-1;
	while (j<m-1)
	{
		//以前一种符合的状态为基准，判断现在的状态，如果继续符合，值加1，否则回到之前从比
		if(k==-1||str[j]==str[k])//如果刚进来，则k++，并把值存入next数组。
		{
			j++;  k++;
			next[j] = k;
			if (str[j]==str[k])
				next[j] = next[k];
		}
		else
			k=next[k];	//回到之前。
	}
}

三、测试

测试一下：

int main()
{
	char str[20]="aaaabcdabcda";
	char a[10]="abc";
	cout<<str<<endl<<a<<endl;
	GetNext(a);
	cout<<kmp(str,a)<<endl;


	char str1[20]="abcdabcda";
	char a1[10]="aaaabc";
	cout<<str1<<endl<<a1<<endl;
	GetNext(a1);
	cout<<kmp(str,a1)<<endl;
	return 0;
}

结果：