基于bf和kmp的串模式匹配算法设计与实现(c语言)

《基于bf和kmp的串模式匹配算法设计与实现(c语言)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构KMF算法//代码#include"stdafx.h"#include"string.h"#include"malloc.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;

2、i<=T[0];i++)T[i]=*(chars+i-1);return1;}}intStrLength(SStringS){//返回串的元素个数returnS[0];}intStrCompare(SStringS,SStringT){//操作结果:若S>T,则返回值>0;若S=T,则返回值=0;若S

3、ring(SStringSub,SStringS,intpos,intlen){//用Sub返回串S的第pos个字符起长度为len的子串。inti;if(pos<1

4、

5、pos>S[0]

6、

7、len<0

8、

9、len>S[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。//其中

10、,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(j>T[0])returni-T[0];elsereturn0;}elsereturn0;}//////////voidget_next(SStringT,intnext[]){/*求模式串T的next函数值并存入数组ne

11、xt算法4.7*/inti=1,j=0;next[1]=0;while(i

12、

13、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;whil

14、e(i<=S[0]&&j<=T[0])if(j==0

15、

16、S[i]==T[j])/*继续比较后继字符*/{++i;++j;}else/*模式串向右移动*/j=next[j];if(j>T[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(

17、"%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("");i=Index_KMP(S,T,m,q);if(i){printf("用KMF得主串和子串在第%d个字符处首次匹配",i);printf

18、("用BF得主串和子串在第%d个字符处首次匹配%d",Index(S,T,m));}elseprintf("子串和主串不匹配");return0;}