KMP算法中get_next函数的实现（c代码）

本文主要是介绍KMP算法中get_next函数的实现（c代码），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

现在，我们有这样的一段目标串，来对它求next

假设此时 j 指在图中位置处，又假设通过计算，我们已经知道了 next[j-1] 的值。那么 j-1 处的最大公共串如上图黄色框框。

 j-1 处最大公共串所指的下标为上图蓝色箭头 next[j-1] ，在此时我们只需要比较j处字符是否和next[j-1]+1 处字符相等，若相等，正如上图情况，那么 next[j] = next[j-1]+1。

 所以，我们得到 j 处的最大公共串为上图，最大公共串长度为3, next[j-1]+1 = 2。

好了，让我们继续往下操作： 

现在，经过上述n次的循环，j已经来的了上图这个位置，并且我们得到了 j-1 的最大公共串长为8，next[j-1] = 7。

为什么next[j-1]不等于8呢？

因为字符串的下标起始是0，我们要找的和 j 比较的字符的下标是前缀公共字符串的最后一个字符下标+1。要是我们把next[j-1]记做了8，位置就不对了。记住next的本质是来帮助我们找前缀公共字符串的最后一个下标的。

我们又来比较 next[j-1]+1 与 j 处的字符是否相等，阿欧，很不幸运。这时候不相等了。

那怎么办呢？别着急，接着往下看。

虽然但是，上述匹配失败了，但是我们依旧知道j-1处的公共字符串，这两段长得一模一样的前后缀字符串。（后面的图可能有些眼花缭乱）

而在下标为 next[j-1] 处的公共字符串呢，因为next求出来了我们是知道的，请看下图蓝色框框：

 那么，关于j-1处的公共字符串，也可以得到下图：

 所以，我们又又又得到下图：

 所以，前后两段的子串是不是长得一模一样呢。

我们来捋一捋上面的思路：

1. j-1 处的公共字符串 ，前缀 abaabbab 和后缀 abaabbab 是长得一模一样的

2.这个前缀 abaabbab 实际上是当下标为 next[j-1] 时的字符串，我们暂且把 next[j-1] 记为 i 。

3.i 处的公共字符串是 ab 。也就是 i 处的前缀ab 和 后缀ab 是一样的

4.i 前的串 和  j-1 处后缀字符串一模一样，那么 j-1 的后缀字符串的两段也能找到相同的前缀ab和后缀ab ，我们可以做一个转换 i 的前缀与 j-1 的前缀 ab ab 相等 ，i 的后缀与 j-1 的后缀相等，那么 i 的前缀ab 就等于 j 的后缀ab

不知道各位看官能否理解，我的废话文学令人捉急哈哈哈

那么我们继续：

 现在，我们来比较next[i]+1 与 j 所指的字符串是否相等，又不相等。我们再重复上述操作。

 又令 i = next[i]

此时，i 前字符串的没有公共串了，next[i] = -1 ，我们让下标为 next[i]+1 和 j 的字符做比较，也就是a和b做比较，还不一样。

好了，我们又令 i=next[i] ， i 等于-1了，说明了 j 就没有公共字符串，令next[j]=-1，至此我们就求到了 j 位置的 next。

现在，就来编写代码吧：

void get_next(char T[],int next[]){
	int len_T = strlen(T); 
	int i,j;
	
	next[0] = -1;
	for(j=1;j<len_T;j++){
		i = next[j-1];

		if(T[j]==T[i+1]){
			next[j]=i+1;
		}
		while(T[j]!=T[i+1]&&i>=0){
			i = next[i];
		}
		if(T[j]==T[i+1]) next[j] = i+1;
		else next[j]=-1;
	}

} 

以上是基于浙江大学数据结构课程中讲解KMP算法的next函数实现的，谢谢各位看官啦，希望各位大佬能给我这个小菜狗指出不足呀！

这篇关于KMP算法中get_next函数的实现（c代码）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！