計(jì)算機(jī)算法實(shí)驗(yàn)報(bào)告BF和KMP.doc

天津市大學(xué)軟件學(xué)院實(shí)驗(yàn)報(bào)告課程名稱：串匹配算法實(shí)驗(yàn)姓名： 陳小龍 學(xué)號(hào)：1150210403班級(jí)： 業(yè)務(wù)1114 串匹配問(wèn)題一、實(shí)驗(yàn)題目：給定一個(gè)主串，在該主串中查找并定位任意給定字符串。二、實(shí)驗(yàn)?zāi)康模?1)深刻理解并掌握蠻力法的設(shè)計(jì)思想；(2)提高應(yīng)用蠻力法設(shè)計(jì)算法的技能；(3)理解這樣一個(gè)觀點(diǎn)：用蠻力法設(shè)計(jì)的算法，一般來(lái)說(shuō)，經(jīng)過(guò)適度的努力后，都可以對(duì)算法的第一個(gè)版本進(jìn)行一定程度的改良，改進(jìn)其時(shí)間性能。三、實(shí)驗(yàn)分析：串匹配問(wèn)題的BF算法1 在串S中和串T中設(shè)比較的下標(biāo)i=1和j=1; 2 循環(huán)直到S中所剩字符個(gè)數(shù)小于T的長(zhǎng)度或T中所有字符均比較完 2.1 k=i 2.2 如果Si=Tj,則比較S和T的下一字符,否則 2.2 將i和j回溯(i=k+1; j=1)3 如果T中所有字符均比較完,則匹配成功,返回k 否則匹配失敗,返回0 時(shí)間復(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,因此最壞情況下時(shí)間復(fù)雜度是(nm)。串匹配問(wèn)題的KMP算法實(shí)現(xiàn)過(guò)程：在串S和串T中高比較的起始下標(biāo)i和j；循環(huán)直到S中所剩字符小于T的長(zhǎng)度或T的所有字符均比較完（如果Si=Tj,則繼續(xù)比較S和T的下一個(gè)字符；否則將j向右滑動(dòng)到nextj位置，即j=nextj;如果j=0,則將i和j分別+1，準(zhǔn)備下趟比較，至于其中的next在此不作詳細(xì)講解）；如果T中所有字符均比較完，則匹配成功，返回匹配的起始下標(biāo)；否則匹配失敗，返回0。時(shí)間復(fù)雜度：(n+m)，當(dāng)mn時(shí)，KMP算法的時(shí)間復(fù)雜性是(n)。四、實(shí)驗(yàn)所用語(yǔ)言和運(yùn)行環(huán)境C+，運(yùn)行環(huán)境Microsoft Visual C+ 6.0五、實(shí)驗(yàn)過(guò)程的原始記錄BF算法程序代碼#include#includevoid main() cout請(qǐng)輸入主串并且以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主串長(zhǎng)度：;coutstrlen(s); coutendlendl;cout請(qǐng)輸入子串并且以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子串長(zhǎng)度：; 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);/主串長(zhǎng)度n=strlen(t);/子串長(zhǎng)度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請(qǐng)輸入主串并且以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主串長(zhǎng)度：;coutstrlen(s); coutendlendl;cout請(qǐng)輸入子串并且以0和回車結(jié)束endl;for(int n=0;ntn;if(tn=0)tn=0;break;cout您輸入的