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

10/19 07:57
阅读数 21

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
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部