一、BF算法。

BF模式匹配算法比较易于理解和编程实现，但是面对文本较大时，计算机的响应效率会比较低，故也称之为“暴力匹配”。

实现过程：

当需要匹配的位置pos为1时：

?如果元素一样，则i++,j++依次匹配，如果不一样：

那就把i指针回溯到第2位，j移动到模式串的第1位，然后又重新开始这个步骤：

至于回溯位置的理解，个人是采用数学归纳法：

?设此时的 i=M=7,j=N=3 ? M-N表示主串中开始匹配的起始位置的前一项，所以要想产生有效的回溯，则必须 M-N+2 ，以此为例，M-N+2=4+2=6? 刚好是起始位置的后一项。?

 //BF匹配
int BF(HString s,int pos,HString t ){
	int i=pos,j=1;                      //i理解为串s的变量  j理解为串t中的变量
	while(i<=s.len&&j<=t.len){         //当两个串均未到达结尾时
		if(s.ch[i]==t.ch[j]){          //如果串匹配，则依次遍历
			i++;
			j++; 
		}else{                      //如果不匹配，则回溯
			i=i-j+2;  //回溯位置 
			j=1;
		} 
	}
	if(j>=t.len){                    //最后输出
		printf("模式串的起始位置为：%d",(i-t.len));
		return true;
	} else{
		return false;
	}
}

二、KMP算法。

KMP算法简称“无回溯算法”，它重要的点就是这个next值怎么计算，而next[1]=0,next[2]=1这个是没有变动的，其余的next值简单来说就是看之前的串前缀和后缀是否相等。

1.next值的计算

针对? " abaabcac "这个字符串

?next [ 1]= 0，next [2]=1

因为没有真子串，所以子串长度为 0 故next [3] =1。

next [4] ,next [5] 这两个子串都为1，则二者都为 2

next [ 6] 子串为 2, 故next [ 6]=3.以此类推。? 最终next值为? 0 1 1 2 2 3 1 2

2.nextval值的计算。

nextval值可根据next值来判断，一般编程不易用到，多用于数据结构的选择题。

例如上面说到字符串s" abaabcac "???????? next [1-8]的值为：0 1 1 2 2 3 1 2

当j=1时，定义得：nextval[ 1]=0

当j=2时,next [2] =1, s2不等于s1 ,则 nextval [2] =next [2] =1

当j=3时,next [3] =1,? s3等于s1 ,则 nextval [3] =nextval [3] =0

当j=4时,next [4] =2, s4不等于s2，则nextval [4] = next [4] =2

三、整体代码实现。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define false 0
#define true 1
typedef struct {
	char *ch;    //字符数组，若是非空则指向起始地址，若为空则NULL 
	int len;   //长度 
}HString;
//初始化
int HInit(HString *s){
	s->ch=NULL;
	s->len=0;
} 
//串赋值
int HStrAssign(HString *s,const char *chars){
	int i=0;
	while(chars[i]!='\0'){    //确定串长 
		i++;
	}
	s->len=i;
	if(s->ch!=NULL){
		free(s);
	}else{
		s->ch=(char *)malloc((s->len+1)*sizeof(char));//0号单元不用
		if(s==NULL){
			printf("空间申请失败！");
			return false;
		} 
	for( i=1;i<=s->len;i++){   //依次赋值 
		s->ch[i]=chars[i-1];
	}
	}
}
//串遍历
int HSbianli(HString *s){
	if(s->len==0){
		printf("串空！");
		return false; 
	}else{
		int i;
		for(i=1;i<=s->len;i++){
			printf("%c",s->ch[i]);
		}
		return true;
	}
}
 //BF匹配
int BF(HString s,int pos,HString t ){
	int i=pos,j=1;
	while(i<=s.len&&j<=t.len){
		if(s.ch[i]==t.ch[j]){
			i++;
			j++;
		}else{
			i=i-j+2;  //回溯位置 
			j=1;
		} 
	}
	if(j>=t.len){
		printf("模式串的起始位置为：%d",(i-t.len));
		return true;
	} else{
		return false;
	}
}
//KMP匹配
//---------------next算法-----------------
void GetNext(HString s,int next[]){
	int j=1,k=0;
	next[1]=0;
	while(j<s.len){
		if(k==0||s.ch[j]==s.ch[k]){
			++j;++k;
			next[j]=k;
		}else{
			k=next[k];
		}
	}
   for(int j=1;j<=s.len;j++){
   	printf(" %d ",next[j]);
   }
}
//---------------nextval算法-----------------
void GetNextval(HString s,int next[],int nextval[]){
 	int j=2,k=0;
 	printf("\n模式串的next值为：");
	GetNext(s,next);
	nextval[1]=0;
	while(j<=s.len){
		k=next[j];
		if(s.ch[j]==s.ch[k]){
			nextval[j]=nextval[k];
		}else{
			nextval[j]=next[j];
			j++;
		} 
	}
	printf("\n模式串的nextval值为：");
	for(int i=1;i<=s.len;i++){
		printf(" %d ",nextval[i]); 
	}	
}
//-------------------KMP------------------
int KMP(HString s,int pos,HString t,int next[]){
	int i=pos,j=1;
	while(i<=s.len&&j<=t.len){
		if(j==0||s.ch[i]==t.ch[j]){   //相同则继续比较后续字符 
			++i;++j;
		}else{
			j=next[j];                //模式串向右滑动 
		}
		if(j>t.len){
			printf("模式串的起始位置为：%d",(i-t.len));   //匹配成功,返回起始位置 
			return true;
		}
	}
}
int main(){
	HString s;
	HString s1;
	HInit(&s);
	HInit(&s1);
	char a[]={"ababcabcacbab"};
	char b[]=("abcac");
	HStrAssign(&s,a);
	HStrAssign(&s1,b);
	printf("此时匹配串为:");
	HSbianli(&s);
	printf("\n此时模式串为:"); 
	HSbianli(&s1);
	printf("\n进行BF匹配");
	BF(s,1,s1);
	int next[s1.len];
	int nextval[s1.len];
	GetNextval(s1,&next[s1.len],&next[s1.len]);
	printf("\n进行KMP匹配");
	KMP(s,1,s1,&next[s1.len]);
}

结果：