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

天津市大學(xué)軟件學(xué)院

實(shí)驗(yàn)報(bào)告課程名稱:串匹配算法實(shí)驗(yàn)姓名：學(xué)號(hào)：班級(jí)：業(yè)務(wù)1114串匹配問(wèn)題一、實(shí)驗(yàn)題目：給定一個(gè)主串，在該主串中查找并定位任意給定字符串。二、實(shí)驗(yàn)?zāi)康模荷羁汤斫獠⒄莆招U力法的設(shè)計(jì)思想；提高應(yīng)用蠻力法設(shè)計(jì)算法的技能；理解這樣一個(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中所有字符均比較完k=i2.2如果S[i]=T[j],則比較S和T的下一字符，否則將i和j回溯(i=k+1;j=1)3如果T中所有字符均比較完，則匹配成功，返回k否則匹配失敗，返回0時(shí)間復(fù)雜度：設(shè)匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中比較了(i-1)■:m次，第i趟成功匹配共比較了m次，所以總共比較了i■:m次，因此平均比較次數(shù)是：:"=7-pi，(i，m)d「"='(i‘m)=^^一般情況下，m<<n,因此最壞情況下時(shí)間復(fù)雜度是0(n，：m)。串匹配問(wèn)題的KMP算法實(shí)現(xiàn)過(guò)程：在串S和串T中高比較的起始下標(biāo)i和j；循環(huán)直到S中所剩字符小于T的長(zhǎng)度或T的所有字符均比較完(如果S[i]=T[j],則繼續(xù)比較S和T的下一個(gè)字符；否則將j向右滑動(dòng)到next[j]位置，即j=next[j];如果j=0,則將i和j分別+1，準(zhǔn)備下趟比較，至于其中的next在此不作詳細(xì)講解)；如果T中所有字符均比較完，則匹配成功，返回匹配的起始下標(biāo)；否則匹配失敗，返回0。時(shí)間復(fù)雜度：0(n-m)，當(dāng)m<<n時(shí)，KMP算法的時(shí)間復(fù)雜性是0(n)。四、實(shí)驗(yàn)所用語(yǔ)言和運(yùn)行環(huán)境C++，運(yùn)行環(huán)境MicrosoftVisualC++6.0五、實(shí)驗(yàn)過(guò)程的原始記錄BF算法程序代碼#include<iostream.h>#include<string>voidmain(){cout<<"請(qǐng)輸入主串并且以0和回車結(jié)束"<<endl;chars[100];chart[100];for(intm=0;m<100;m++){cin>>s[m];if(s[m]=='0'){s[m]='\0';break;}}cout<<"您輸入的主串為：〃；for(into=0;o<strlen(s);++o){cout<<s[o];}cout<<endl;cout<<"主串長(zhǎng)度：〃；cout<<strlen(s);cout<<endl<<endl;cout<<"請(qǐng)輸入子串并且以0和回車結(jié)束"<<endl;for(intn=0;n<100;n++){cin>>t[n];if(t[n]=='0'){t[n]='\0';break;}}cout<<"您輸入的子串為：〃；for(inta=0;a<strlen(t);++a){cout<<t[a];}cout<<endl;cout<<"子串長(zhǎng)度：〃；cout<<strlen(t);cout<<endl;cout<<endl<<"++++++++BF算法++++++++"<<endl;inti,j,k,y=0;for(i=0;i<strlen(s)-strlen(t)+1;){k=i;for(j=0;j<strlen(t);)

if(s[i]==t[j]){if(j==strlen(t)-1){cout<<"找到了相同的字串：〃；cout<<"位置在主串的第〃<<i-j+1<<〃的位置上〃;cout<<endl;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<<"沒(méi)有找到可以匹配的子串〃<<endl;}}程序執(zhí)行結(jié)果：沒(méi)有查找到子串查找到了子串沒(méi)有查找到子串'DAC--3-shiyaDebugexeH

"D:\Cff$hiy日n\Debug^bfex&Isdjfnsonpyoi*請(qǐng)趣入壬串并且齊和回車結(jié)束您物人的主串為=wlltjfaeioraacwir:既16

請(qǐng)輸入主串并且以叫利回車?吉束isdIsdjfnsonpyoi*主串為,主串長(zhǎng)度:13找到了相同茵卓串：位置在主串的第8的位置上Presskeytocontinue^|請(qǐng)輸入子串并旦以^和回車結(jié)束|豚匍子辜為=ioraa|子§

1請(qǐng)輸入子串并且以皿和回車結(jié)束seinueB子吊為:seinue子串長(zhǎng)度；6++++++++BF^7-股有找到WEL找到了相同茵卓串：位置在主串的第8的位置上Presskeytocontinue^KMP算法程序代碼#include<iostream.h>#include<string>〃前綴函數(shù)值，用于KMP算法intGETNEXT(chart[],intb){intNEXT[10];NEXT[0]=-1;intj,k;j=0;k=-1;while(j<strlen(t)){if((k==-1)ll(t[j]==t[k])){j++;k++;NEXT[j]=k;}elsek=NEXT[k];}b=NEXT[b];returnb;}intKMP(chars[],chart[]){inta=0;intb=0;intm,n;m=strlen(s);〃主串長(zhǎng)度n=strlen(t);//子串長(zhǎng)度coutvvendl?"+++++++++KMP算法++++++++++++"<<endl;while(a<=m-n){while(s[a]==t[b]&&b!=n){a++;b++;}if(b==n){cout<<"找到了相應(yīng)的子串位置在主串："<<a-b+1<<endl;return0;}b=GETNEXT(t,b);a=a-b;if(b==-1)b++;}cout<<"沒(méi)有找到匹配的子串！"<<endl;return0;}voidmain(){cout<<"請(qǐng)輸入主串并且以0和回車結(jié)束”<<endl;chars[100];chart[100];for(intm=0;m<100;m++){cin>>s[m];if(s[m]=='0'){s[m]='\0';break;}}cout<<"您輸入的主串為：”；for(into=0;o<strlen(s);++o){cout<<s[o];}cout<<endl;cout<<"主串長(zhǎng)度：”；cout<<strlen(s);cout<<endl<<endl;cout<<"請(qǐng)輸入子串并且以0和回車結(jié)束”<<endl;for(intn=0;n<100;n++){cin>>t[n];if(t[n]=='0'){t[n]='\0';break;

}cout<<"您輸入的子串為：”for(inta=0;a<strlen(t);++a){cout<<t[a];}cout<<endl;cout<<"子串長(zhǎng)度：”；cout<<strlen(t);cout<<endl;KMP(s,t);}程序執(zhí)行結(jié)果：沒(méi)有查到子串'D:\C++shiy沒(méi)有查到子串'D:\C++shiy3rADebug\kiTip.exe""D：AC■+-shiyan^DebugXkmp.exen請(qǐng)輸入主串并且議0和回車結(jié)束門i睥邸J燦￡u。入的主葦為=Sjd-wernsfa.sjdhFt*給長(zhǎng)度Y姑［青輸入子串并且以。和回車結(jié)束S(asjdhfuE您擎A的子串?為：^sjdhfu子豐長(zhǎng)度於a*■I找到了相應(yīng)的子串位置在主串：8^pessan^ikeytc-cuntinue