《三种模式匹配算法的比较和分析.doc》由会员分享，可在线阅读，更多相关《三种模式匹配算法的比较和分析.doc（8页珍藏版）》请在金锄头文库上搜索。
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;return 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);
