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

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

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

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

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