三種模式匹配算法的比較和分析

1、三種模式匹配算法作業(yè)要求：分別用KMP、MonteCarlo、LasVegs算法編制三個程序，隨機生成不小于5000對長度不等的01串（三個程序使用相同的串），然后統(tǒng)計算法的執(zhí)行時間和MonteCarlo算法的出錯比率，并根據(jù)運行結(jié)果對三種算法進行深入的比較。1、 算法思路KMP算法的主要特點是指向主串的指針不需要回溯，只向右移動，即模式串在與主串失配時，并不回溯主串的指針與模式串重新匹配，而是根據(jù)已經(jīng)得到的匹配信息將模式串盡可能遠的向右滑動一段?；瑒泳嚯x的大小取決于模式串的失效函數(shù)next, nextk（0=k2m時， Y和X(j)的對p作模運算后的“指紋”Ip都要小于p, 此時p不可能可以

2、整除|Y X(j)|，因此不會出現(xiàn)當Ip（X(j)）=Ip(y)時卻有X(j)Y的誤判情況，所以這種情況下MonteCarlo出錯率為0。3） 素數(shù)一定大時，MonteCarlo算法的出錯率比理論值1/n要小的多，即當Ip（X(j)）= Ip(y)時卻有X(j)Y的情況很少。相反，當素數(shù)很小時，不同0/1序列對素數(shù)作模運算的結(jié)果相同的可能性增大，出錯率相應(yīng)地變大。4） 當模式串的長度比主串小很多時，三個算法的執(zhí)行時間明顯快了，KMP和MonteCarlo算法的執(zhí)行時間幾乎相等。這也是比較容易理解的，模式串很短意味著它與主串匹配成功的可能性就大，算法不需要從頭到尾掃描一遍主串就可以在主串的較前面

3、找到匹配串的位置，此外，模式串的長度小則說明耗費在掃描一遍模式串的時間就短，因此執(zhí)行算法所花費的時間就少得多，KMP時間復雜度接近O(m+n)，與MonteCarlo算法相等。為了更好的說明問題，對p的大小和模式串的長度選取了幾組不同的測試數(shù)據(jù)，以下為不同數(shù)據(jù)的運行結(jié)果（其中m，n分別為主串和模式串的長度，m, n, p都是在給定的區(qū)間上隨機取值）：1）第一組：素數(shù)p2m，取，從測試結(jié)果可以看出MonteCarlo算法的出錯率達到了20%以上，這是難以接受的。p越小MonteCarlo算法的出錯率越大。2）第二組：取，此時隨機選取素數(shù)p既有可能小于也有可能大于，MonteCarlo算法的出錯率

4、只有0.03%.3）第三組：取，此時隨機選取的素數(shù)必定大于，MonteCarlo算法的出錯率降至0.4）第四組：取，KMP算法和MonteCarlo算法每次執(zhí)行的時間幾乎相等，并且MonteCarlo算法的出錯率很小,幾乎接近0。5）第五組：取，素數(shù)p取介于16位機器表示最大整型數(shù)和32位機器表示最大整型數(shù)之間，此時MonteCarlo算法的出錯率為0.07% 1/n3、算法實現(xiàn)代碼（程序中MAXSIZE=10000）/文件名：PatternMatching.cpp/功能：實現(xiàn)并比較三種模式匹配算法：KMP，MonteCarlo，LasVegas#include random.h#includ

5、e randstr.h#include defs.h#include #include #include #include #include #include #include using namespace std;/函數(shù)聲明/bool isprime(int n);/判斷n是否為素數(shù)int random_prime( int min, int max ); /隨機產(chǎn)生一個minmax-1之間的素數(shù)int KMP(char* s, char* t, int position); /KMP算法int getIP(char *x, int len, int prime); /獲取x0xlen-1

6、的指紋int MonteCarlo(char* x, char* y, int position, int prime);/MonteCarlo算法int LasVegas(char* x, char* y, int position, int prime); /LasVegas算法/函數(shù)定義/函數(shù)名：isprime/功能：測試一個整數(shù)是否為素數(shù)/輸出：若n為素數(shù)，則返回true;否則falsebool isprime(int n)for(int i = 2; i = min; i-)if(isprime(i) break;return i;/三種模式匹配算法的實現(xiàn)/I、KMP算法/函數(shù)名：K

7、MP/功能：利用KMP算法匹配模式串/輸入：主串s和模式串t/輸出：模式串在主串第pos個字符之后出現(xiàn)的位置int KMP(char* s, char* t, int pos)int i, j;int s_len = (int)strlen(s);int t_len = (int)strlen(t);/先求模式串t的nextint *next = new intt_len;i = 0; j = -1;next0 = -1;while(i t_len)if(j = -1 ) i+; j+; nexti = j ; elseif(ti = tj) i+; j+; nexti = j ; else

8、j = nextj;/再匹配模式串，求在主串中的位置i = pos - 1 ;j = 0;while(i s_len & j = t_len) return (i - t_len) + 1;else return 0;/II、MonteCarlo算法/函數(shù)名：getIP/功能：求序列x的指紋/輸入：01串x，長度len/輸出：X(i) = xixi+1.xi+len-1 mod p的指紋int getIP(char *x, int len, int p)int ip = 0;for(int k = 0 ; k = len -1; k+)ip = ( 2 * ip + xk - 0) % p;r

9、eturn ip;/函數(shù)名：MonteCarlo/功能：利用隨機算法MonteCarlo進行模式匹配/輸入：主串s和模式串t,隨機素數(shù)p/輸出：模式串在主串第pos個字符之后出現(xiàn)的位置int MonteCarlo(char* x, char* y, int pos, int p)int j = 0;int Ipx, Ipy, wp;int x_len = (int)strlen(x);int y_len = (int)strlen(y); /取指紋Ipx = getIP(x + pos - 1, y_len, p);Ipy = getIP(y, y_len, p); /計算2m mod pwp

10、 = 1;for(int i = 0; i y_len; i+)wp = (wp * 2) % p; /開始匹配模式串while( j = x_len - y_len - pos + 1)if(Ipx = Ipy) return j + 1; elseIpx = ( 2 * Ipx - wp * ( xj - 0 ) + (xj + y_len - 0) ) % p;if(Ipx = p) Ipx -= p;j+;return 0;/III、LasVegas算法/函數(shù)名：LasVegas/功能：對MonteCarlo算法的改進，當Ip(X(j)=Ip(Y)時比較X(j)與Y是否相等，若相等則返

11、回/ 子串在主串中的位置，否則繼續(xù)執(zhí)行循環(huán)。該算法總能給出正確的位置/輸入：主串s和模式串t,隨機素數(shù)p/輸出：模式串在主串第pos個字符之后出現(xiàn)的位置int LasVegas(char* x, char* y, int pos, int p)int j = 0;int Ipx, Ipy, wp;int x_len = (int)strlen(x);int y_len = (int)strlen(y); /取指紋Ipx = getIP(x + pos - 1, y_len, p);Ipy = getIP(y, y_len, p); /計算2m mod pwp = 1;for(int i = 0

12、; i y_len; i+)wp = (wp * 2) % p; /開始匹配模式串while( j = x_len - y_len -( pos - 1) )if(Ipx = Ipy & !strncmp(x + j, y, strlen(y)return j + 1;elseIpx = ( 2 * Ipx - wp * ( xj - 0 ) + (xj + y_len - 0) ) % p;if(Ipx = p) Ipx -= p;j+;return 0;/主函數(shù)/main()char *x, *y; DWORD t_start, t_end;/記錄算法開始執(zhí)行時間和結(jié)束時間int m,n;

13、int index_KMPMAXSIZE, index_MCMAXSIZE, index_LVMAXSIZE;/分別存放KMP和MonteCarlo算法返回的匹配結(jié)果，即模式串在主串中首次出現(xiàn)的位置 int primeMAXSIZE; /存放MAXSIZE個隨機產(chǎn)生的素數(shù)int minlen, maxlen; while(1)cout maxlen;cout minlen;/隨機產(chǎn)生MAXSIZE對主串和子串最長長度分別為maxlen,minlen的0/1串RandomString rs(minlen,maxlen); /素數(shù)發(fā)生器：產(chǎn)生MonteCarlo和Las Vegas算法中所需要的素

14、數(shù)for(int i = 0; i MAXSIZE; i+)x = rs.getX(i);y = rs.getY(i);n = (int)strlen(y);m = (int)strlen(y);primei = random_prime(m*m,MAXINT32);/隨機產(chǎn)生一個素數(shù)cout endl;cout 三種模式匹配算法運行時間： endl;cout - endl;/KMP算法t_start = GetTickCount();/開始時間for(int i = 0; i MAXSIZE; i+)x = rs.getX(i);y = rs.getY(i);index_KMPi = KMP

15、(x, y, 1);t_end = GetTickCount();/結(jié)束時間cout KMP ： t_end - t_start ms endl; /MonteCarlo算法int mismatch = 0 ; /失敗的次數(shù)t_start = GetTickCount();/開始執(zhí)行MonteCarlo算法for(int i = 0; i MAXSIZE; i+)x = rs.getX(i);y = rs.getY(i);index_MCi = MonteCarlo(x, y, 1, primei);t_end = GetTickCount();/MonteCarlo算法運行完畢cout MonteCarlo ： t_end - t_start ms endl; /LasVegas算法t_start = GetTickCount();/開始執(zhí)行MonteCarlo算法for(int i = 0; i MAXSIZE; i+)x = rs.getX(i);y = rs.getY(i);index_LVi = LasVegas(x, y, 1, primei);t_end = GetTickCount();/LasVegas算法運行完畢cout LasVegas ： t_end - t_