實

驗

報

告

一

串

匹

配

問

題?班級：計算師號：姓名：一、實題目：給定一個文本在該文本中查找并定位任意給定字符串。二、實目的：(1)深刻理解并掌握蠻力法的設計思想;(2)提高應用蠻力法設計算法的技能;(3)理解這樣一個觀點:用蠻力法設計的算法一般來說,經過適度的努力后,都可以對算法的第一個版本進行一定程度的改良改進其時間性能。三、實要求：(1)實現BF算法;(2)實現BF算法的改進算法:KMP算法和BM算法(3)對上述3個算法進行時間復雜性分析,并設計實驗程序驗證分析結果。四、算描述（對算法主要部分進行偽代碼描述或畫出流程圖）BF法：基本思想：從主串S的第一個字符開始和模式T第一個字符進行比較，若相等，則繼續比較兩者的后續字符；若不相等，則從主串的第二個字符開始和模式T第一個字符進行比較，重復上述過程，若T的字符全部比較完畢，則說明本趟匹配成功；若最后一輪匹配的起始位置是n-，則主串S中剩下的字符不足夠匹配整個模式T，匹配失敗。這個算法稱為樸素的模式匹配算法，簡稱算法。KMP法：基本思想：1.在串S和串T中分別設比較的起始下標ij；2.循環直到S中所剩字符長度小于T的長度或中所有字符均比較完畢2.1如果S[i]=T[j]，則繼續比較S和T下一個字符；否則2.2將j向右滑動到next[j]位置，即j=next[j]2.3如果j=0，則將i和j分別加1，準備下一趟比較；2.4如果T中所有字符均比較完畢，則返回匹配的起始下標；否則返回；BM法：基本思想：BM算法與KMP算法的主要區別是匹配操作的方向不同。雖然算法僅把匹配操作的字符比突順序改為從右向左，但匹配發生失敗時，模式T右移的計算方法卻發生了較大的變化。

開主串S長模式T長→i

開主串S長→aNN

≦i<m

YY

N→ba

S[a]=T[YN

a1S[a]=T[b加1Ya加1b加1

Y

b=n

N→→aYb=n結

N

結

Y

b=-1

Nb1BF算法??

KMP算法

開→a→zN主串SY模式T長且Yi1j1

NY

Nj<0i+DIST(T,結BM算法五、實驗結果與結論（給出測試數據以及程序運行結果，并進行比較，得出自己的結論）?設計思想：設文本串T，模式串P。首先將T與P進行左對齊，然后進行從右向左比較，若是某趟比較不匹配時BM算法就采用兩條啟發式規則，即壞字符規則和好后

綴規則，來計算模式串向右移動的距離，直到整個匹配過程的結束。BE法：#include<stdio.h>#include<string.h>#include<conio.h>main(){chars[100];chart[100];inti,a,b,m,n;printf("*****pleaseinputastring:");scanf("%s",s);printf("pleaseinputsearchstring:");scanf("%s",t);m=strlen(s);n=strlen(t);printf("*******BF********\n");for(i=0;i<m;i++){b=0;a=i;while(s[a]==t[b]&&b!=n){a++;b++;}if(b==n){printf("success!\n");return0;

}}printf("nofound!:%s\n\n",&t);return0;}?KMP法：#include<stdio.h>#include<string.h>#include<conio.h>main(){chars[100];chart[100];inti,a,b,m,n;printf("*****pleaseinputastring:");scanf("%s",s);printf("pleaseinputsearchstring:");scanf("%s",t);m=strlen(s);n=strlen(t);printf("*******KMP********\n");for(a=0;a<=m-n;a++){b=0;while(s[a]==t[b]&&b!=n){a++;b++;}if(b==n)

{printf("success!\n");return0;}else{b=b+1;a=a-b;}if(b=-1){b++;}elsereturn0;}printf("nofound!:%s\n\n",&t);return0;}?

BM

算法：函數{

{}}voidBM(char*S,char*T){ints1,t1;s1=strlen(S);t1=strlen(T);intj,i=t1-1;while(i<s1){j=t1-1;while(j>=0&&S[i]==T[j]){i--;j--;}

if(j==-1){cout<<"該串從第&i位開始匹配："<<i+2<<endl;break;}else{time++;i=i+dist(S[i],T);}}if(i>=s1)cout<<"匹配不成功"<<endl;}voidmain(){int*next=newint;//給next指針分配空間char*S=newchar;//給S指針分配空間char*T=newchar;//給T指針分配空間cout<<"請輸入串S:";cin>>S;cout<<"請輸入串T:";cin>>T;co