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

昆明理工大學信息工程與自動化學院學生實驗報告（20102011 ）課程名稱：算法分析與設(shè)計 開課實驗室：計算中心3102010年11月12日年級、專業(yè)、班081學號200810405339姓名趙麗成績實驗項目名稱串匹配問題指導(dǎo)教師吳霖教師評教師簽名：語年 月日一、實驗內(nèi)容和目的1、深刻理解并掌握蠻力算法的設(shè)計思想；2、提高應(yīng)用蠻力算法設(shè)計算法的技能；3力后，都可以對算法的第一個版本進行一定程度的改良，改進其時間性能。二、實驗原理及基本技術(shù)路線圖（方框原理圖）=“ss?s=“tt?t”，在主12 n 12 mST的過程稱為串匹配，也稱模式匹配。串匹配問題屬于易解問題。串匹配問題的特征：n很大，常常需要在大量信息中進行匹配；執(zhí)行頻率高。BF算法：ST的第一個字符進行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；若不相等，則從主串TTSBFKMP算法：STij；STT完畢S[i]=T[j]，STjnext[j]j=next[j]；j=0，ij1，準備下一趟比較；T0；BM算法：BMKMPBMT設(shè)計思想：T，PTPBM距離，直到整個匹配過程的結(jié)束。開始主串S開始主串S長度→m模式T長度→nNa≦m-nYNbnYa1b1YNb=nnext[]bYb=-1結(jié)束Nb1開始主串S長度→m模式T長度→n0→iNi<mY0→bNbnYa1b1Yb=nN結(jié)束BF算法 BF算法KMP算法0→z模式TNS-1Y模式T長度-1→jj≧0且S[i]=T[j]NYi1j1YNj<0i+DIST(T,S[]i結(jié)束BMBM算法三、所用儀器、材料（設(shè)備名稱、型號、規(guī)格等）Windows7，MicrosoftVisualC++6.0四、實驗方法、步驟1、實現(xiàn)BF算法；2、實現(xiàn)BF算法的改進算法:KMP算法和BM算法；3、觀察并記錄運行結(jié)果。五、實驗過程原始記錄(數(shù)據(jù)、圖表、計算等)源程序：#include"stdio.h"#include"conio.h"#include<iostream>//BF算法intBF(chars[],chart[]){inti;inta;intb;intm=strlen(s);//主串長度n=strlen(t); //子串長度printf("\n*****BF*****算法for(i=0;i<m;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[0]=-1;intj,k;j=0;k=-1;while(j<strlen(t)){if((k==-1)||(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(a<=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==-1)b++;}printf("找不到%s\n\n",t);return0;}//滑動距離函數(shù),BMintDIST(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(i<=strlen(s)-1){j=strlen(t)-1;while(j>=0&&s[i]==t[j]){j--;i--;}if(j<0){}else

printf("查找成功!!\n\n");return0;i=i+DIST(t,s[i]);}printf("找不到%s\n\n",t);return0;}voidmain(){chars[]={'\0'}; //intn=10;chart[]={'\0'}; //Tprintf("\n----------串匹配問題 \n");printf("\nscanf("%s",&s);printf("\nT\n