KMP算法原理解析 (递归分治篇)------- 算法笔记018

梦里梦外; 2023-07-06 05:00 34阅读 0赞

## 基本概念 ##

> KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。  
> —————————引用自百度百科

先来看一个问题：

> 匹配字符串：ababababac  
> 模式匹配串为：ac  
> 要求返回模式匹配串在匹配字符串中的下标，如果匹配失败返回-1

对于这样一个问题我们可以很轻松的想出一个解决算法。  
就是将匹配串ac，按个地与字符串进行匹配,如果匹配成功，则返回对应下标。不匹配则跳到下一个，继续按个与匹配串比较，直到比较完字符串为止。我们称这种算法为BF算法。就是暴力破解。  
具体过程如下：

第一次匹配             第二次匹配          ...       最后一次匹配   
    字符串: ababababac            ababababac                   ababababac
    匹配串: ac（在c处不匹配x）       ac（在a处不匹配x）                    ac （完全符合，匹配成功，返回a的下标）

我们发现这种匹配效率很差，如果编程实现，我们要先遍历字符串数组，接着再遍历匹配串数组，进行挨个比较。时间复杂度就为O(m\*n).  
有没有什么算法能让我们直接跳过中间那些相同的字符，进而简化我们匹配的步骤呢？这样子就引出了KMP算法的概念。这个算法就是最大程度上简化匹配步骤，从而达到匹配字符串的目的。

## 算法核心 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]

## NEXT函数 ##

void kmp_next(char *s,int next[]){ 
    		int j,i;
    		int k=0;//前后缀交集最大数
    		j=0;//后索引
    		i=1;//前索引
    		next[j]=0;
    	while(i<strlen(s)){ 
    		//相同操作
    		if(s[j]==s[i]){ 
    			k++;//多一个相同就多增加1
    			next[i]=k;//对应next数组位置的值
    			i++;//前索引向前
    			j=k;//后索引到k下标处，k是当前数组中前后缀的交集长度，而k下标正好是下一次要比较的地方。很难说清楚这个关系，只可意会，待会模拟一下，加深理解。 
    		}else{ 
    		//这里是比较发现不相同的情况
    			if(j!=0){ //当后索引不为第一个字符时
    				j=next[j-1];//回溯
    			    k=next[j];//回溯后k就要改变
    			}else{ 
    			//当比较到第一个字符时
    			   k=0;	//重置k
    			   next[i]=k;//没有最长前后缀交集
    			   i++;
    			}	
    		}	
    	}	
    }

## KMP实现算法 ##

int kmp_search(char *src,char *des){ 
    	int i,j;
    	int *next=(int *)malloc(sizeof(int)*strlen(des));//分配NEXT数组空间
    	kmp_next(des,next);//根据模式字符串求解NEXT数组
    	i=j=0;//i遍历模式字符串，j遍历匹配字符串
    	
    	while(i<strlen(des)&&j<strlen(src)){ 
    		//如何匹配，指向下一个
    		if(des[i]==src[j]){ 
    			i++;
    			j++;
    		}else{ 
    			//如果是第一个字符不匹配，则将匹配字符指向下一个 
    			if(i-1<0){ 
    				j++; 
    			}else{ 
    				//否则从模式字符串下标next[i-1]处匹配 
    				i=next[i-1];
    			}
    		
    		}
    		
    	}
    	
    	//当子串匹配成功的时候，这个i必然指向strlen(des)这个值
    	//假如不是指向这个值我们都返回-1不管是什么情况都是失败的
    	 
    	if(i==strlen(des)){ 
    		return j-i;//计算下标返回
    	}else{ 
    		return -1; 
    	} 
    
    }

## 模拟KMP算法的执行(加深理解) ##

#### 一. 对NEXT函数的模拟 ####

假设我们要求解的next数组目标模式匹配字符为：a a b a a b a a a
       下标： 0 1 2 3 4 5 6 7 8   
    > 第一次：a a b a a b a a a 
    > next： 0 1
    >        j i  ——>发现i,j处的字符相等，next[i]处为1
     
    > 第二次：a a b a a b a a a 
    > next： 0 1 0
    >          j i ——>i,j处字符不相等,j回溯 
    >        j   i ——>还是不相等,next[i]处为0     
     
    > 第三次：a a b a a b a a a        
    > next： 0 1 0 1
    >        j     i ——>i,j处相等,next[i]处为1
    
    >第四次： a a b a a b a a a   
    > next： 0 1 0 1 2
    >          j     i ——>i,j处相等,next[i]处为2
    
    >第五次： a a b a a b a a a   
    > next： 0 1 0 1 2 3
    >            j     i ——>i,j处相等,next[i]处为3
    
    >第六次： a a b a a b a a a   
    > next： 0 1 0 1 2 3 4
    >              j     i ——>i,j处相等,next[i]处为4
    
    >第七次： a a b a a b a a a   
    > next： 0 1 0 1 2 3 4 5
    >                j     i ——>i,j处相等,next[i]处为5
    
     >第八次： a a b a a b a a a   
    > next：  0 1 0 1 2 3 4 5 1 
    >                   j     i ——>i,j处不相等,j回溯               
    >             j           i ——>i,j处不相等,j回溯      
    >         j               i ——>i,j处相等,next[i]处为1

#### 二. 对kmp\_search函数的模拟 ####

假设被查找的字符串为：a b x a b c a b c a b y
    模式匹配字符串为：			   a b c a b y
    模式匹配字符串的next数组：        0 0 0 1 2 0
      字符串： a b x a b c a b c a b y
    > 第一次： a b c a b y
    >             i
    > next：  0 0 0 1 2 0          
    >：发现在 i 处不匹配，将next[i-1]下标处的字符与x继续匹配
    
     字符串： a b x a b c a b c a b y
    >第二次：     a b c a b y
    >            i  
    >next：      0 0 0 1 2 0      
    >：在第一个字符就不匹配,i++向后继续匹配
    
     字符串： a b x a b c a b c a b y
    >第二次：       a b c a b y
    >                        i  
    >next：        0 0 0 1 2 0      
    >：发现在i处不匹配，将next[i-1]下标处的字符与c继续匹配
    
     字符串： a b x a b c a b c a b y
    >第二次：             a b c a b y
    >                              i  
    >next：              0 0 0 1 2 0      
    >：匹配成功，最后要返回的下标就是左边空出来的位数 6

## 运行 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200216171014632.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200216190758766.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz,size_16,color_FFFFFF,t_70