資源描述：
《串匹配BM算法、KMP算法、BF算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、....實驗報告一串匹配問題?班級：_計算機師_學(xué)號：2姓名：_一、實驗題目：給定一個文本,在該文本中查找并定位任意給定字符串。二、實驗?zāi)康模?1)深刻理解并掌握蠻力法的設(shè)計思想;(2)提高應(yīng)用蠻力法設(shè)計算法的技能;(3)理解這樣一個觀點:用蠻力法設(shè)計的算法,一般來說,經(jīng)過適度的努力后,都可以對算法的第一個版本進行一定程度的改良,改進其時間性能。三、實驗要求：(1)實現(xiàn)BF算法;(2)實現(xiàn)BF算法的改進算法:KMP算法和BM算法;(3)對上述3個算法進行時間復(fù)雜性分析,并設(shè)計實驗程序驗證分析結(jié)果。四、算法描述（對算法主要部分進行偽代碼描述或畫出流程圖）BF算法：
2、基本思想：從主串S的第一個字符開始和模式T的第一個字符進行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；若不相等，則從主串S的第二個字符開始和模式T的第一個字符進行比較，重復(fù)上述過程，若T中的字符全部比較完畢，則說明本趟匹配成功；若最后一輪匹配的起始位置是n-m，則主串S中剩下的字符不足夠匹配整個模式T，匹配失敗。這個算法稱為樸素的模式匹配算法，簡稱BF算法。KMP算法：基本思想：1.在串S和串T中分別設(shè)比較的起始下標(biāo)i和j；2.循環(huán)直到S中所剩字符長度小于T的長度或T中所有字符均比較完畢2.1如果S[i]=T[j]，則繼續(xù)比較S和T的下一個字符；否則2.2將j向右滑
3、動到next[j]位置，即j=next[j]；2.3如果j=0，則將i和j分別加1，準(zhǔn)備下一趟比較；2.4如果T中所有字符均比較完畢，則返回匹配的起始下標(biāo)；否則返回0；BM算法：基本思想：BM算法與KMP算法的主要區(qū)別是匹配操作的方向不同。雖然BM算法僅把匹配操作的字符比突順序改為從右向左，但匹配發(fā)生失敗時，模式T右移的計算方法卻發(fā)生了較大的變化。學(xué)習(xí)資料....??開始主串S長度→m模式T長度→n0→ii4、a]=T[b]且b≠na加1b加1b=nYYYNNNKMP算法結(jié)束next[b]→ba-b→ab=-1b加1?學(xué)習(xí)資料....開始i≦主串S長度-1模式T長度-1→jj≧0且S[i]=T[j]i減1j減1j<0YYYNNNBM算法結(jié)束0→a0→b0→z模式T長度-1→ii+DIST(T,S[i])→i???學(xué)習(xí)資料....五、實驗結(jié)果與結(jié)論：（給出測試數(shù)據(jù)以及程序運行結(jié)果，并進行比較，得出自己的結(jié)論）?設(shè)計思想：設(shè)文本串T，模式串為P。首先將T與P進行左對齊，然后進行從右向左比較，若是某趟比較不匹配時，BM算法就采用兩條啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則，來計
5、算模式串向右移動的距離，直到整個匹配過程的結(jié)束。??BE算法：#include#include#includemain(){chars[100];chart[100];inti,a,b,m,n;printf("*****pleaseinputastring:");scanf("%s",s);printf("pleaseinputsearchstring:");scanf("%s",t);m=strlen(s);n=strlen(t);printf("*******BF********");for(i=0
6、;i#include#includemain(){chars[100];chart[100];學(xué)習(xí)資料....inti,a,b,m,n;printf("*****pleaseinputastring:");sca
7、nf("%s",s);printf("pleaseinputsearchstring:");scanf("%s",t);m=strlen(s);n=strlen(t);printf("*******KMP********");for(a=0;a<=m-n;a++){b=0;while(s[a]==t[b]&&b!=n){a++;b++;}if(b==n){printf("success!");return0;}else{b=b+1;a=a-b;}if(b=-1){b++;}elsereturn0;學(xué)習(xí)資料....}printf("nofound!:%s
8、n",&t);ret
