题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2087
解题思路：这是KMP算法模板的应用。需要注意的地方就是，这里的子串需要重新取，所以对于j的处理时要改变一下。

版本1

#include <cstdio>
#include <cstring>
#include <cstdlib>
const int maxn = 1010;
int next[maxn];
char str[maxn],pat[maxn];
void getNext(char s[],int len){
	int j=-1;
	next[0]=-1;
	for(int i =1;i<len;i++){
		while(j!=-1&&s[i]!=s[j+1]){
			j=next[j];
		}
	
		if(s[i]==s[j+1]){
		j++;
		}
		next[i]=j;
    }
} 
//统计pattern串在text串中出现的次数
int KMP(char text[],char pattern[]){
	int n=strlen(text);
	int m=strlen(pattern);
	getNext(pattern,m);
	int ans = 0,j=-1;
	for(int i=0;i<n;i++){
		while(j!=-1&&text[i]!=pattern[j+1]){
			j=next[j];
		}
		if(text[i]==pattern[j+1]){
			j++;
		}
		if(j==m-1){
			ans++;
			j=next[0];
		}
	}
	return ans;
} 
int main(){
	while(scanf("%s",str)!=EOF&&str[0]!='#'){
		scanf("%s",pat);
		memset(next,0,sizeof(next));
		int tmp=KMP(str,pat);
    	printf("%d\n",tmp);
	}
	return 0;
}

版本2

根据左神进阶视频讲解改写而成，十分感谢左神，终于让我弄懂了KMP算法。

#include<cstdio>
#include<cstring>
using namespace std;
char str1[1005],str2[1005];
int next[1005];
void getNext(char str[],int len){
	int i=2,cn=0;
	next[0]=-1;
	next[1]=0;
	while(i<len){
		if(str[i-1]==next[cn]) next[i++] = ++cn;
		else if(cn > 0) cn = next[cn];
		else next[i++] = 0;
	}
}
int main(){
	while(scanf("%s",str1)&&str1[0]!='#'){
		scanf("%s",str2);
		int len1 = strlen(str1);
		int len2 = strlen(str2);
		int j=0,i=0,cnt=0;
		getNext(str2,len2);
		while(i<len1){
			if(str1[i] == str2[j]){
				i++; 
				j++;
			}else{ //甲乙没配上，则乙往右推 
				if(next[j]==-1){ //推不动了，乙已经在0位置了，则只能让甲移动 
					i++; 
				}else{ //乙还能推,则推到j的最长前缀的下一个位置 
					j = next[j];  
				} 
			}
			if(j == len2){ //说明已经匹配上str2了，但是还要继续找 
				j=0;
				cnt++;
			} 
		}
		printf("%d\n",cnt);
	}
	return 0;
}