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

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

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

3、 將j向右滑動(dòng)到nextj位置，即j=nextj；2.3 如果j=0，則將i和j分別加1，準(zhǔn)備下一趟比較；2.4 如果T中所有字符均比較完畢，則返回匹配的起始下標(biāo)；否則返回0；BM算法：基本思想：BM算法與KMP算法的主要區(qū)別是匹配操作的方向不同。雖然BM算法僅把匹配操作的字符比突順序改為從右向左，但匹配發(fā)生失敗時(shí)，模式T右移的計(jì)算方法卻發(fā)生了較大的變化。  開始主串S長(zhǎng)度m模式T長(zhǎng)度n0ii<m0biaSa=Tb且bna加1b加1b=nYNYYYNNNBF算法結(jié)束開始主串S長(zhǎng)度m模式T長(zhǎng)度n0a0baM-NM-Nm-nSa=Tb且bna加1b加1b=nYYYNNNK

4、MP算法結(jié)束nextbba-bab=-1b加1 開始i主串S長(zhǎng)度-1模式T長(zhǎng)度-1jj0且Si=Tji減1j減1j<0YYYNNNBM算法結(jié)束0a0b0z模式T長(zhǎng)度-1ii+DIST(T,Si)i   五、實(shí)驗(yàn)結(jié)果與結(jié)論：（給出測(cè)試數(shù)據(jù)以及程序運(yùn)行結(jié)果，并進(jìn)行比較，得出自己的結(jié)論） 設(shè)計(jì)思想：設(shè)文本串T，模式串為P。首先將T與P進(jìn)行左對(duì)齊，然后進(jìn)行從右向左比較，若是某趟比較不匹配時(shí)，BM算法就采用兩條啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則，來計(jì)算模式串向右移動(dòng)的距離，直到整個(gè)匹配過程的結(jié)束。  BE算法：#include

5、 <stdio.h>#include <string.h>#include <conio.h>main()char s100;char 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("*BF*n");for(i

6、=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 <stdio.h>#include <string.h>#include <conio.h>main()char s100;char t100;int i,a,b,m,n;printf("*please in

7、put 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!n");return 0;elseb=b+1;a=a-b;if(b=-1)b+;el

8、se return 0; printf("no found!:%snn",&t); return 0; BM算法：#include <iostream>using namespace std;#include <stdio.h>#include <string.h>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;i+) if(ch=Ti&&i<t1)

9、k=i+1;if(ch=Ti&&i=t1-1) k=0; if(k=-1) k=0; return t1-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) i-; j-; if(j=-1) cout<<"該串從第&i位開始匹配："<<i+2<<endl; break; else time+; i=i+d

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