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

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

1、串的模式匹配问题：朴素算法与KMP算法仰之弥高，钻之弥坚。由俭入奢易，由奢入俭难。删繁就简三秋树，领异标新二月花。南朝四百八十寺，多少楼台烟雨中。皮之不存，毛将焉附。#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

2、]){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

3、

4、T[i]==T[j]){++i;++j;next[i]=j;}elsej=next[j];}return*next;}intIndex_K

5、MP(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

6、

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

8、in(){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+1);printf("请输匹配起始位置");scanf("%d",&j);//printf("%d",k);do{printf("请输入您需要的任务的序号");printf("1:朴素

9、的模式匹配算法");printf("2:快速模式匹配算法");printf("3:退出");scanf("%d",&id);switch(id){case1:{printf("你调用了功能1:");printf("朴素的模式匹配算法");k=Index(A,B,j);printf("该位置为：");printf("%d",k);break;}case2:{printf("你调用了功能2:");printf("快速模式匹配算法");a=Index_KMP(A,

10、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非空，1<=pos<=StrLength(s).inti=pos;i

11、ntj=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

12、

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

14、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

15、

16、S[i]==T[j]){++i;++j;}elsej=