KMP算法通俗解析

本文主要是介绍KMP算法通俗解析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

KMP的算法的历史不过多讲解，直接干最难的部分

先上代码

1.求next数组的代码：（伪代码）

int next[1000];  //next
void Get_next(char s[]){//s 为模串
	next[0]=-1;
	int i=0;
	int j=-1;
    while(s[i]!='\0'){  
    	if(j==-1 || s[i]==s[j]){  /*在这里，j==-1时，为什么也满足呢，因为当j==-1时，进入if主体，i++,j++;也就把next数组的值变为0，这是j的回溯过程*/
    		i++;                    
    		j++;
    		next[i]=j; 
		}
		else
		    j=next[j];//回溯。直到满足s[i]==s[j],如果到最后也没有满足，则j一定==-1,next的值为0
	}
}

2.求解代码：（伪代码）

 int a=strlen(s1);
    int b=strlen(s2);
    int t=0,m=0; 
    while(t<a && m<b){//和next代表过程如出一辙得相似！
    	if(m==-1 || s1[t]==s2[m]){
    		t++;
    		m++;
		}
		else
		   m=next[m];
	}
	if(m>=b)printf("%d",t-b+1);
	else printf("-1");

3.完整代码

#include<cstdio>
#include<cstring>
char s1[1000];
char s2[1000];
int next[1000];
void Get_next(char s[]){
	next[0]=-1;
	int i=0;
	int j=-1;
    while(s[i]!='\0'){
    	if(j==-1 || s[i]==s[j]){
    		i++;
    		j++;
    		next[i]=j;
		}
		else
		    j=next[j];
	}
}
int main(){
	scanf("%s %s",&s1,&s2);
    Get_next(s2); 
    int a=strlen(s1);
    int b=strlen(s2);
    int t=0,m=0; 
    while(t<a && m<b){
    	if(m==-1 || s1[t]==s2[m]){
    		t++;
    		m++;
		}
		else
		   m=next[m];
	}
	if(m>=b)printf("%d",t-b+1);
	else printf("-1");
	return 0;
}

请看详细的注释

这篇关于KMP算法通俗解析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！