一个字符串是否为另一个子串

1、文档根源为:从网络采集整理.word版本可编写.支持.判断子串算法比较一、问题描绘本文主要议论分别用LasVegas，MonteCarlo，KMP算法判断某个字符串能否是另一个字符串的子串。同时，分别统计出这三种算法的时间，以及MonteCarlo算法的犯错率，并进行相应的剖析比较。二、问题剖析对于LasVegas，及MonteCarlo的算法思想见课件。下边说明一下KMP算法思想。设有字符串x和y，其长度分别为LengthX和LengthY。看y能否为x的子串。KMP算法基本策略是：预办理模式y，获取此中与模式般配有关的子字符串关系规律，进而当发生匹配失败时，能够确立持续与x目前地点般配的y

2、的新地点，同时不要求在x中回溯。这样保证，只需遍历一次字符串x和y，即可判断出结果。此时算法耗费时间为O(LengthX+LengthY).获取最正确性能。设x=x0,xm-1,y=y0,yn-1,目前正在比较xi与yj能否相等。假如相等，则i、j各向前推进一步，持续比较。假如不等，则如图(1)所示，有两种状况需要办理：j=0,只需要持续比较xi+1与y0即可。(2)j0,设p=y0,yj-1,s是p两端般配的最大真子字符串，且s=y0,yk，则由已般配的结果，xi-k-1,xi-1=yj-k-1,yj-1=s,进而xi-k-1,xi-1=y0,yk，所以xi可与yk+1持续比较。而且，因为s

3、是p两端般配的最大真子字符串，用反证法不难证明，xi与yk+1持续比较不会遗漏模式。自然，p也是其自己两端般配的最大字符串，但p不可以作为s用，不然比较就会堕入无穷循环。ii+1(1)j=0Xsi-1iXYsjsK+1Yp(2)j0j-1j于是可获取模式的失败函数定义以下模式y=y0,yn-1的失败函数f定义以下最大k=0存在的话比如：对于-1y=abcabcacab,有不然f(j)=j0123456789yabcabcacabf-1-1-10123-101明显，失败函数f刻画了y与模式般配有关的子字符串关系规律，后边求解f(j)，于是我们会获取Find函数，见后边下边求解失败函数第一，f(0

4、)=-1.下边由f(j-1)求出f(j)PVPUY文档根源为:从网络采集整理.word版本可编写.支持.S若u=v,则f(j)=f(j-1)+1,若u=w,则f(j)=f2(j-的字符与u相等，或形式：-1f(j-1)1mm-1S(j)=f(j),f(j)=f(f(j).j-1j不然标志f1)+1,不然能够持续计算下去，直至找到某个m，使第fm(j-1)+1个地点fm(j-1)=-1且第0地点的字符仍不等于u.由此，可得失败函数f另一种假如j=0详细的fail算法见附录kf(j)=fm(j-1)+1m是使得x(f(j-1)+1)=x(j)的最小k三、各个算法流程图-1假如上述k不存在LasVe

5、gas算法开始MonteCarlo算法开始求出字符串x的指纹lpx开始求出字符串x的指纹lpxf0=-1求出字符串yj的指纹lpyji=fj-1,j=1符，m为x的长度If(x(j)!=x(i+1)和i=0)由lpyj求出lpy(j+1)求出字符串yj的指纹lpyjNKMP算法开始i=f(i)由lpyj求出lpy(j+1)NYlpx=lpyji0N利用失败函数Yfail()求出x字符串Y般配的规律，并放入数组f中。f(j)=-1i=f(i)NNx=yjlpx=lpyj结束用find函数判断x能否为y的子串YFind函数流程图Y结束开始返回地点j返回地点jNX和y均在长度范围内Y结束结束Nxj=

6、yij=0NYYi+,j+j=fj-1+1i+jx.length或NYx.length=0返回y中第一个与x般配的地点返回-1结束四、结果剖析注：运转电脑，双核均为2.27GHz,所用语言C+，测试5000对字符串,部分测试了20000对L：LasVegas所用时间，M：MonteCarlo所用时间K：KMP所用时间E：ErrorMonteCarlo犯错个数P：所用的素数Y的长度X的长度L/msM/msK/msE/个标准文档根源为:从网络采集整理.word版本可编写.支持.672127813150501487149151610114均值7.48.413.41.8错误率0.036%2%13101

7、5213161345080910721413150915113均值11.612.812.22.2错误率0.044%1.25%151123415131665010013122219191511712161均值13.813.418.42.6错误率0.052%1%7482112369771392500500847512428474112195631073均值81.274.2118.82.2错误率0.044%0.20%下边测试了20000对4414613482344843032910301000434429364194364343492443644133016均值43943934418.4错误率0.0

8、92%0.10%441433368154244783631540100042641035912405428345204304293599均值425.2435.6358.814.2错误率0.071%0.10%文档根源为:从网络采集整理.word版本可编写.支持.40749641234674393326501000413457335445147934934414753176均值435.8469.23494.4错误率0.002%0.10%21512195171822107211616631100500021522147164352142091183102221203116612均值176921161

9、703.22错误率0.01%0.02%218321591717221432232169412005000213520771806221502323159602239198317292均值21702154.81708.41.4错误率0.007%0.02%213322011936322072308190615005000219622211835422612231194512125221118985均值2184223419042.8错误率0.014%0.02%错误率剖析如上表所示：据理论计算，MonteCarlo的错误率概率不超出1/n,此中n为x的长度。结果与理论偏差不大。此外可看犯错误率与两个要

10、素亲密有关。一个是x和y长度相差量，长度相差越大，偏差就越大。另一个是所选素数的大小，素数越大，偏差就越小，素数越小，误差就越大。Y的长度X的长度L/msM/msK/ms1005000176921161703200500021702154170850050002184223419041000500023022314214115005000239323852526200050002546257827912500500025662580302730005000261626893497文档根源为:从网络采集整理.word版本可编写.支持.3500500026482809369940005000288

11、8290338714500500029762959421250005000307031364739时间比较如上表所示：固然三个算法时间复杂度均为O(m+n),此中m，n分别为x和y的长度。LasVegas比MonteCarlo运转时间少，有点奇异，LasVegas比MonteCarlo多履行了指令，时间却短些。原由可能是X和Y的长度仍是比较小的，测试的对数也不是很大致使了这样的结果。在第一个表中能够看出，随机算法时间比KMP少，可是在X和Y长度相差较大时，KMP更优。原由可能是X和Y的长度相差较大时，需要计算指纹的次数就会增添好多致使时间较长。但是相差很近时，需要计算指纹的次数也会降落，时间更

12、优。由第二张表能够看出这类差别。五、附录：#include#include#include#include#include#include#includeusingnamespacestd;boolwitness2(int,int,int,int);/找凭证数intRabin_Miller(int);/找寻大素数的进口程序intexpmod(int,int,int);/Expmod算法，求am（modp）boolMonto_Carlo(char*,char*,int,int,int);/Monte_Carlo算法，判断能否为子串boolLas_Vegas(char*,char*,int,int

13、,int);/Las_Vegas算法，判断能否为子串boolKMP(char*,char*,int,int);/KMP算法，判断是否为子串intmain()constintxl=5000;/x的长度constintyl=800;/y的长度intm;char*x=newcharxl;/y能否为x的子串char*y=newcharyl;int*p=newint10;/产生10个大小的素数数组intL=0;/统计Las_Vegas般配成功的次数intM=0;/统计Monte_Carlo般配成功的次数intK=0;/统计KMP般配成功的次数doubleLT=0.0;/统计Las_Vegas所用时间文档

14、根源为:从网络采集整理.word版本可编写.支持.doubleMT=0.0;/统计Monte_Carlo所用时间doubleKT=0.0;/统计KMP所用时间structtimebstart,stop;/统计时间构造体time_tdiff;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_

15、Miller算法判断能否为素数pi=m;i+;Sleep(500);m=rand()10|rand();/m2*xl*xlcoutm*iendl;for(intii=0;ii20000;ii+)/产生20000组字符串对for(i=0;ixl;i+)/随机给x分派01字符串xi=rand()%2+0;for(intj=0;jyl;j+)/随机给y分派01字符串yj=rand()%2+0;ftime(&start);/开始统计时间if(Las_Vegas(x,y,prand()%10,xl,yl)L+;/若成功，次数加一ftime(&stop);/结束统计时间/litm

16、litmendl;文档根源为:从网络采集整理.word版本可编写.支持.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);/开始统计

17、时间if(KMP(x,y,yl,xl)K+;/若成功，次数加一ftime(&stop);/结束统计时间diff=stop.time-start.time;KT+=diff*1000+litm;/不停累加时间coutLMKendl;/输出各个算法成功的个数，进行判断比较coutLTMTKTendl;/输出各个算法所用的时间，进行判断比较deletex;deletey;deletep;return0;/Las_Vegas算法参数为两个字符串x，y，素数n，以及x，y的长度xl，ylboolLas_Vegas(char*x,char*y,intn,intx

18、l,intyl)intp=n;intlpx=0;/x指纹intlpy=0;/y指纹intWp=1;for(inti=0;iyl;i+)/求出x的指纹,y1的指纹lpx=lpx*2+xi-0;lpy=lpy*2+yi-0;lpx%=p;lpy%=p;/coutlpxlpx*lpy文档根源为:从网络采集整理.word版本可编写.支持.lpyendl;for(i=0;iyl;i+)/求出WpWp*=2;Wp%=p;/coutWpWpendl;for(intj=1;j=xl-yl+1;j+)if(lpx=lpy)/假如指纹相等，在判断比较能否Xj和y能否相等，若都是，则说明y是x的子串for(inti

19、=0;iyl;i+)if(xj-1!=yi)returnfalse;j+;returntrue;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;/coutjnewlpxlpxendl;returnfalse;/Monte_Carlo算法参数为两个字符串x，y，素数n，以及x，y的长度xl，ylboolMonto_Carlo(char*x,char*y,intn,intxl,intyl)intp=n;intlpx=0;/x指纹intlpy=0;/y指纹i

20、ntWp=1;for(inti=0;iyl;i+)/求出x的指纹,y1的指纹lpx=lpx*2+xi-0;lpy=lpy*2+yi-0;文档根源为:从网络采集整理.word版本可编写.支持.lpx%=p;lpy%=p;/coutlpxlpx*lpylpyendl;for(i=0;iyl;i+)/求出WpWp*=2;Wp%=p;/coutWpWpendl;for(intj=1;j=xl-yl+1;j+)if(lpx=lpy)/假如指纹相等，则说明y是x的子串returntrue;else/假如不是，由lpj求出lpj+1/lpj+1=2*lpj-Wp*Xj+Xj+mlpx*=2;if(xj-1=

21、1)lpx-=Wp;if(xj+yl-1=1)lpx+=1;lpx%=p;/coutjnewlpxlpxendl;returnfalse;boolKMP(char*x,char*y,intLengthP,intLengthS)int*f=newintLengthP;/f数组寄存y中每段最大般配地点，大小为y的长度f0=-1;for(intj=1;j=0)i=fi;/假如不相等，返回到上个相等处，持续比较，直到找到相等地点，自然前提是地点i=0if(yj=yi+1)文档根源为:从网络采集整理.word版本可编写.支持.fj=i+1;/假如是相等跳出循环，就能加上1，持续下去elsefj=-1;/

22、不然就赋值为-1，此时i0j=0;/字符串y的指针，用来拿出j地点y中的字符inti=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，即不可以般配returnfalse;elsereturntrue;/般配成功求出素数的进口函数intRabin_Miller(intn)srand(