一个字符串是否为另一个的子串.docx

判定子串算法比较一、问题描述本文主要讨论分别用Las Vegas，Monte Carlo，KMP算法判断某个字符串是不是另一个字符串的子串。同时，分别统计出这三种算法的时间，以及Monte Carlo算法的出错率，并进行相应的分析比较。二、问题分析关于Las Vegas，及Monte Carlo的算法思想见课件。下面说明一下KMP算法思想。设有字符串x和y，其长度分别为LengthX和LengthY。看y是否为x的子串。KMP算法基本策略是：预处理模式y，获得其中与模式匹配有关的子字符串关系规律，从而当发生匹配失败时，可以确定继续与x当前位置匹配的y的新位置，同时不要求在x中回溯。这样保证，只要遍历一次字符串x和y，即可判断出结果。此时算法消耗时间为O(LengthX+LengthY).得到最佳性能。设x=x0,xm-1 ,y=y0,yn-1,当前正在比较xi与yj是否相等。如果相等，则i、j各向前推进一步，继续比较。如果不等，则如图(1)所示，有两种情况需要处理：(1) j=0,只需要继续比较xi+1与y0即可。(2) j0,设p=y0,yj-1,s是p两头匹配的最大真子字符串，且s=y0,yk，则由已匹配的结果，Yji+1iXxi-k-1,xi-1=yj-k-1,yj-1=s,从而xi-k-1,xi-1=y0,yk，因此xi可与yk+1继续比较。而且，由于s是p两头匹配的最大真子字符串，用反证法不难证明，xi与yk+1继续比较不会遗漏模式。当然，p也是其本身两头匹配的最大字符串，但p不能作为s用，否则比较就会陷入无限循环。(1) j=0sii-1 XYK+1ssjj-1p (2) j0于是可得到模式的失败函数定义如下模式y=y0,yn-1的失败函数f定义如下最大k=0存在的话-1否则f(j)=例如：对于y=abcabcacab,有j0123456789yabcabcacabf-1-1-10123-101显然，失败函数f刻画了y与模式匹配有关的子字符串关系规律，后面求解f(j)，于是我们会得到Find函数，见后面下面求解失败函数首先，f(0)=-1.下面由f(j-1)求出f(j)UVPPYjf (j-1)j-1SS若u=v,则f(j)=f(j-1)+1,否则标记f1(j)=f(j), fm(j)=f(fm-1(j).-1如果j=0若u=w,则f(j)=f2(j-1)+1,否则可以继续计算下去，直至找到某个m，使第fm(j-1)+1个位置的字符与u相等，或fm(j-1)=-1且第0位置的字符仍不等于u.由此，可得失败函数f另一种形式：如果上述k不存在m是使得x(fkj-1+1)=x(j)的最小kf(j)=fmj-1+1-1具体的fail算法见附录三、各个算法流程图返回位置j结束Y求出字符串x的指纹lpx求出字符串yj的指纹lpyjyj为字符串y前m个字符，m为x的长度由lpyj求出lpy(j+1)NY lpx=lpyj x=yjNLas Vegas算法开始开始yj为字符串y前m个字符，m为x的长度求出字符串yj的指纹lpyj求出字符串x的指纹lpxN结束返回位置jY lpx=lpyj由lpyj求出lpy(j+1)Monte Carlo算法开始f0=-1i=fj-1,j=1If(x(j)!=x(i+1)和i=0)NYi=f(i)开始KMP算法Ni0利用失败函数fail()求出x字符串匹配的规律，并放入数组f中。Yi=f(i)f(j)=-1结束用find函数判断x是否为y的子串结束开始Find函数流程图X和y均在长度范围内NYNNj=0 xj=yiYYi+j=fj-1+1i+,j+jx.length或x.length=0NY返回y中第一个与x匹配的位置返回-1结束四、结果分析注：运行电脑，双核均为2.27GHz,所用语言C+，测试5000对字符串,部分测试了20000对L：Las Vegas所用时间，M：Monte Carlo所用时间 K：KMP所用时间E：Error Monte Carlo出错个数 P：所用的素数Y的长度X的长度L/msM/msK/msE/个标准505067212781311487149151610114均值7.48.413.41.8错误率0.036%2%508013101521316134910721413150915113均值11.612.812.22.2错误率0.044%1.25%501001511234151316613122219191511712161均值13.813.418.42.6错误率0.052%1%5005007482112369771392847512428474112195631073均值81.274.2118.82.2错误率0.044%0.20%下面测试了20000对3010004414613482344843032910434429364194364343492443644133016均值43943934418.4错误率0.092%0.10%401000441433368154244783631542641035912405428345204304293599均值425.2435.6358.814.2错误率0.071%0.10%50100040749641234674393326413457335445147934934414753176均值435.8469.23494.4错误率0.002%0.10%10050002151219517182210721161663121522147164352142091183102221203116612均值176921161703.22错误率0.01%0.02%200500021832159171722143223216941213520771806221502323159602239198317292均值21702154.81708.41.4错误率0.007%0.02%500500021332201193632207230819061219622211835422612231194512125221118985均值2184223419042.8错误率0.014%0.02% 错误率分析如上表所示：据理论计算，Monte Carlo的错误率概率不超过1/n,其中n为x的长度。结果与理论偏差不大。另外可看出错误率与两个因素密切相关。一个是x和y长度相差量，长度相差越大，误差就越大。另一个是所选素数的大小，素数越大，误差就越小，素数越小，误差就越大。Y的长度X的长度L/msM/msK/ms100500017692116170320050002170215417085005000218422341904100050002302231421411500500023932385252620005000254625782791250050002566258030273000500026162689349735005000264828093699400050002888290338714500500029762959421250005000307031364739 时间比较如上表所示： 虽然三个算法时间复杂度均为O(m+n),其中m，n分别为x和y的长度。Las Vegas比Monte Carlo运行时间少，有点奇怪，Las Vegas比Monte Carlo多执行了指令，时间却短些。原因可能是X和Y的长度还是比较小的，测试的对数也不是很大导致了这样的结果。 在第一个表中可以看出，随机算法时间比KMP少，但是在X和Y长度相差较大时，KMP更优。原因可能是X和Y的长度相差较大时，需要计算指纹的次数就会增加很多导致时间较长。然而相差很近时，需要计算指纹的次数也会下降，时间更优。由第二张表可以看出这种差异。 五、附录：#include #include #include #include #include #include #include using namespace std;bool witness2(int,int,int,int); /找证据数int Rabin_Miller(int); /寻找大素数的入口程序int expmod(int,int,int); /Expmod算法，求am（mod p）bool Monto_Carlo(char *,char *,int ,int ,int );/Monte_Carlo算法，判断是否为子串bool Las_Vegas(char *,char *,int ,int ,int ); /Las_Vegas算法，判断是否为子串bool KMP(char *,char *,int,int); /KMP算法，判断是否为子串int main()const int xl=5000;/x的长度const int yl=800;/y的长度int m;char *x=new charxl;/y是否为x的子串char *y=new charyl;int *p=new int10;/产生10个大小的素数数组int L=0; /统计Las_Vegas匹配成功的次数int M=0; /统计Monte_Carlo匹配成功的次数int K=0; /统计KMP匹配成功的次数double LT=0.0; /统计Las_Vegas所用时间double MT=0.0; /统计Monte_Carlo所用时间double KT=0.0; /统计KMP所用时间struct timeb start,stop;/统计时间结构体time_t diff;cout*endl;/产生10个素数srand(unsigned)time(NULL);/种种子/C+最大产生的随机数为65535if (xl=100)m=rand()%(2*xl*xl); /小于50000elsem=rand()10|rand();/rand()*212coutm5000&m2*xl*xl&Rabin_Miller(m)=0)/调用Rabin_Miller算法判断是否为素数pi=m;i+;Sleep(500);m=rand()10|rand();/m2*xl*xlcoutm*iendl;for (int ii=0;ii20000;ii+)/产生20000组字符串对for (i=0;ixl;i+)/随机给x分配01字符串xi=rand()%2+0;for (int j=0;jyl;j+)/随机给y分配01字符串yj=rand()%2+0;ftime(&start); /开始统计时间if (Las_Vegas(x,y,prand()%10,xl,yl)L+; /若成功，次数加一ftime(&stop); /结束统计时间/litm litmendl;diff=stop.time-start.time;LT+=diff*1000+litm;/不断累加时间ftime(&start); /开始统计时间if (Monto_Carlo(x,y,prand()%10,xl,yl)M+; /若成功，次数加一ftime(&stop); /结束统计时间diff=stop.time-start.time;MT+=diff*1000+litm;/不断累加时间ftime(&start); /开始统计时间if (KMP(x,y,yl,xl)K+; /若成功，次数加一ftime(&stop); /结束统计时间diff=stop.time-start.time;KT+=diff*1000+litm;/不断累加时间coutL M Kendl; /输出各个算法成功的个数，进行判断比较coutLT MT KTendl; /输出各个算法所用的时间，进行判断比较delete x;delete y;delete p;return 0;/Las_Vegas算法/参数为两个字符串x，y，素数n，以及x，y的长度xl，ylbool Las_Vegas(char *x,char *y,int n,int xl,int yl)int p=n;int lpx=0; /x指纹int lpy=0; /y指纹int Wp=1;for (int i=0;iyl;i+)/求出x的指纹,y1的指纹lpx=lpx*2+xi-0;lpy=lpy*2+yi-0;lpx%=p;lpy%=p;/coutlpx lpx*lpy lpyendl;for (i=0;iyl;i+) /求出WpWp*=2;Wp%=p;/coutWp Wpendl;for (int j=1;j=xl-yl+1;j+)if (lpx=lpy) /如果指纹相等，在判断比较是否Xj和y是否相等，若都是，则说明y是x的子串for (int i=0;iyl;i+)if (xj-1!=yi)return false;j+;return true;else/如果不是，由lpj求出lpj+1/lpj+1=2*lpj-Wp*Xj+Xj+mlpx*=2;if (xj-1=1)lpx-=Wp;if (xj+yl-1=1)lpx+=1;lpx%=p;/coutj new lpx lpxendl;return false;/Monte_Carlo算法/参数为两个字符串x，y，素数n，以及x，y的长度xl，ylbool Monto_Carlo(char *x,char *y,int n,int xl,int yl)int p=n;int lpx=0; /x指纹int lpy=0; /y指纹int Wp=1;for (int i=0;iyl;i+)/求出x的指纹,y1的指纹lpx=lpx*2+xi-0;lpy=lpy*2+yi-0;lpx%=p;lpy%=p;/coutlpx lpx*lpy lpyendl;for (i=0;iyl;i+) /求出WpWp*=2;Wp%=p;/coutWp Wpendl;for (int j=1;j=xl-yl+1;j+)if (lpx=lpy) /如果指纹相等，则说明y是x的子串return true;else/如果不是，由lpj求出lpj+1/lpj+1=2*lpj-Wp*Xj+Xj+mlpx*=2;if (xj-1=1)lpx-=Wp;if (xj+yl-1=1)lpx+=1;lpx%=p;/coutj new lpx lpxendl;return false;bool KMP(char *x,char *y,int LengthP,int LengthS)int *f=new intLengthP;/f数组存放y中每段最大匹配位置，大小为y的长度f0=-1;/初始化分f0=-1，此时无匹配for(int j=1;j=0)i=fi;/如果不相等，返回到上个相等处，继续比较，直到找到相等位置，当然前提是位置i=0if(yj=yi+1)fj=i+1;/如果是相等跳出循环，就能加上1，继续下去elsefj=-1;/否则就赋值为-1，此时i0j=0; /字符串y的指针，用来取出j位置y中的字符int i=0; /字符串x的指针，用来取出i位置x中的字符while(jLengthP)&(iLengthS)if(yj=xi)/如果y在j处字符等于x在i处字符，i，j均向后移一位j+;i+;else/如果不相等，分两种情况if(j=0)/j=0，y字符串还没移动，x指针i向后移一位i+;else/否则，x跳动上一个与y匹配的位置处，有失败函数求得位置，并自动向后移一位j=fj-1+1;if(jLengthP)|LengthP=0) /若x能匹配的长度j小于lengthp，或者y长度为0，即不能匹配return false;elsereturn true; /匹配成功/求出素数的入口函数int Rabin_Miller(int n)srand(time(0);int m=0,q=1;m