C/C++教程

KMP算法中get_next函数的实现(c代码)

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

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

假设此时 指在图中位置处,又假设通过计算,我们已经知道了 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 的最大公共串长为8next[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代码)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!