實驗項目一 串匹配問題

實驗項目一串匹配問題實驗項目一串匹配問題實驗項目一串匹配問題資料僅供參考文件編號：2022年4月實驗項目一串匹配問題版本號：A修改號：1頁次：1.0審核：批準:發(fā)布日期：實驗項目一串匹配問題實驗題目給定一個文本，在該文本中任意查找并定位任意給定字符串。實驗目的深刻理解并掌握蠻力法的設(shè)計思想；提高應用蠻力法設(shè)計算法的技能；理解這樣一個觀點：用蠻力法設(shè)計的算法，一般來說，經(jīng)過適度的努力后，都可以對算法的第一個版本進行一定程度的改良，改進其時間性能。實驗要求實現(xiàn)BF算法；實現(xiàn)BF算法的改進算法：KMP算法和BM算法；對上述三個算法進行時間復雜性分析，并設(shè)計實驗程序驗證分析結(jié)果。實驗提示BF算法，KMP算法和BM算法都是串匹配問題中的經(jīng)典算法，BF算法和KMP算法請參見本章第節(jié)。下面介紹BM算法。BM算法是Boyer和Moore共同設(shè)計的快速匹配算法。BM算法與KMP算法的主要區(qū)別是匹配操作的方向不同。雖然BM算法僅把匹配操作的字符比較順序改為從左到右，但匹配發(fā)生失敗時，模式T右移的計算方法卻發(fā)生了較大的變化。實驗代碼BF算法代碼#include<>#include<>#defineN50voidmain(){chara[N],b[N];printf("請輸入待匹配的兩個字符串，主串a(chǎn)為:\n");gets(a);printf("模式串b為:\n");gets(b);inti=1,j=1,s,t;s=strlen(a);t=strlen(b);while(i<s&&j<t){if(a[i]==b[j]){i++;j++;}else{i=i-j+2;j=1;}}if(j>=t)printf("從a串的%d個字符開始匹配\n",i-j+1);elseprintf("匹配失敗\n");}KMP算法代碼#include<>#include<>#defineN50voidGetNext(chart[],intnext[]){next[1]=0;intj=1,k=0,h;h=strlen(t);while(j<h)if((k==0)||(t[j]==t[k])){j++;k++;next[j]=k;break;}else k=next[k];}voidmain(){chars[N],t[N];intnext[N]={0};printf("請輸入主串s:\n");gets(s);printf("請輸入模式串t:\n");gets(t);inti=1,j=1,k=strlen(s)-1,h=strlen(t)-1;while((i<=k)&&(j<=h)){if(s[i]==t[j]){i++;j++;}else{GetNext(t,next);j=next[j];{if(j==0){i++;j++;}}}}if(j>h)printf("匹配的起始下表為:%d\n",i-j+1);elseprintf("匹配失敗\n");}BM算法代碼#include<>#include<>#defineN50intGetDist(chart[],charc){inti,k=0;intm;m=strlen(t)-1;for(i=m;i>0;i--){if(t[i]==c){ k=i;break; }}if((k!=m)&&(k!=0))returnm-k;elsereturnm;}intBM(chars[],chart[],intn,intm){inti,j;i=m;while(i<=n){j=m;while(j>0&&(s[i]==t[j])){j=j-1;i=i-1;}if(j==0){ returni+1; break; }else{ i+=GetDist(t,s[i]); } }return0;}voidmain(){chars[N],t[N];intr,n,m;printf("請輸入主串s:\n");gets(s);printf("請輸入模式串t:\n");gets(t);n=strlen(s)-1;m=strlen(t)-1;r=BM(s,t,n,m)