基于BF和KMP的串模式匹配算法设计与实现(C语言)

数据结构KMF算法//代码#includestdafx.h#includestring.h#includemalloc.h#defineMAXSTRLEN255intk;//定义全局变量typedefcharSString[MAXSTRLEN+1];//0号元素存放串的长度。intStrAssign(SStringT,char*chars){//生成一个其值等于chars的串Tinti;if(strlen(chars)MAXSTRLEN)return0;else{T[0]=strlen(chars);for(i=1;i=T[0];i++)T[i]=*(chars+i-1);return1;}}intStrLength(SStringS){//返回串的元素个数returnS[0];}intStrCompare(SStringS,SStringT){//操作结果:若ST,则返回值0;若S=T,则返回值=0;若ST,则返回值0inti;for(i=1;i=S[0]&&i=T[0];++i)if(S[i]!=T[i])returnS[i]-T[i];returnS[0]-T[0];}///////////////////intSubString(SStringSub,SStringS,intpos,intlen){//用Sub返回串S的第pos个字符起长度为len的子串。inti;if(pos1||posS[0]||len0||lenS[0]-pos+1)return0;for(i=1;i=len;i++)Sub[i]=S[pos+i-1];Sub[0]=len;return1;}///////////intIndex(SStringS,SStringT,intpos){//返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0。//其中,T非空,1≤pos≤StrLength(S)。inti,j;if(1=pos&&pos=S[0]){i=pos;j=1;while(i=S[0]&&j=T[0])if(S[i]==T[j])/*继续比较后继字符*/{++i;++j;}else/*指针后退重新开始匹配*/{i=i-j+2;j=1;}if(jT[0])returni-T[0];elsereturn0;}elsereturn0;}//////////voidget_next(SStringT,intnext[]){/*求模式串T的next函数值并存入数组next算法4.7*/inti=1,j=0;next[1]=0;while(iT[0])if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}elsej=next[j];k=i;}//////////////////////intIndex_KMP(SStringS,SStringT,intpos,intnext[]){/*利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。*//*其中,T非空,1≤pos≤StrLength(S)。算法4.6*/inti=pos,j=1;while(i=S[0]&&j=T[0])if(j==0||S[i]==T[j])/*继续比较后继字符*/{++i;++j;}else/*模式串向右移动*/j=next[j];if(jT[0])/*匹配成功*/returni-T[0];elsereturn0;}intmain(intargc,char*argv[]){intm,i,j,*q;SStringT,S;charp[100];printf(请输入主串);scanf(%s,p);StrAssign(S,p);//生成主串S。printf(请输入子串);scanf(%s,p);StrAssign(T,p);//生成子串T。printf(请输入在哪位置之后);scanf(%d,&m);q=(int*)malloc((i+1)*sizeof(int));//生成T的next数组get_next(T,q);printf(子串的next函数为:);for(j=1;j=k;j++)printf(%d,*(q+j));printf(\n);i=Index_KMP(S,T,m,q);if(i){printf(用KMF得主串和子串在第%d个字符处首次匹配\n,i);printf(用BF得主串和子串在第%d个字符处首次匹配%d,Index(S,T,m));}elseprintf(子串和主串不匹配\n);return0;}