小强在学习的路上

小强在学习的路上

目录

1. KMP算法是什么?

2. KMP算法的由来

2.1 需要要解决的问题

2.2 一开始想到的方法

2.3 KMP算法诞生了

3.KMP算法的详解

4.KMP算法的实现

5.KMP算法的改进


1. KMP算法是什么?

  • KMP算法是一种改进的字符串匹配算法,即可以快速的从主串中找到子串的算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。
  • KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。

2. KMP算法的由来

2.1 需要要解决的问题

我们在数据结构的“串”这一章中提到的问题:主串找子串这个问题,
例如:现在我们有主串:arr1[ ] = "abababc",子串:arr2[ ] = “abc”。

2.2 一开始想到的方法

我们一开始想到的是暴力求解,我们是将子串和主串逐一匹配,如果第一个字符相等就继续匹配第二个字符,直到子串与主串全都匹配成功,就返回子串的位置,一旦其中某两个字符匹配不成功,主串就回到开始匹配字符的下一字符,而子串回到第一字符。
通过以上举例可以看出,传统的暴力求解,需要多次回溯,且第一个字符串和第二个字符串都需要回溯,明显回溯过去也一定是错的,那有没有什么办法让他回溯到特定的位置,不至于像暴力求解一样,产生许多不必要的步骤,于是就有了本篇的重点:KMP算法诞生了

2.3 KMP算法诞生了

KMP算法是一种改进的字符串匹配算法,即可以快速的从主串中找到子串的算法。

3.KMP算法的详解

(1)现在我们先看一个图:第一个长条代表主串,第二个长条代表子串,当发现指针指向的元素不匹配时,指针回溯到第一个元素,这个就是算法效率低的原因,称为幼稚的匹配算法。

数据结构KMP算法详解-LMLPHP

数据结构KMP算法详解-LMLPHP

(2)现在我们看一下聪明的KMP匹配算法是什么样子的:下图还是当发现指针指向的元素不匹配时,移动模式窜,使前缀移动到后缀的地方

数据结构KMP算法详解-LMLPHP

数据结构KMP算法详解-LMLPHP

数据结构KMP算法详解-LMLPHP

(3)这一步弄懂了,KMP算法的精髓就差不多掌握了。事实上,每一个字符前的字符串都有最长相等前后缀,而且最长相等前后缀的长度是我们移位的关键,所以我们单独用一个next数组存储子串的最长相等前后缀的长度。而且next数组的数值只与子串本身有关。
所以next[i]=j,含义是:下标为i 的字符前的字符串最长相等前后缀的长度为j。

数据结构KMP算法详解-LMLPHP

然后把他们放到一个数组中

数据结构KMP算法详解-LMLPHP

4.KMP算法的实现

现在我们分析一下KMP算法的时间复杂度:
KMP算法中多了一个求数组的过程,多消耗了一点点空间。我们设主串s长度为n,子串t的长度为m。求next数组时时间复杂度为O(m),因后面匹配中主串不回溯,比较次数可记为n,所以KMP算法的总时间复杂度为O(m+n),空间复杂度记为O(m)。相比于朴素的模式匹配时间复杂度O(m*n),KMP算法提速是非常大的,这一点点空间消耗换得极高的时间提速是非常有意义的,这种思想也是很重要的。

  • 下面我们一起来欣赏计算机如何求得next数组的
typedef struct
{	
	char data[MaxSize];
	int length;			//串长
} SqString;
//SqString 是串的数据结构
//typedef重命名结构体变量,可以用SqString t定义一个结构体。
void GetNext(SqString t,int next[])		//由模式串t求出next值
{
	int j,k;
	j=0;k=-1;
	next[0]=-1;//第一个字符前无字符串,给值-1
	while (j<t.length-1) 
	//因为next数组中j最大为t.length-1,而每一步next数组赋值都是在j++之后
	//所以最后一次经过while循环时j为t.length-2
	{	
		if (k==-1 || t.data[j]==t.data[k]) 	//k为-1或比较的字符相等时
		{	
			j++;k++;
			next[j]=k;
			//对应字符匹配情况下,s与t指向同步后移
			//通过字符串"aaaaab"求next数组过程想一下这一步的意义
			//printf("(1) j=%d,k=%d,next[%d]=%d\n",j,k,j,k);
       	}
       	else
		{
			k=next[k];
			**//我们现在知道next[k]的值代表的是下标为k的字符前面的字符串最长相等前后缀的长度
			//也表示该处字符不匹配时应该回溯到的字符的下标
			//这个值给k后又进行while循环判断,此时t.data[k]即指最长相等前缀后一个字符**
			//为什么要回退此处进行比较,我们往下接着看。其实原理和上面介绍的KMP原理差不多
			//printf("(2) k=%d\n",k);
		}
	}
}
  • KMP算法代码解释
int KMPIndex(SqString s,SqString t)  //KMP算法
{

	int next[MaxSize],i=0,j=0;
	GetNext(t,next);
	while (i<s.length && j<t.length) 
	{
		if (j==-1 || s.data[i]==t.data[j]) 
		{
			i++;j++;  			//i,j各增1
		}
		else j=next[j]; 		//i不变,j后退,现在知道为什么这样让子串回退了吧
    }
    if (j>=t.length)
		return(i-t.length);  	//返回匹配模式串的首字符下标
    else  
		return(-1);        		//返回不匹配标志
}

5.KMP算法的改进

为什么KMP算法这么强大了还需要改进呢?
大家来看一个例子:
主串s=“aaaaabaaaaac”
子串t=“aaaaac”
这个例子中当‘b’与‘c’不匹配时应该‘b’与’c’前一位的‘a’比,这显然是不匹配的。'c’前的’a’回溯后的字符依然是‘a’。
我们知道没有必要再将‘b’与‘a’比对了,因为回溯后的字符和原字符是相同的,原字符不匹配,回溯后的字符自然不可能匹配。但是KMP算法中依然会将‘b’与回溯到的‘a’进行比对。这就是我们可以改进的地方了。我们改进后的next数组命名为:nextval数组。KMP算法的改进可以简述为: 如果a位字符与它next值指向的b位字符相等,则该a位的nextval就指向b位的nextval值,如果不等,则该a位的nextval值就是它自己a位的next值。 这应该是最浅显的解释了。如字符串"ababaaab"的next数组以及nextval数组分别为:
下标     | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
子串     | a | b | a | b | a | a | a | b |
next     |-1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 |
nextval |-1| 0 |-1 | 0 |-1 | 3 | 1 | 0 |

我们来分析下代码:

void GetNextval(SqString t,int nextval[])  
//由模式串t求出nextval值
{
	int j=0,k=-1;
	nextval[0]=-1;
   	while (j<t.length) 
	{
       	if (k==-1 || t.data[j]==t.data[k]) 
		{	
			j++;k++;
			if (t.data[j]!=t.data[k]) 
//这里的t.data[k]是t.data[j]处字符不匹配而会回溯到的字符
//为什么?因为没有这处if判断的话,此处代码是next[j]=k;
//next[j]不就是t.data[j]不匹配时应该回溯到的字符位置嘛
				nextval[j]=k;
           	else  
				nextval[j]=nextval[k];
//这一个代码含义是不是呼之欲出了?
//此时nextval[j]的值就是就是t.data[j]不匹配时应该回溯到的字符的nextval值
//用较为粗鄙语言表诉:即字符不匹配时回溯两层后对应的字符下标
       	}
       	else  k=nextval[k];    	
	}

}
int KMPIndex1(SqString s,SqString t)    
//修正的KMP算法
//只是next换成了nextval
{
	int nextval[MaxSize],i=0,j=0;
	GetNextval(t,nextval);
	while (i<s.length && j<t.length) 
	{
		if (j==-1 || s.data[i]==t.data[j]) 
		{	
			i++;j++;	
		}
		else j=nextval[j];
	}
	if (j>=t.length)  
		return(i-t.length);
	else
		return(-1);
}
06-29 06:52