串匹配BM算法、KMP算法、BF算法

1、實驗報告一 串匹配問題班級： _計算機(jī)師 _ 學(xué) 號： 2 姓 名： _一、實驗題目 ：給定一個文本 , 在該文本中查找并定位任意給定字符串。二、實驗?zāi)康模?1) 深刻理解并掌握蠻力法的設(shè)計思想 ;(2) 提高應(yīng)用蠻力法設(shè)計算法的技能 ;(3) 理解這樣一個觀點(diǎn) : 用蠻力法設(shè)計的算法 , 一般來說 , 經(jīng)過適度的努力后 , 都可以對算法的第一個版本進(jìn)行一定程度的改良 , 改進(jìn)其時間性能。三、實驗要求：(1) 實現(xiàn) BF 算法 ;(2) 實現(xiàn) BF 算法的改進(jìn)算法 : KMP 算法和 BM 算法 ;(3) 對上述 3 個算法進(jìn)行時間復(fù)雜性分析 , 并設(shè)計實驗程序驗證分析結(jié)果。四、算法描述 (對

2、算法主要部分進(jìn)行偽代碼描述或畫出流程圖) BF算法：基本思想：從主串 S的第一個字符開始和模式 T 的第一個字符進(jìn)行比較，若相等， 則繼續(xù)比較兩者的后續(xù)字符；若不相等，則從主串 S的第二個字符開始和模式 T 的第一 個字符進(jìn)行比較，重復(fù)上述過程，若 T 中的字符全部比較完畢，則說明本趟匹配成功； 若最后一輪匹配的起始位置是 n- m，則主串 S 中剩下的字符不足夠匹配整個模式 T，匹 配失敗。這個算法稱為樸素的模式匹配算法，簡稱 BF 算法。KMP算法： 基本思想：1. 在串 S和串 T中分別設(shè)比較的起始下標(biāo) i 和 j ；2. 循環(huán)直到 S中所剩字符長度小于 T的長度或 T 中所有字符均比較

3、完畢 如果 Si=Tj ，則繼續(xù)比較 S和 T的下一個字符；否則 將 j 向右滑動到 nextj 位置，即 j=nextj ； 如果 j=0 ，則將 i 和j 分別加 1，準(zhǔn)備下一趟比較； 如果 T 中所有字符均比較完畢，則返回匹配的起始下標(biāo)；否則返回0；BM算法：基本思想： BM算法與 KMP算法的主要區(qū)別是匹配操作的方向不同。雖然 BM算法僅把匹配操作的字符比突順序改為從右向左，但匹配發(fā)生失敗時，模式 T 右移的計算方法 卻發(fā)生了較大的變化。BF算法KMP算法五、實驗結(jié)果與結(jié)論： （給出測試數(shù)據(jù)以及程序運(yùn)行結(jié)果，并進(jìn)行比較，得出自己的結(jié)論）設(shè)計思想：設(shè)文本串 T，模式串為 P。首先將 T

4、與 P進(jìn)行左對齊，然后進(jìn)行從右向 左比較，若是某趟比較不匹配時， BM算法就采用兩條啟發(fā)式規(guī)則，即壞字符規(guī)則和好后 綴規(guī)則，來計算模式串向右移動的距離，直到整個匹配過程的結(jié)束。BE算法：#include <>#include <>#include <>main()char s100;char t100;int i,a,b,m,n;printf("*please input a string:"); scanf("%s",s);printf("please input search string:")

5、; scanf("%s",t);m=strlen(s); n=strlen(t);printf( "*for(i=0;i<m;i+)b=0;a=i;while(sa=tb&&b!=n)a+; b+;if(b=n)printf("success!n"); return 0;printf("no found!:%snn",&t); return 0;KMP算法：#include <>#include <>#include <> main()char s100;ch

6、ar t100;int i,a,b,m,n; printf("*please input a string:"); scanf("%s",s);printf("please input search string:");scanf("%s",t);m=strlen(s); n=strlen(t);printf("*KMP*n");for(a=0;a<=m-n;a+)b=0;while(sa=tb&&b!=n)a+;b+;if(b=n)printf("success

7、!n");return 0;elseb=b+1;a=a-b; if(b=-1) b+; else return 0;printf("no found!:%snn",&t); return 0;BM算法：#include <iostream> using namespace std;#include <>#include <> static int time=0;/dist 函數(shù)int dist(char ch,char *T)int k=-1,t1; t1=strlen(T);for(int i=0;i<t1-1;

8、i+)if(ch=Ti&&i<t1)k=i+1;if(ch=Ti&&i=t1-1) k=0; if(k=-1)k=0;returnt1-k;void BM(char *S,char *T)int s1,t1;s1=strlen(S);t1=strlen(T);int j,i=t1-1;while(i<s1)j=t1-1;while(j>=0&&Si=Tj)j-;if(j=-1)cout<<" 該串從第 &i 位開始匹配： "<<i+2<<endl;break;els

9、etime+;i=i+dist(Si,T);if(i>=s1)cout<<" 匹配不成功 "<<endl;void main() cout<<" 請輸入串 S:"int *next=new int;/給 next 指針分配空間char *S=new char;/給 S 指針分配空間char *T=new char;/給 T 指針分配空間cin>>S;cout<<" 請輸入串 T:"cin>>T;cout<<"BM 算法: "BM(S,T);cout&l