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;
}

请看详细的注释

上一篇:javaweb学习--javabean


下一篇:C 字符及ASCII值