根据牛客网左神讲的内容改编而成。KMP算法通过最长前后缀实现了加速，可以通过反证法加以证明，有兴趣的可以参考算法导论。

判断pattern在Text的什么位置出现的

#include<cstdio>
#include<cstring>
int next[100];
int ans=0;
void getNext(char s[], int len){  //此处的next数组存的是i-1前不含本身的最长前后缀长度 
	next[0] = -1; //人为规定 
	next[1] = 0; //人为规定 
	int i = 2;
	int cn = 0; //跳的位置
	while(i < len){
		if(s[i-1] == s[cn]){
			next[i++]=++cn;
		}else if(cn > 0){
			cn=next[cn];
		}else{
			next[i++]=0;
		}
	} 
}
 
 
int KMP(char text[], char pattern[]){
	int n = strlen(text);
	int m = strlen(pattern);
	getNext(pattern, m);
	int i=0,j=0;
	while(i <n && j <m){
		if(text[i] == pattern[j]){
			i++;
			j++;
		}else if(next[j] == -1){ //pattern串已经滑到头了 
			i++;
		}else{
			j = next[j];    //继续滑动至最大前缀 
		}		
	}
	return j==m?(i-j):-1; // 找到则返回找到的位置，找不到返回-1 
}

int main(){
	char text[]="habahwriteababacidufd";
	char pattern[]="ababac";
	int x =KMP(text,pattern);
	printf("%d",x);
	return 0;
}

统计模式串Pattern在匹配串Text中出现的次数

#include<cstdio>
#include<cstring>
int next[100];
void getNext(char s[], int len){  //此处的next数组存的是i-1前不含本身的最长前后缀长度 
	next[0] = -1; //人为规定 
	next[1] = 0; //人为规定 
	int i = 2;
	int cn = 0; //跳的位置
	while(i < len){
		if(s[i-1] == s[cn]){
			next[i++]=++cn;
		}else if(cn > 0){
			cn=next[cn];
		}else{
			next[i++]=0;
		}
	} 
}
 
 
int KMP(char text[], char pattern[]){
	int n = strlen(text);
	int m = strlen(pattern);
	int ans = 0;
	getNext(pattern, m);
	int i=0,j=0;
	while(i <n && j <m){
		if(text[i] == pattern[j]){
			i++;
			j++;
		}else if(next[j] == -1){ //pattern串已经滑到头了 
			i++;
		}else{
			j = next[j];    //继续滑动至最大前缀 
		}
		if(j==m){
			j=next[j-1];
			ans++;
		}		
	}
	return ans;
}

int main(){
	char text[]="habahwriteababacidufd";
	char pattern[]="aba";
	int x =KMP(text,pattern);
	printf("%d",x);
	return 0;
}