串匹配問題：BF算法、KMP算法、BM算法

昆明理工大學(xué)信息工程與自動化學(xué)院學(xué)生實驗報告（2010一2011學(xué)年第一學(xué)期）課程名稱： 算法分析與設(shè)計 開課實驗室：計算中心3102010年11月12日年級【、專業(yè)、班計科081班學(xué)號200810405339姓名趙麗成績實驗項目名稱串匹配問題指導(dǎo)教師吳霖教師評語教師簽名：年 月日一、 實驗內(nèi)容和目的1、 深刻理解并掌握蠻力算法的設(shè)計思想；2、 提高應(yīng)用蠻力算法設(shè)計算法的技能；3、 理解這樣一個觀點:用蠻力法設(shè)計的算法，一般來說，經(jīng)過適度的努力后，都可以對算法的第一個版本進(jìn)行一定程度的改良，改進(jìn)其時間性能。二、 實驗原理及基本技術(shù)路線圖（方框原理圖）串匹配問題 給定兩個串S二“ss??s”和T二“tt?t”，在主12n 12m串S中查找子串T的過程稱為串匹配，也稱模式匹配。串匹配問題屬于易解問題。串匹配問題的特征：（1） 算法的一次執(zhí)行時間不容忽視：問題規(guī)模n很大，常常需要在大量信息中進(jìn)行匹配；（2） 算法改進(jìn)所取得的積累效益不容忽視：串匹配操作經(jīng)常被調(diào)用,執(zhí)行頻率高。BF算法：基本思想：從主串S的第一個字符開始和模式T的第一個字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；若不相等，則從主串S的第二個字符開始和模式T的第一個字符進(jìn)行比較，重復(fù)上述過程,若T中的字符全部比較完畢，則說明本趟匹配成功；若最后一輪匹配的起始位置是n-m，則主串S中剩下的字符不足夠匹配整個模式T，匹配失敗。這個算法稱為樸素的模式匹配算法，簡稱BF算法。KMP算法：在串S和串T中分別設(shè)比較的起始下標(biāo)i和j；2?循環(huán)直到S中所剩字符長度小于T的長度或T中所有字符均比較完畢2.1如果S[i]=T[j],貝U繼續(xù)比較S和T的下一個字符；否則2.2將j向右滑動到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ā)生了較大的變化。設(shè)計思想：設(shè)文本串T,模式串為P。首先將T與P進(jìn)行左對齊，然后進(jìn)行從右向左比較，若是某趟比較不匹配時，BM算法就采用兩條啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則，來計算模式串向右移動的距離，直到整個匹配過程的結(jié)束。BF算法b加1KMP算法BM算法三、 所用儀器、材料（設(shè)備名稱、型號、規(guī)格等）Windows7,MicrosoftVisualC++6.0四、 實驗方法、步驟1、 實現(xiàn)BF算法；2、 實現(xiàn)BF算法的改進(jìn)算法:KMP算法和BM算法;3、 觀察并記錄運行結(jié)果。五、 實驗過程原始記錄（數(shù)據(jù)、圖表、計算等）源程序：#include"stdio.h"#include"conio.h"#includeviostream>//BF算法intBF(chars[],chart[]){inti;inta;intb;intm,n;m=strlen(s);//主串長度n=strlen(t);〃子串長度printf("\n*****BF*****算法\n");for(i=0;ivm;i++){b=0;a=i;while(s[a]=t[b]&&b!=n){a++;b++;}if(b==n){printf("查找成功!!\n\n");return0;}}printf("找不到%s\n\n",t);return0;}〃前綴函數(shù)值，用于KMP算法intGETNEXT(chart[],intb){intNEXT[10];NEXT[O]=-1;intj,k;j=0;k=-1;while(jvstrlen(t)){f((k==-l)ll(t[j]=t[k])){j++；k++;NEXT[j]=k;}elsek=NEXT[k];}b=NEXT[b];returnb;}〃KMP算法intKMP(chars[],chart[]){inta=0;intb=0;intm,n;m=strlen(s);//主串長度n=strlen(t);〃子串長度printf("\n*****KMP算法*****\n");while(av=m-n){while(s[a]=t[b]&&b!=n){a++;b++;}if(b==n){printf("查找成功!!\n\n");return0;}b=GETNEXT(t,b);a=a-b;if(b=-l)b++;printf("找不到％s\n\n",t);return0;}〃滑動距離函數(shù)，用于BM算法intDIST(chart[],charc){inti=0,x=1;intn;n=strlen(t);while(x&&i!=n-1){if(t[i]==c)x=0;elsei++;}if(i!=n-1)n=n-1-i;returnn;}//BM算法intBM(chars[],chart[]){inta=0;intb=0;inti,j;printf("\n*****BM算法*****\n");intz=0;i=strlen(t)-1;while(iv=strlen(s)-1){j=strlen(t)-1;while(j>=0&&s[i]==t[j]){j--；i--;if(jvO){printf("查找成功!!\n\n");return0;}elsei=i+DIST(t,s[i]);}printf("找不到%s\n\n",t);return0;}voidmain(){chars[]={'\0'}; 〃主串Sintn=10;chart[]={'\0'}; 〃模式Tprintf("\n 串匹配問題 \n");printf("\n輸入主串S\nS=");scanf("%s",&s);printf("\n輸入子串T\nT=");scanf("%s",&t);printf("主串長%d，子串長為％d\n",strlen(s),strlen(t));BF(s,t);〃BF算法KMP(s,t); 〃KMP算法BM(s,t);//BM算法'C:\Users\li\Desktop\算法分折與設(shè)計\目15對\DEbug\串配對總灼串匹配問題輸入主串￡S=ababcabcacbab輸入子串TT=abca