一个字符串是否为另一个子串.docx
- 文档编号:9683502
- 上传时间:2023-05-20
- 格式:DOCX
- 页数:23
- 大小:132.88KB
一个字符串是否为另一个子串.docx
《一个字符串是否为另一个子串.docx》由会员分享,可在线阅读,更多相关《一个字符串是否为另一个子串.docx(23页珍藏版)》请在冰点文库上搜索。
一个字符串是否为另一个子串
判定子串算法比较
一、问题描述
本文主要讨论分别用LasVegas,MonteCarlo,KMP算法判断某个字符串是不是另一个字符串的子串。
同时,分别统计出这三种算法的时间,以及MonteCarlo算法的出错率,并进行相应的分析比较。
二、问题分析
关于LasVegas,及MonteCarlo的算法思想见课件。
下面说明一下KMP算法思想。
设有字符串x和y,其长度分别为LengthX和LengthY。
看y是否为x的子串。
KMP算法基本策略是:
预处理模式y,获得其中与模式匹配有关的子字符串关系规律,从而当发生匹配失败时,可以确定继续与x当前位置匹配的y的新位置,同时不要求在x中回溯。
这样保证,只要遍历一次字符串x和y,即可判断出结果。
此时算法消耗时间为O(LengthX+LengthY).
得到最佳性能。
设x=
…,
y=
…,
当前正在比较
与
是否相等。
如果相等,则i、j各向前推进一步,继续比较。
如果不等,则如图
(1)所示,有两种情况需要处理:
(1)j=0,只需要继续比较
与
即可。
(2)j>0,设p=
…,
s是p两头匹配的最大真子字符串,且s=
…,
,则由已匹配的结果,
…,
=
…,
=s,从而
…,
=
…,
,因此
可与
继续比较。
而且,由于s是p两头匹配的最大真子字符串,用反证法不难证明,
与
继续比较不会遗漏模式。
当然,p也是其本身两头匹配的最大字符串,但p不能作为s用,否则比较就会陷入无限循环。
(1)
j=0
X
(2)j>0
于是可得到模式的失败函数定义如下
模式y=
…,
的失败函数f定义如下
例如:
对于y=abcabcacab,有
j0123456789
yabcabcacab
f-1-1-10123-101
显然,失败函数f刻画了y与模式匹配有关的子字符串关系规律,后面求解f(j),于是我们会得到Find函数,见后面
下面求解失败函数
首先,f(0)=-1.下面由f(j-1)求出f(j)
若u=v,则f(j)=f(j-1)+1,否则标记
(j)=f(j),
(j)=f(
.
若u=w,则f(j)=
+1,否则可以继续计算下去,直至找到某个m,使第
(j-1)+1个位置的字符与u相等,或
(j-1)=-1且第0位置的字符仍不等于u.由此,可得失败函数f另一种形式:
具体的fail算法见附录
三、各个算法流程图
①LasVegas算法
开始
②MonteCarlo算法
③KMP算法
Find函数流程图
四、结果分析
注:
运行电脑,双核均为2.27GHz,所用语言C++,测试5000对字符串,部分测试了20000对
L:
LasVegas所用时间,M:
MonteCarlo所用时间K:
KMP所用时间
E:
ErrorMonteCarlo出错个数P:
所用的素数
Y的长度
X的长度
L/ms
M/ms
K/ms
E/个
标准
50
50
6
7
21
2
7
8
13
1
14
8
7
1
4
9
15
1
6
10
11
4
均值
7.4
8.4
13.4
1.8
错误率
0.036%
2%
50
80
13
10
15
2
13
16
13
4
9
10
7
2
14
13
15
0
9
15
11
3
均值
11.6
12.8
12.2
2.2
错误率
0.044%
1.25%
50
100
15
11
23
4
15
13
16
6
13
12
22
1
9
19
15
1
17
12
16
1
均值
13.8
13.4
18.4
2.6
错误率
0.052%
1%
500
500
74
82
112
3
69
77
139
2
84
75
124
2
84
74
112
1
95
63
107
3
均值
81.2
74.2
118.8
2.2
错误率
0.044%
0.20%
下面测试了20000对
30
1000
441
461
348
23
448
430
329
10
434
429
364
19
436
434
349
24
436
441
330
16
均值
439
439
344
18.4
错误率
0.092%
0.10%
40
1000
441
433
368
15
424
478
363
15
426
410
359
12
405
428
345
20
430
429
359
9
均值
425.2
435.6
358.8
14.2
错误率
0.071%
0.10%
50
1000
407
496
412
3
467
439
332
6
413
457
335
4
451
479
349
3
441
475
317
6
均值
435.8
469.2
349
4.4
错误率
0.002%
0.10%
100
5000
2151
2195
1718
2
2107
2116
1663
1
2152
2147
1643
5
214
2091
1831
0
2221
2031
1661
2
均值
1769
2116
1703.2
2
错误率
0.01%
0.02%
200
5000
2183
2159
1717
2
2143
2232
1694
1
2135
2077
1806
2
2150
2323
1596
0
2239
1983
1729
2
均值
2170
2154.8
1708.4
1.4
错误率
0.007%
0.02%
500
5000
2133
2201
1936
3
2207
2308
1906
1
2196
2221
1835
4
2261
2231
1945
1
2125
2211
1898
5
均值
2184
2234
1904
2.8
错误率
0.014%
0.02%
1错误率分析
如上表所示:
据理论计算,MonteCarlo的错误率概率不超过1/n,其中n为x的长度。
结果与理论偏差不大。
另外可看出错误率与两个因素密切相关。
一个是x和y长度相差量,长度相差越大,误差就越大。
另一个是所选素数的大小,素数越大,误差就越小,素数越小,误差就越大。
Y的长度
X的长度
L/ms
M/ms
K/ms
100
5000
1769
2116
1703
200
5000
2170
2154
1708
500
5000
2184
2234
1904
1000
5000
2302
2314
2141
1500
5000
2393
2385
2526
2000
5000
2546
2578
2791
2500
5000
2566
2580
3027
3000
5000
2616
2689
3497
3500
5000
2648
2809
3699
4000
5000
2888
2903
3871
4500
5000
2976
2959
4212
5000
5000
3070
3136
4739
2时间比较
如上表所示:
虽然三个算法时间复杂度均为O(m+n),其中m,n分别为x和y的长度。
LasVegas比MonteCarlo运行时间少,有点奇怪,LasVegas比MonteCarlo多执行了指令,时间却短些。
原因可能是X和Y的长度还是比较小的,测试的对数也不是很大导致了这样的结果。
在第一个表中可以看出,随机算法时间比KMP少,但是在X和Y长度相差较大时,KMP更优。
原因可能是X和Y的长度相差较大时,需要计算指纹的次数就会增加很多导致时间较长。
然而相差很近时,需要计算指纹的次数也会下降,时间更优。
由第二张表可以看出这种差异。
五、附录:
#include
#include
#include
#include
#include
#include
#include
usingnamespacestd;
boolwitness2(int,int,int,int);//找证据数
intRabin_Miller(int);//寻找大素数的入口程序
intexpmod(int,int,int);//Expmod算法,求a^m(modp)
boolMonto_Carlo(char*,char*,int,int,int);//Monte_Carlo算法,判断是否为子串
boolLas_Vegas(char*,char*,int,int,int);//Las_Vegas算法,判断是否为子串
boolKMP(char*,char*,int,int);//KMP算法,判断是否为子串
intmain()
{
constintxl=5000;//x的长度
constintyl=800;//y的长度
intm;
char*x=newchar[xl];//y是否为x的子串
char*y=newchar[yl];
int*p=newint[10];//产生10个大小的素数数组
intL=0;//统计Las_Vegas匹配成功的次数
intM=0;//统计Monte_Carlo匹配成功的次数
intK=0;//统计KMP匹配成功的次数
doubleLT=0.0;//统计Las_Vegas所用时间
doubleMT=0.0;//统计Monte_Carlo所用时间
doubleKT=0.0;//统计KMP所用时间
structtimebstart,stop;//统计时间结构体
time_tdiff;
cout<<"*****"< //产生10个素数 srand((unsigned)time(NULL));//种种子 //C++最大产生的随机数为65535 if(xl<=100) m=rand()%(2*xl*xl);//小于50000 else m=rand()<<10|rand();//rand()*2^12 cout< inti=0;//计数变量看素数的产生有没有达到10个 while(i! =100) { //srand(time(&t)); if(m>5000&&m<2*xl*xl&&Rabin_Miller(m)==0)//调用Rabin_Miller算法判断是否为素数 { p[i]=m; i++; } Sleep(500); m=rand()<<10|rand();//m<2*xl*xl cout< } for(intii=0;ii<20000;ii++)//产生20000组字符串对 { for(i=0;i { x[i]=rand()%2+'0'; } for(intj=0;j { y[j]=rand()%2+'0'; } ftime(&start);//开始统计时间 if(Las_Vegas(x,y,p[rand()%10],xl,yl)) { L++;//若成功,次数加一 } ftime(&stop);//结束统计时间 //cout< diff=stop.time-start.time; LT+=diff*1000+stop.millitm-start.millitm;//不断累加时间 ftime(&start);//开始统计时间 if(Monto_Carlo(x,y,p[rand()%10],xl,yl)) { M++;//若成功,次数加一 } ftime(&stop);//结束统计时间 diff=stop.time-start.time; MT+=diff*1000+stop.millitm-start.millitm;//不断累加时间 ftime(&start);//开始统计时间 if(KMP(x,y,yl,xl)) { K++;//若成功,次数加一 } ftime(&stop);//结束统计时间 diff=stop.time-start.time; KT+=diff*1000+stop.millitm-start.millitm;//不断累加时间 } cout< cout< deletex; deletey; deletep; return0; } //Las_Vegas算法 //参数为两个字符串x,y,素数n,以及x,y的长度xl,yl boolLas_Vegas(char*x,char*y,intn,intxl,intyl) { intp=n; intlpx=0;//x指纹 intlpy=0;//y指纹 intWp=1; for(inti=0;i { lpx=lpx*2+x[i]-'0'; lpy=lpy*2+y[i]-'0'; lpx%=p; lpy%=p; } //cout<<"lpx"< for(i=0;i { Wp*=2; Wp%=p; } //cout<<"Wp"< for(intj=1;j<=xl-yl+1;j++) { if(lpx==lpy)//如果指纹相等,在判断比较是否Xj和y是否相等,若都是,则说明y是x的子串 { for(inti=0;i { if(x[j-1]! =y[i]) returnfalse; j++; } returntrue; } else//如果不是,由lpj求出lpj+1 {//lpj+1=2*lpj-Wp*Xj+Xj+m lpx*=2; if(x[j-1]=='1') lpx-=Wp; if(x[j+yl-1]=='1') lpx+=1; lpx%=p; //cout< } } returnfalse; } //Monte_Carlo算法 //参数为两个字符串x,y,素数n,以及x,y的长度xl,yl boolMonto_Carlo(char*x,char*y,intn,intxl,intyl) {intp=n; intlpx=0;//x指纹 intlpy=0;//y指纹 intWp=1; for(inti=0;i { lpx=lpx*2+x[i]-'0'; lpy=lpy*2+y[i]-'0'; lpx%=p; lpy%=p; } //cout<<"lpx"< for(i=0;i { Wp*=2; Wp%=p; } //cout<<"Wp"< 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+m lpx*=2; if(x[j-1]=='1') lpx-=Wp; if(x[j+yl-1]=='1') lpx+=1; lpx%=p; //cout< } } returnfalse; } boolKMP(char*x,char*y,intLengthP,intLengthS) { int*f=newint[LengthP];//f数组存放y中每段最大匹配位置,大小为y的长度 f[0]=-1;//初始化分f[0]=-1,此时无匹配 for(intj=1;j { inti=f[j-1]; while((y[j]! =y[i+1])&&(i>=0)) { i=f[i];//如果不相等,返回到上个相等处,继续比较,直到找到相等位置,当然前提是位置i>=0 } if(y[j]==y[i+1]) f[j]=i+1;//如果是相等跳出循环,就能加上1,继续下去 else f[j]=-1;//否则就赋值为-1,此时i<0 } j=0;//字符串y的指针,用来取出j位置y中的字符 inti=0;//字符串x的指针,用来取出i位置x中的字符 while((j { if(y[j]==x[i]) { //如果y在j处字符等于x在i处字符,i,j均向后移一位 j++; i++; } else { //如果不相等,分两种情况 if(j==0)//j=0,y字符串还没移动,x指针i向后移一位 i++; else//否则,x跳动上一个与y匹配的位置处,有失败函数求得位置,并自动向后移一位 j=f[j-1]+1; } } if((j returnfalse; else returntrue;//匹配成功 } //求出素数的入口函数 intRabin_Miller(intn) { srand(time(0)); intm=0,q=1; m=(n-1)/2; if(n%2==0)//保证n为偶数 { return-1; } while(m%2==0)//n-1=m*a^q { m/=2; q++; } for(inti=0;i<15;i++)//执行15次 { inta=rand()%(n-1)+2;//a为(0,n-1)之间的随机数 if(witness2(a,n,q,m))//若存在一个满足证据数,就说明n为素数 { //cout<<"合数"< return1; } } return0; } //判断是否为证据数 //是证据数返回false boolwitness2(inta,intn,intq,intm) { intx=expmod(a,n,m);//x=a^m(modn) if(x==1) returnfalse;//若a^m(modn)=1,则a^2m,a^4m,…,(modn)均=1 for(inti=0;i { if(x==n-1) returnfalse;//如果对于某个非负整数i有(a^m)^(2^i)(modn)=n-1,则对于所有满足i<j≤q的j,均有(a^m)^(2^j)(modn)=1 x=(x*x)%n; if(x==1) returntrue;//若n为素数,在首次遇到(a^m)^(2^i)(modn)=1(1≤i≤q)之前,必有(a^m)^(2^i)(modn)=n-1。 } returntrue; } //求出a^m(modn) intexpmod(inta,intn,intm) { inti=0; intlength=log(m)/log (2)+1;//求出m的二进制表示 int*b=newint[length]; ints=m/2;inty=m%2; while(i { b[i++]=y; y=s%2; s/=2; } b[i]=1; //c=c*c,若bk=1,c=a*c,否则,c=c; intc=1; for(intj=length-1;j>=0;j--) { c=(c*c)%n; if(b[j]==1) { c=a*c%n;//每一步都模取n } } returnc; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一个 字符串 是否 另一 个子