資源描述:
《串的模式匹配問題:樸素算法與kmp算法》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。
1、串的模式匹配問題:樸素算法與KMP算法仰之彌高,鉆之彌堅。由儉入奢易,由奢入儉難。刪繁就簡三秋樹,領(lǐng)異標新二月花。南朝四百八十寺,多少樓臺煙雨中。皮之不存,毛將焉附。#include#includeintIndex(char*S,char*T,intpos){//返回字串T在主串S中第pos個字符之后的位置。若不存在,則函數(shù)值為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函數(shù)值并存入數(shù)組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函數(shù)求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("請輸入主字串內(nèi)容");gets(A+1);*A=strlen(A+1);printf("請輸入子字串內(nèi)容");gets(B+1);*B=strlen(B+1);printf("請輸匹配起始位置");scanf("%d",&j);//printf("%d",k);do{printf("請輸入您需要的任務(wù)的序號");printf("1:樸素
9、的模式匹配算法");printf("2:快速模式匹配算法");printf("3:退出");scanf("%d",&id);switch(id){case1:{printf("你調(diào)用了功能1:");printf("樸素的模式匹配算法");k=Index(A,B,j);printf("該位置為:");printf("%d",k);break;}case2:{printf("你調(diào)用了功能2:");printf("快速模式匹配算法");a=Index_KMP(A,
10、B,j);printf("該位置為:");printf("%d",a);break;}case3:{printf("你調(diào)用了功能3:");printf("退出");}}}while(id!=3);#include#includeintIndex(char*S,char*T,intpos){//返回字串T在主串S中第pos個字符之后的位置。若不存在,則函數(shù)值為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函數(shù)值并存入數(shù)組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函數(shù)求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=