串的模式匹配问题：朴素算法与kmp算法58290

《串的模式匹配问题：朴素算法与kmp算法58290》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、串的模式匹配问题：朴素算法与KMP算法58290#include#includeintIndex(char*S,char*T,intpos){//返回字串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0.//其中，T非空，1<=pos<=StrLength(s).inti=pos;intj=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;}intget_ne

2、xt(char*T,intnext[]){//求模式串T的next函数值并存入数组next。inti=1;next[1]=0;intj=0;while(i

3、

4、T[i]==T[j]){++i;++j;next[i]=j;}elsej=next[j];}return*next;}intIndex_KMP(char*S,char*T,intpos){//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法，其中T非空，1<=pos<=StrLength(S).intnext[100];*next=get_next(T,

5、next);intj=1,i=pos;while(i<=S[0]&&j<=T[0]){if(j==0

6、

7、S[i]==T[j]){++i;++j;}elsej=next[j];}if(j>T[0])returni-T[0];elsereturn0;}voidmain(){intid,j,k,i,a;printf("输入主串、子串和匹配起始位置");charA[20];charB[10];printf("请输入主字串内容");gets(A+1);*A=strlen(A+1);printf("请输入子字串内容");gets(B+1);*B=strlen(B+

8、1);printf("请输匹配起始位置");scanf("%d",&j);//printf("%d",k);do{printf("请输入您需要的任务的序号");printf("1:朴素的模式匹配算法");printf("2:快速模式匹配算法");printf("3:退出");scanf("%d",&id);switch(id){case1:{printf("你调用了功能1:");printf("朴素的模式匹配算法");k=Index(A,B,j);printf("该位置为：");printf("%d",k);break;

9、}case2:{printf("你调用了功能2:");printf("快速模式匹配算法");a=Index_KMP(A,B,j);printf("该位置为：");printf("%d",a);break;}case3:{printf("你调用了功能3:");printf("退出");}}}while(id!=3);#include#includeintIndex(char*S,char*T,intpos){//返回字串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0.//其中，T

10、非空，1<=pos<=StrLength(s).inti=pos;intj=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;}intget_next(char*T,intnext[]){//求模式串T的next函数值并存入数组next。inti=1;next[1]=0;intj=0;while(i

11、

12、T[i]==T[j]){++i;++j;next[i]=j;}elsej=nex

13、t[j];}return*next;}intIndex_KMP(char*S,char*T,intpos){//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法，其中T非空，1<=pos<=StrLength(S).intnext[100];*next=get_next(T,next);intj=1,i=pos;while(i<=S[0]&&j<=T[0]){if(j==0

14、

15、S[i]==T[j]){++i;++j;}elsej=next[j];}if(j>T[0])returni-T[0];elsereturn0;}voidmain(

16、){int