KMP算法学习

本文主要是介绍KMP算法学习，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

在百度词条里找到了这个，感觉还是不是很好理解。
我们知道KMP是在BF算法上面改进而来的，BF通过一遍遍的对比，算法复杂度最大为（n*m）最小为（m+n），而KMP可以直接把算法复杂度控制在（m+n）。
同样是对比，KMP优势就在于不是一个个去对比，而是在对比之后能够直接跳转到对应的跳转位置。
假如我们现在需要的主数组a为：abababababca （i控制）而子数组为b：abababca （j控制），在第一次对比不符合时，KMP可以选择i跳到第四个出现的a上，而不是第一个a后面的b。这样就能在主函数大的时候
所以，我们应该如何去进行跳转？

因此我们需要一个next【】来得知跳转的位置。
这里的next【】就是在某个位置前字符串中他们前缀和后缀交集的最大长度。
这里解释一下前缀，比如abcde 它的前缀就有[a] [ab] [abc] [abcd] 后缀就有[bcde] [cde] [de] [e]
这里交集就是0即e +1位置上的next为0；

abababc为例
前缀有a ab aba abab ababa ababab
后缀有c bc abc babc ababc bababc
这里的交集就是 0 故c +1位置next为0；
ababab：
前缀：ababa abab aba ab a
后缀：babab abab bab ab b
交集：abab ab
最大长度：4
所以b +1位置上next为4；

接下来就是next的代码：

void getNext(char* p,int *next)
{
	next[0] = -1;
	int i = 0, j = -1;
	while (i < strlen(p))
	{
		if (j == -1 || p[i] == p[j])
		{
			i++;
			j++;
			next[i] = j;
		}
		else if (p[i] != p[j])
		{
			j = next[j];
		}
	}
}

KMP：

int KMP(char* t, char* p,int *next)
{
	int i = 0, j = 0;
	while (i < strlen(t) && j < strlen(p))
	{
		if (j == -1 || t[i] == p[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j == strlen(p))
	{
		return i - j;

	}
	else {
		return -1;
	}
}

若有不足欢迎补充。

这篇关于KMP算法学习的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！