串的模式匹配問題：樸素算法與kmp算法

《串的模式匹配問題：樸素算法與kmp算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、串的模式匹配問題：樸素算法與KMP算法仰之彌高，鉆之彌堅(jiān)。由儉入奢易，由奢入儉難。刪繁就簡(jiǎn)三秋樹，領(lǐng)異標(biāo)新二月花。南朝四百八十寺，多少樓臺(tái)煙雨中。皮之不存，毛將焉附。#include#includeintIndex(char*S,char*T,intpos){//返回字串T在主串S中第pos個(gè)字符之后的位置。若不存在，則函數(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個(gè)字符之后的位置的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("請(qǐng)輸入主字串內(nèi)容");gets(A+1);*A=strlen(A+1);printf("請(qǐng)輸入子字串內(nèi)容");gets(B+1);*B=strlen(B+1);printf("請(qǐng)輸匹配起始位置");scanf("%d",&j);//printf("%d",k);do{printf("請(qǐng)輸入您需要的任務(wù)的序號(hào)");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個(gè)字符之后的位置。若不存在，則函數(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個(gè)字符之后的位置的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=