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