首页 > 代码库 > 全局匹配KMP算法

全局匹配KMP算法

 

KMP算法是通过分析模式字符串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。

 

本全局匹配KMP算法针对串的堆式存储数据结构

 

# define MAXSIZE 45  //固定next数组的长度# define OK 1# define ERROR 0typedef int Status;    //返回状态//存放匹配字符串的位置 int indexArray[MAXSIZE] = {0}; //记录匹配字符串出现的次数 int searchIndex = 0; //------------------串的堆分配存储表示typedef struct {	char* ch; //指针域,指向存放串值的存储空间基址	int length; // 整型域:存放串长} HString;

 

  

next函数值仅取决于模式串本身而和相匹配的主串无关,因此从分析器定义出发而用递推的方法求得next函数的值。

 

/*	功能:获取next函数; */void get_next(HString* t,int* next){		 int i = 1,j = 0;	 *(next+1) = 0;	 while(i<t->length)	 {	 	if(j == 0 || *(t->ch+i-1) == *(t->ch+j-1))	 	{	 		i++;	 		j++;	 		*(next+i) = j;	 	}	 	else	 		j = *(next+j);	 }}

  

匹配过程中产生“失配”时,指针i不变,指针j退回到next[j]所知识的位置上重新经行比较,并且当指针j退至0时,指针id和指针j需同时加1。即若主串中的第i个字符和模式中的第1个字符不等,应从主串中的第i+1个字符起重新匹配。

当所匹配记录相等的字符数大于或等于模式串长度时,记录当前位置,即匹配合适的位置,然后继续进行下一组的匹配。

获取next函数算法的时间复杂度为O(m),通常模式串的长度m比主要串的长度n小得多,因此,对整个匹配算法来说是值得的。

在一般情况下,仅有一次模式匹配的时间复杂度为O(m+n),因此全局模式匹配的时间复杂度与匹配成功次数相关。为O(m+n)*b(b次)。

KMP算法的最大特点就是指示主串的指针不需回溯,整个匹配过程中,对主串仅需从头至尾扫描一编。

 

/*	功能:kmp算法 从pos开始,获取串s中所有匹配串t位置,存放在全局函数indexArray中
     初始条件:t非空,且i<=pos<=s->length*/ status Index_KMP(HString* s,HString* t,int pos){ //处理非法输入
     if(!t || pos>1 || pos> s->length)
       return ERROR; //清空 for(int k =0;k<MAXSIZE;k++) { indexArray[k] = 0; } searchIndex = 0; //得到next数组 int j,next[MAXSIZE] = {}; get_next(s,next); if (pos < 0 || pos > s->length) exit(0); int sLength = s->length; int tLength = t->length; int i = pos-1; j = 0; while(i<= sLength && j<=tLength) { if(j == 0 ||*(s->ch + i) == *(t->ch + j)) { ++i; ++j; if(j>= tLength) { indexArray[searchIndex] = i-tLength+1; searchIndex++; } } else{ j = *(next+j); } }
  return OK;}

  高亮显示区域应为if(j== tLength) 。如果写成大于等于,当主串最后位置出现匹配的字符串,即给下列测试代码中的S1赋值为abaabc时,程序给数值赋值后,i继续自增加,造成最后输出结果为1 9 17 25 26。因此,应将if(j>= tLength)改成if(j== tLength)

测试如下:

        HString S1;	InitHString(&S1);	AssigHString(&S1,"abaabc");		HString S;	InitHString(&S);	AssigHString(&S,"abaabcd abaabcf abaabcj abaabck");		Index_KMP(&S,&S1,1);	printf("S1在S中的出现次数:%d\n",searchIndex	);			for(int i=0;i<searchIndex;i++)		printf("%d  ",indexArray[i]);	printf("\n");    

 显示结果为:1 9 17 25 

 

总结,细心调试,同时要增强代码的健壮性。