實驗項目一串匹配問題

1、實驗項目一 串匹配問題1. 實驗題目給定一個文本，在該文本中任意查找并定位任意給定字符串。2. 實驗?zāi)康?1)深刻理解并掌握蠻力法的設(shè)計思想；(2)提高應(yīng)用蠻力法設(shè)計算法的技能；(3)理解這樣一個觀點(diǎn)：用蠻力法設(shè)計的算法,一般來說，經(jīng)過適度的努力后，都可以對算法的第一個版本進(jìn)行一定程度的改良,改進(jìn)其時間性能。.實驗要求(1)實現(xiàn)BF算法；(2)實現(xiàn)BF算法的改進(jìn)算法：KMP算法和BM算法；(3)對上述三個算法進(jìn)行時間復(fù)雜性分析，并設(shè)計實驗程序驗證分析結(jié)果。4. 實驗提示BF算法，KMP算法和BM算法都是串匹配問題中的經(jīng)典算法，BF算法和KMP算法請參見本章第節(jié)。下面介紹 BM算法。BM算法是B

2、oyer和Moore共同設(shè)計的快速匹配算法。BM算法與KMP算法的主要區(qū)別是匹配操作的方向不同。雖然BM算法僅把匹配操作的字符比較順序改為從左到右，但匹配發(fā)生失敗時，模式T右移的計算方法卻發(fā)生了較大的變化。5. 實驗代碼 BF算法代碼#in clude#in clude#defi ne N 50void mai n()char aN,bN;printf(”請輸入待匹配的兩個字符串，主串gets(a);printf(模式串 b 為:n);gets(b);int i=1,j=1,s,t;s=strle n( a);t=strle n( b);while(is&j=t)printf(從a串的介字符開

3、始匹配elseprintf(匹配失敗 n);KMP算法代碼#in clude#in cludea 為:n);n ”,i-j+1);#defi ne N 50void GetNext(char t,int next)next1=0;int j=1,k=0,h;h=strle n(t);while(jh)if(k=0)|(tj=tk)j+;k+;n extj=k;break;elsek=n extk;void mai n()char sN,tN;int n extN=0;printf(請輸入主串s:n);gets(s);printf(”請輸入模式串t:n);gets(t);int i=1,j=1,

4、k=strle n( s)-1,h=strle n(t)-1;while(i=k) &(jh):%dn,i-j+1);printf(”匹配的起始下表為elseprintf(匹配失敗 n);BM算法代碼#in clude#in clude#defi ne N 50int GetDist(char t,char c)int i,k=0;int m;m=strle n( t)-1;for(i=m;i0;i-)if(ti=c)k=i;break;if(k!=m)&(k!=0)return m-k;elsereturn m;int BM(char s,char t,int n,int m)int i,j

5、;i=m;while(i0&(si=tj)j=j-1;i=i-1;if(j=0)return i+1;break;elsei+=GetDist(t,si);return 0;void mai n()char sN,tN;int r,n,m;printf(請輸入主串s:n);gets(s);printf(”請輸入模式串t:n);gets(t);n=strle n(s)-1;m=strle n( t)-1;r=BM(s,t ,n ,m);if(r!=0):%dn,r);printf(匹配的起始下標(biāo)為elseprintf(匹配失敗);6.實驗結(jié)果BF算法實驗結(jié)果Bl- -: Duuu-Bent and SettincsXA(i*inist catorel)ucXl. exef請輸人薦嚴(yán)配的兩個字符已 主瓠知LMjeertpu lop棧尢串h為土篤串的丄個字符幵始匹卑Pteia