[数据结构与算法]数据结构-KMP算法

数据结构-KMP算法（C语言版）
KMP算法是三位学者在 BF算法的基础上同时提出的模式匹配的改进算法。
BF算法在模式串中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时,主串的比较位置需要回退。KMP算法在上述情况下,主串位置不需要回退,从而可以大大提高效率.
代码如下：

#include<stdio.h>
#include<stdlib.h> 
#include<string.h>
//这个获取next数组的函数有些难以理解，如果你能搞懂这个函数，KMP算法基本就理解了
void GetNext(char *T,int *next,int lenth){
	//设置初始值 
		next[0]=-1;
		int i=0;
		int j=-1;
	//循环 当i<数组长度时 
	while(i<lenth){
		if(j==-1||T[i]==T[j]){//当j=-1:表示第i+1项的前缀和后缀没有一个相等的
							  //当T[i]==T[j] 表示此时前后缀相等 
			i++;
			j++;
			next[i]=j; 
		}
		else{//当此时的前缀和后缀不相等时0
			j=next[j];//j回溯 指向新的前缀 
		}
	}
}
int KMP(char S[],char T[]){
	int next[20];
	int i=0,j=0;
	int lenS=strlen(S);
	int lenT=strlen(T);
	GetNext(T,next,lenT);
	while(i<lenS&&j<lenT){
		if(j==-1||S[i]==T[j]){
			i++;
			j++;
		}
		else{
			j=next[j];//这里的next数组会有些难以理解
		}
	}
	if(j==lenT){
		return (i-j);
	}
	else{
		return -1;
	}
}


int main()
{
	int k;
	char s[100];
	char t[100]; 
	printf("请输入主串\n") ;
	gets(s);
	printf("请输入模型串\n");
	gets(t);
	//调用KMP算法
	k=KMP(s,t);
	if(k==-1){
		printf("主串中未找到与模型串匹配的子串\n");
	}
	else{
		printf("在主串第%d个字符后找到与模型串匹配的子串\n",k);
	}
	return 0;
}

若有更好的建议或者有什么不足欢迎评论区指出！