計算機(jī)算法實驗報告BF和KMP.doc

天津市大學(xué)軟件學(xué)院實驗報告課程名稱：串匹配算法實驗姓名： 陳小龍 學(xué)號：1150210403班級： 業(yè)務(wù)1114 串匹配問題一、實驗題目：給定一個主串，在該主串中查找并定位任意給定字符串。二、實驗?zāi)康模?1)深刻理解并掌握蠻力法的設(shè)計思想；(2)提高應(yīng)用蠻力法設(shè)計算法的技能；(3)理解這樣一個觀點：用蠻力法設(shè)計的算法，一般來說，經(jīng)過適度的努力后，都可以對算法的第一個版本進(jìn)行一定程度的改良，改進(jìn)其時間性能。三、實驗分析：串匹配問題的BF算法1 在串S中和串T中設(shè)比較的下標(biāo)i=1和j=1; 2 循環(huán)直到S中所剩字符個數(shù)小于T的長度或T中所有字符均比較完 2.1 k=i 2.2 如果Si=Tj,則比較S和T的下一字符,否則 2.2 將i和j回溯(i=k+1; j=1)3 如果T中所有字符均比較完,則匹配成功,返回k 否則匹配失敗,返回0 時間復(fù)雜度：設(shè)匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中比較了（i-1）m次，第i趟成功匹配共比較了m次，所以總共比較了im次，因此平均比較次數(shù)是：i=1n-m+1pi(im)= i=1n-m+11n-m+1(im)= m(n-m+2)2一般情況下，mn,因此最壞情況下時間復(fù)雜度是(nm)。串匹配問題的KMP算法實現(xiàn)過程：在串S和串T中高比較的起始下標(biāo)i和j；循環(huán)直到S中所剩字符小于T的長度或T的所有字符均比較完（如果Si=Tj,則繼續(xù)比較S和T的下一個字符；否則將j向右滑動到nextj位置，即j=nextj;如果j=0,則將i和j分別+1，準(zhǔn)備下趟比較，至于其中的next在此不作詳細(xì)講解）；如果T中所有字符均比較完，則匹配成功，返回匹配的起始下標(biāo)；否則匹配失敗，返回0。時間復(fù)雜度：(n+m)，當(dāng)mn時，KMP算法的時間復(fù)雜性是(n)。四、實驗所用語言和運行環(huán)境C+，運行環(huán)境Microsoft Visual C+ 6.0五、實驗過程的原始記錄BF算法程序代碼#include#includevoid main() cout請輸入主串并且以0和回車結(jié)束endl;char s100;char t100;for(int m=0;msm;if(sm=0)sm=0;break;cout您輸入的主串為：;for(int o=0;ostrlen(s);+o)coutso;coutendl;cout主串長度：;coutstrlen(s); coutendlendl;cout請輸入子串并且以0和回車結(jié)束endl;for(int n=0;ntn;if(tn=0)tn=0;break;cout您輸入的子串為：;for(int a=0;astrlen(t);+a)coutta; coutendl; cout子串長度：; coutstrlen(t);coutendl;coutendl+BF算法+endl; int i,j,k,y=0; for(i=0;istrlen(s)-strlen(t)+1;) k=i; for(j=0;jstrlen(t);) if(si=tj) if(j=strlen(t)-1) cout找到了相同的字串：;cout位置在主串的第i-j+1的位置上; coutendl;y=1;break; +i; +j; else j=0;break;i=k+1;if(y=1)break;if(i=strlen(s)-strlen(t)+1&j!=strlen(t)-1)cout沒有找到可以匹配的子串endl;程序執(zhí)行結(jié)果：查找到了子串 沒有查找到子串KMP算法程序代碼#include#include/前綴函數(shù)值,用于KMP算法int GETNEXT(char t,int b)int NEXT10;NEXT0=-1;int j,k;j=0;k=-1;while(jstrlen(t)if (k=-1)|(tj=tk)j+;k+;NEXTj=k;else k=NEXTk;b=NEXTb;return b;int KMP(char s,char t)int a=0;int b=0;int m,n;m=strlen(s);/主串長度n=strlen(t);/子串長度coutendl+KMP算法+endl;while(a=m-n)while(sa=tb&b!=n)a+;b+;if(b=n)cout找到了相應(yīng)的子串位置在主串：a-b+1endl;return 0;b=GETNEXT(t,b);a=a-b;if(b=-1) b+;cout沒有找到匹配的子串！endl;return 0;void main() cout請輸入主串并且以0和回車結(jié)束endl;char s100;char t100;for(int m=0;msm;if(sm=0)sm=0;break;cout您輸入的主串為：;for(int o=0;ostrlen(s);+o)coutso;coutendl;cout主串長度：;coutstrlen(s); coutendlendl;cout請輸入子串并且以0和回車結(jié)束endl;for(int n=0;ntn;if(tn=0)tn=0;break;cout您輸入的