• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

简述KMP模式匹配算法,next函数和nextval函数

互联网 diligentman 1周前 (10-18) 10次浏览

KMP算法

  首先KMP算法是基于next函数而实现的,与BF算法相比,KMP算法是没有了主串指针回溯的情况。改进后的算法复杂度为O(m+n).

KMP算法的简述
  每一次比较时,当子串与主串不相等的时候,主串的指针不回溯,而是通过next函数所求得的值当作下一位子串开始比较的位置。(即尽可能地向右边滑动一段的距离,从而减少比较的次数)。


KMP算法匹配过程示例
  
第一趟匹配:   a   b   
a   b   c   a   b   c   a   c   b   a   b

           a   b   
c   a   c

  
第二趟匹配:   a   b   a   b   c   a   
b   c   a   c   b   a   b

             a   b   c   a   
c

  
第三趟匹配:   a   b   a   b   c   a   b   c   a   
c   b   a   b

                  a   b   c   a   
c

  首先要解决的是,当主串和子串失配的时候子串要向后
滑动多少,这就要说到
next函数了,
next函数就是计算子串每一位失配的时候应该向后滑动多少。

  
假设此时匹配的关系如下:

    S = S1 S2 … S(i-j+1) S(i-j+2)… S(i-k+1) … S(i-1) 
S(i) … S(n)

    T =         T1  T2 …  T(j-k+1) … T(j-1) 
T(j) … 

    T =                  T1 …   T(k-1) 
T(k) … 

  由上图可以看出来当
S(i)
T(j)不相等时,从
T(j)前面的真子串开始寻找最大匹配的真前缀子串和后缀子串,若如图所示最长的真前缀子串和后缀子串为
K-1,对比
KMP算法示例图,可以看出只需要
滑动使得T(k)与S(i)对齐即可,因为是最大的真前缀子串和最大的真后缀子串,所以当前子串匹配的位置前面的字符,一定与主串对应位置的各个字符相等,这样子滑动子串就避免了主串指针的不断回溯。

  设next[j] = k,则
next[j]表示当子串与主串失配的时候,子串下一位与主串相比的元素的下标

  因此我们可以得到
next的函数:

  当j = 1时,说明当前处于子串的第一个有效值的位置,前面的真子串长度为0,所以next[j] = 0

  当位于其他位置的时候,next[j]的值就是目前已匹配的最长的真前缀子串的下一位。

  每一次
滑动的位数就是当前子串不匹配的位置,前面的
真前缀子串
真后缀子串所相等时的最大子串的长度加1。

  
实际上我们会发现子串滑动的位数与主串并没有什么关系



KMP算法代码

int Index_KMP(SString *S, int pos, SString *T) {


	int next[MAXSIZE] ;
	Get_Next( T, next);
	int i = pos, j = 1;
	while(i <= S->len && j <= T->len) {
		if(S->data[i] == T->data[j] || j == 0) {
			//j == 0是一个判断条件,当子串匹配到第一个字符的时候都没有匹配
			//子串与主串的指针都要向后移动,重新从头开始进行匹配
			++i;
			++j;
		} else {
			j = next[j];
		}
		
	}
	if(j > T->len)
		return(i - T->len);
	else
		return 0;

}

next算法的描述
  首先next函数是基于递推的思想的,KMP算法是基于next函数来实现的。

next的函数值,由上述的定义可以得到next[1] = 0,假设next[j] = k,说明最长的匹配的真前缀子串和后缀子串的长度为k-1,那么next[j+1]有以下两种情况:

  (1)当T[j] = T[k]时,也就是说当T[j]失配的时候重新找到的匹配的位置与他相等,也就是说现在子串前k+1个字符相等,所以next[j+1]时,值为k+1,即next[j+1] = next[j] +1,一定要注意next值的定义。
  (2)当T[j] != T[k]时,这时候求next值的问题我们可以看作是一个模式匹配的问题,匹配的过程中模式串既是主串又是模式串。其中1<k’<k<j,相当于如果当前的失配,那么就向前一直找直到下一位与当前主串的字符相匹配,或者直到子串的第一位还是不匹配,那么主串和子串同时向后移动,这就是while循环的条件,具体如下:
  ①:若T[j] = T[k’],且k’ = next[k],那么next[j+1] = k’+1,即next[j+1] = next[next[k]]+1.
  ②:若T[j] != T[k],则继续比较T[j]和T[next[k’]],即比较T[j]和T[next[next[k]]].
  然后一直这样下去直到k = 0都没有成功,则next[j+1] = 1.


next算法代码

void Get_Next(SString *T,int *next) {
	int i = 1, j = 0;
	next[1] = 0;
	while(i < T->len) {
		if(j == 0 || T->data[i] == T->data[j]) { //相等时,next的值等于j+1
			++i;
			++j;
			next[i] = j;
		} else {
			j = next[j];//往前寻找更小的匹配的子串
		}
	}
}

nextval算法的描述

  这是基于next的算法进行的,弥补next算法的缺陷的。
  主要解决了模式串中大量连续重复的字符,nextval函数减少了主串的无用比较的次数
  假设主串为:‘aaabaaaab’ 子串为:'aaaab’则对应的next函数值为下:
 


    j   1  2  3  4  5


     模式串  a  a  a    a  b


   next[j+1]  0  1  2  3  4
  从匹配的过程中来说,如果已经和j = 4不匹配,那么前面和T[j =4]相等的字符也无需比较了,直接去找下一位与其不同的字符即可。

  若
T[j] = T[next[j]],不需要进行S[i]和T[next[j]]的比较,直接进行S[i]和T[next[next[j]]]的比较,换句话说,此时的next[j] =next[k],将next[j]的值修正为nextval[j].

  若
T[j] != T[next[j]]的话,则当S[i] != T[j]时,还是需要进行S[i] 与 T[next[j]]的比较,因此nextval的值就是k.

nextval算法代码

void Get_NextVal(SString *T, int *next, int *nextval)
{
	int j = 2;//j = 1时,nextval[1]的值默认为 0所以从2开始
	nextval[1] = 0;
	Get_Next( T, next);
	while(j <= T->len)
	{
		if(T->data[j] == T->data[next[j]])
		{
			nextval[j] = next[next[j]];
		}
		else{
			nextval[j] = next[j];
		}
		j++;
	}	
}


喜欢 (0)