三种模式匹配算法的比较和分析

1、三种模式匹配算法作业要求：分别用KMP、MonteCarlo、LasVegs算法编制三个程序，随机生成不小于5000对长度不等的01串（三个程序使用相同的串），然后统计算法的执行时间和MonteCarlo算法的出错比率，并根据运行结果对三种算法进行深入的比较。1、 算法思路KMP算法的主要特点是指向主串的指针不需要回溯，只向右移动，即模式串在与主串失配时，并不回溯主串的指针与模式串重新匹配，而是根据已经得到的匹配信息将模式串尽可能远的向右滑动一段。滑动距离的大小取决于模式串的失效函数next, nextk（0=k2m时， Y和X(j)的对p作模运算后的“指纹”Ip都要小于p, 此时p不可能可以

2、整除|Y X(j)|，因此不会出现当Ip（X(j)）=Ip(y)时却有X(j)Y的误判情况，所以这种情况下MonteCarlo出错率为0。3） 素数一定大时，MonteCarlo算法的出错率比理论值1/n要小的多，即当Ip（X(j)）= Ip(y)时却有X(j)Y的情况很少。相反，当素数很小时，不同0/1序列对素数作模运算的结果相同的可能性增大，出错率相应地变大。4） 当模式串的长度比主串小很多时，三个算法的执行时间明显快了，KMP和MonteCarlo算法的执行时间几乎相等。这也是比较容易理解的，模式串很短意味着它与主串匹配成功的可能性就大，算法不需要从头到尾扫描一遍主串就可以在主串的较前面

3、找到匹配串的位置，此外，模式串的长度小则说明耗费在扫描一遍模式串的时间就短，因此执行算法所花费的时间就少得多，KMP时间复杂度接近O(m+n)，与MonteCarlo算法相等。为了更好的说明问题，对p的大小和模式串的长度选取了几组不同的测试数据，以下为不同数据的运行结果（其中m，n分别为主串和模式串的长度，m, n, p都是在给定的区间上随机取值）：1）第一组：素数p2m，取，从测试结果可以看出MonteCarlo算法的出错率达到了20%以上，这是难以接受的。p越小MonteCarlo算法的出错率越大。2）第二组：取，此时随机选取素数p既有可能小于也有可能大于，MonteCarlo算法的出错率

4、只有0.03%.3）第三组：取，此时随机选取的素数必定大于，MonteCarlo算法的出错率降至0.4）第四组：取，KMP算法和MonteCarlo算法每次执行的时间几乎相等，并且MonteCarlo算法的出错率很小,几乎接近0。5）第五组：取，素数p取介于16位机器表示最大整型数和32位机器表示最大整型数之间，此时MonteCarlo算法的出错率为0.07% 1/n3、算法实现代码（程序中MAXSIZE=10000）/文件名：PatternMatching.cpp/功能：实现并比较三种模式匹配算法：KMP，MonteCarlo，LasVegas#include random.h#includ

5、e randstr.h#include defs.h#include #include #include #include #include #include #include using namespace std;/函数声明/bool isprime(int n);/判断n是否为素数int random_prime( int min, int max ); /随机产生一个minmax-1之间的素数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算法/函数定义/函数名：isprime/功能：测试一个整数是否为素数/输出：若n为素数，则返回true;否则falsebool isprime(int n)for(int i = 2; i = min; i-)if(isprime(i) break;return i;/三种模式匹配算法的实现/I、KMP算法/函数名：K

7、MP/功能：利用KMP算法匹配模式串/输入：主串s和模式串t/输出：模式串在主串第pos个字符之后出现的位置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算法/函数名：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;/函数名：MonteCarlo/功能：利用随机算法MonteCarlo进行模式匹配/输入：主串s和模式串t,随机素数p/输出：模式串在主串第pos个字符之后出现的位置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算法/函数名：LasVegas/功能：对MonteCarlo算法的改进，当Ip(X(j)=Ip(Y)时比较X(j)与Y是否相等，若相等则返

11、回/ 子串在主串中的位置，否则继续执行循环。该算法总能给出正确的位置/输入：主串s和模式串t,随机素数p/输出：模式串在主串第pos个字符之后出现的位置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;/主函数/main()char *x, *y; DWORD t_start, t_end;/记录算法开始执行时间和结束时间int m,n;

13、int index_KMPMAXSIZE, index_MCMAXSIZE, index_LVMAXSIZE;/分别存放KMP和MonteCarlo算法返回的匹配结果，即模式串在主串中首次出现的位置 int primeMAXSIZE; /存放MAXSIZE个随机产生的素数int minlen, maxlen; while(1)cout maxlen;cout minlen;/随机产生MAXSIZE对主串和子串最长长度分别为maxlen,minlen的0/1串RandomString rs(minlen,maxlen); /素数发生器：产生MonteCarlo和Las Vegas算法中所需要的素

14、数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);/随机产生一个素数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();/结束时间cout KMP ： t_end - t_start ms endl; /MonteCarlo算法int mismatch = 0 ; /失败的次数t_start = GetTickCount();/开始执行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();/开始执行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_