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

1三种模式匹配算法作业要求：分别用KMP、MonteCarlo、LasVegs算法编制三个程序，随机生成不小于5000对长度不等的01串（三个程序使用相同的串），然后统计算法的执行时间和MonteCarlo算法的出错比率，并根据运行结果对三种算法进行深入的比较。1、算法思路KMP算法的主要特点是指向主串的指针不需要回溯，只向右移动，即模式串在与主串失配时，并不回溯主串的指针与模式串重新匹配，而是根据已经得到的匹配信息将模式串尽可能远的向右滑动一段。滑动距离的大小取决于模式串的失效函数next,next[k]（0=k=m-1）的值表示当模式串在下标为k的字符处与主串失配时应该向右移动到下标为next[k]的字符处再与主串重新匹配。算法首先要求模式串的失效函数next，然后再根据next的值进行模式匹配，在最坏情况下的时间复杂度为O（m*n），m为模式串的长度，n为主串的长度，当如果模式串中有较多相同的字符时，时间复杂度一般可达到O（m+n）。MonteCarlo随机算法主要是通过比较模式串和主串中与模式串等长的串的“指纹”来匹配的，若两者指纹相等，则可以认为在概率意义下两者是相等的，算法中要求用到一个随机产生的素数作模运算，该素数的选取直接影响了算法的准确率，算法的时间复杂度为O（m+n）。但有一定的出错率，即选取主串中比较串的指纹与模式串相等时但比较串与模式串并不相等，理论上这种情况出现的概率为1/n，只与主串的长度有关，与模式串的长度无关，但实际上只要选取素数合适出错率比1/n要小的多。LasVegas算法是对MonteCarlo算法的改进，当模式串的指纹与主串中的比较串相等时，此时并不直接返回匹配的位置，而是判断两个字符串是否真的相等，相等则返回，否则继续匹配。所以，该算法总能得到正确的位置，但算法的执行时间稍微比MonteCarlo算法要长一点（判断字符串是否相等的耗费），时间复杂度的期望值不超过O(m+n)。要完成上述三个模式匹配算法的比较，需要一个0/1串的随机发生器和一个素数发生器。程序中头文件”randstr.h”包含的RandomString类是用来产生MAXSIZE对的主串和模式串的，0/1串的长度和内容都是随机的，为了便于比较，规定主串的长度一定大于模式串的长度。”random.h”包含的Random类封装了产生随机数的函数。素数发生器首先产生MAXSIZE个随机数保存在prime数组中，供随机算法使用。本程序中随机生成了10000对0/1串作为测试数据，即MAXSIZE=10000。”defs.h”定义了所用的常量。2、算法分析和比较运行PatternMatching可以发现：1）三个算法运行的时间处于同一数量级的，其中在大多数情况下MonteCarlo的算法都要快于KMP和LasVegas算法，从理论上分析MonteCarlo算法的平均时间复杂度优于KMP算法，一般情况MonteCarlo时间复杂度为O（m+n），而KMP最好情况O（m+n），最坏为O(n*m)。LasVegs要比MonteCarlo稍微慢一点点，这是预料之中的，因为判断字符串相等耗费了额外的时间。KMP和LasVegs算法的平均时间复杂度大致相等。2）随机选取的素数大小直接影响了MonteCarlo算法的出错率。在模式串不是很长时，当素数大于某个数时我们可以发现出错率可以降到0。设模式串的最长长度为m，当随机产生的素数p2m时，Y和X(j)的对p作模运算后的“指纹”Ip都要小于p,此时p不可能可以整除|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算法的执行时间几乎相等。这也是比较容易理解的，模式串很短意味着它与主串匹配成功的可能性就大，算法不需要从头到尾扫描一遍主串就可以在主串的较前面找到匹配串的位置，此外，模式串的长度小则说明耗费在扫描一遍模式串的时间就短，因此执行算法所花费的时间就少得多，KMP时间复杂度接近O(m+n)，与MonteCarlo算法相等。2为了更好的说明问题，对p的大小和模式串的长度选取了几组不同的测试数据，以下为不同数据的运行结果（其中m，n分别为主串和模式串的长度，m,n,p都是在给定的区间上随机取值）：1）第一组：素数p2m，取]2,1[],128,[],16,1[mpmnm，从测试结果可以看出MonteCarlo算法的出错率达到了20%以上，这是难以接受的。p越小MonteCarlo算法的出错率越大。2）第二组：取]2,2[],128,[],16,1[16pmnm，此时随机选取素数p既有可能小于m2也有可能大于m2，MonteCarlo算法的出错率只有0.03%.3）第三组：取]2,2[],128,[],16,1[3216pmnm，此时随机选取的素数必定大于m2，MonteCarlo算法的出错率降至0.4）第四组：取]2,[],1024,[],8,1[162mpmnm，KMP算法和MonteCarlo算法每次执行的时间几乎相等，并且MonteCarlo算法的出错率很小,几乎接近0。35）第五组：取]2,2[],2048,[],2000,1[3216pmnm，素数p取介于16位机器表示最大整型数和32位机器表示最大整型数之间，此时MonteCarlo算法的出错率为0.07%1/n3、算法实现代码（程序中MAXSIZE=10000）//文件名：PatternMatching.cpp//功能：实现并比较三种模式匹配算法：KMP，MonteCarlo，LasVegas#includerandom.h#includerandstr.h#includedefs.h#includeiostream#includefstream#includetime.h#includewindows.h#includestdlib.h#includemath.h#includestring.husingnamespacestd;//////////////////////////函数声明///////////////////////////////////////////////////////////////////////////////boolisprime(intn);//判断n是否为素数intrandom_prime(intmin,intmax);//随机产生一个min~max-1之间的素数4intKMP(char*s,char*t,intposition);//KMP算法intgetIP(char*x,intlen,intprime);//获取x[0]…x[len-1]的指纹intMonteCarlo(char*x,char*y,intposition,intprime);//MonteCarlo算法intLasVegas(char*x,char*y,intposition,intprime);//LasVegas算法//////////////////////////函数定义////////////////////////////////////////////////////////////////////////////////函数名：isprime//功能：测试一个整数是否为素数//输出：若n为素数，则返回true;否则falseboolisprime(intn){for(inti=2;i=sqrt((double)n);i++)if(n%i==0)returnfalse;returntrue;}//函数名：random_prime//功能：随机产生一个[min,max-1]区间上的素数intrandom_prime(intmin,intmax){inti;srand((int)time(0));i=rand()%(max-min)+min;for(;i=min;i--)if(isprime(i))break;returni;}//////////////////////三种模式匹配算法的实现/////////////////////////////I、KMP算法//函数名：KMP//功能：利用KMP算法匹配模式串//输入：主串s和模式串t//输出：模式串在主串第pos个字符之后出现的位置intKMP(char*s,char*t,intpos){inti,j;ints_len=(int)strlen(s);intt_len=(int)strlen(t);//先求模式串t的nextint*next=newint[t_len];i=0;j=-1;next[0]=-1;while(it_len){5if(j==-1){i++;j++;next[i]=j;}else{if(t[i]==t[j]){i++;j++;next[i]=j;}elsej=next[j];}}//再匹配模式串，求在主串中的位置i=pos-1;j=0;while(is_len&&jt_len){if(j==-1||s[i]==t[j]){i++;j++;}//继续比较后面的字符elsej=next[j];//模式串向右移动};//deletenext;if(j=t_len)return(i-t_len)+1;elsereturn0;}//II、MonteCarlo算法//函数名：getIP//功能：求序列x的指纹//输入：01串x，长度len//输出：X(i)=x[i]x[i+1]...x[i+len-1]modp的指纹intgetIP(char*x,intlen,intp){intip=0;for(intk=0;k=len-1;k++)ip=(2*ip+x[k]-'0')%p;returnip;}//函数名：MonteCarlo//功能：利用随机算法MonteCarlo进行模式匹配//输入：主串s和模式串t,,随机素数p//输出：模式串在主串第pos个字符之后出现的位置intMonteCarlo(char*x,char*y,intpos,intp){intj=0;intIpx,Ipy,wp;intx_len=(int)strlen(x);inty_len=(int)strlen(y);//取指纹Ipx=getIP(x+pos-1,y_len,p);6Ipy=getIP(y,y_len,p);//计算2mmodpwp=1;for(inti=0;iy_len;i++)wp=(wp*2)%p;//开始匹配模式串while(j=x_len-y_len-pos+1){if(Ipx==Ipy)returnj+1;else{Ipx=(2*Ipx-wp*(x[j]-'0')+(x[j+y_len]-'0'))%p;if(Ipx0)Ipx+=p;if(Ipx=p)Ipx-=p;j++;}}return0;}//III、LasVegas算法//函数名：LasVegas//功能：对MonteCarlo算法的改进，当Ip(X(j))=Ip(Y)时比较X(j)与Y是否相等，若相等则返回//子串在主串中的位置，否则继续执行循环。该算法总能给出正确的位置//输入：主串s和模式串t,,随机素数p//输出：模式串在主串第pos个字符之后出现的位置intLasVegas(char*x,char*y,intpos,intp){intj=0;intIpx,Ipy,wp;intx_len=(int)strlen(x);inty_len=(int)strlen(y);//取指纹Ipx=get