字符串匹配——KMP算法中的next数组理解

本文主要是介绍字符串匹配——KMP算法中的next数组理解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

关于原理就不讲了，只说下我对Next数组的理解，希望可以让你获得灵光一闪。

其实最难的就是是j=Next[j];这么一句话，当时思考了很长时间，终于明白的时候确实很兴奋加得意。

#include<cstdio>
#include<cstring>
void getNext(int *Next,char* src){int i,j;Next[0]=-1;i=0;j=-1;int N=strlen(src);while(i<N-1){if(j==-1||src[i]==src[j]){++i;++j;Next[i]=j;}else{/*理解难点：假设已经存在Next；假设是两个字符串在进行比较。1.	a）假设现在有两个字符串 src （传入的完整字符串，长度为 N ） 和 dest（不完全字符串，从第i个位置到末尾，长度为 N-i ） 进行比较，b）假设Next数组已经存在，则我回溯的时候就有位置了。2.	若 src 从0到第j-1个位置，与dest相同，	但是 src 在第j个位置 与字符串 dest 不相同，3.	则 src 该回溯到Next[j]的位置重新进行比较*/j=Next[j];}}
}int KMPMatch(char *father,char *son){int i,j;i=0;j=0;int next[15];getNext(next,son);while(i<strlen(father)){if(j==-1||father[i]==son[j]){++i;++j;}else{j=next[j];}//src的游标j到达strlen(src),说明dest中存在src子串if(j==strlen(son) )return i-strlen(son);}return -1;}int main(){char dest[]="ABC ABCABD ABC ABD";char src[]="ABC ABD";int res=KMPMatch(dest,src);printf("%d\n",res);return 0;
}

这篇关于字符串匹配——KMP算法中的next数组理解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---