實(shí)驗(yàn)項(xiàng)目一 串匹配問題

實(shí)驗(yàn)項(xiàng)目一串匹配問題實(shí)驗(yàn)項(xiàng)目一串匹配問題實(shí)驗(yàn)項(xiàng)目一串匹配問題資料僅供參考文件編號(hào)：2022年4月實(shí)驗(yàn)項(xiàng)目一串匹配問題版本號(hào)：A修改號(hào)：1頁(yè)次：1.0審核：批準(zhǔn):發(fā)布日期：實(shí)驗(yàn)項(xiàng)目一串匹配問題實(shí)驗(yàn)題目給定一個(gè)文本，在該文本中任意查找并定位任意給定字符串。實(shí)驗(yàn)?zāi)康纳羁汤斫獠⒄莆招U力法的設(shè)計(jì)思想；提高應(yīng)用蠻力法設(shè)計(jì)算法的技能；理解這樣一個(gè)觀點(diǎn)：用蠻力法設(shè)計(jì)的算法，一般來說，經(jīng)過適度的努力后，都可以對(duì)算法的第一個(gè)版本進(jìn)行一定程度的改良，改進(jìn)其時(shí)間性能。實(shí)驗(yàn)要求實(shí)現(xiàn)BF算法；實(shí)現(xiàn)BF算法的改進(jìn)算法：KMP算法和BM算法；對(duì)上述三個(gè)算法進(jìn)行時(shí)間復(fù)雜性分析，并設(shè)計(jì)實(shí)驗(yàn)程序驗(yàn)證分析結(jié)果。實(shí)驗(yàn)提示BF算法，KMP算法和BM算法都是串匹配問題中的經(jīng)典算法，BF算法和KMP算法請(qǐng)參見本章第節(jié)。下面介紹BM算法。BM算法是Boyer和Moore共同設(shè)計(jì)的快速匹配算法。BM算法與KMP算法的主要區(qū)別是匹配操作的方向不同。雖然BM算法僅把匹配操作的字符比較順序改為從左到右，但匹配發(fā)生失敗時(shí)，模式T右移的計(jì)算方法卻發(fā)生了較大的變化。實(shí)驗(yàn)代碼BF算法代碼#include<>#include<>#defineN50voidmain(){chara[N],b[N];printf("請(qǐng)輸入待匹配的兩個(gè)字符串，主串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個(gè)字符開始匹配\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("請(qǐng)輸入主串s:\n");gets(s);printf("請(qǐng)輸入模式串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("請(qǐng)輸入主串s:\n");gets(s);printf("請(qǐng)輸入模式串t:\n");gets(t);n=strlen(s)-1;m=strlen(t)-1;r=BM(s,t,n,m)