Boyer-Moore 经典单模式匹配算法
BM模式匹配算法-原理(图解)
由于毕业设计(入侵检测)的需要,这两天仔细研究了BM模式匹配算法,稍有心得,特此记下。
首先,先简单说明一下有关BM算法的一些基本概念。
BM算法是一种精确字符串匹配算法(区别于模糊匹配)。
BM算法采用从右向左比较 的方法,同时应用到了两种启发式规则,即坏字符规则 和好后缀规则 ,来决定向右跳跃的距离。
BM算法的基本流程: 设文本串T,模式串为P。首先将T与P进行左对齐,然后进行从右向左比较 ,如下图所示:
若是某趟比较不匹配时,BM算法就采用两条启发式规则,即坏字符规则 和好后缀规则 ,来计算模式串向右移动的距离,直到整个匹配过程的结束。
下面,来详细介绍一下坏字符规则 和好后缀规则 。
首先,诠释一下坏字符和好后缀的概念。
请看下图:
图中,第一个不匹配的字符(红色部分)为坏字符,已匹配部分(绿色)为好后缀。
1)坏字符规则(Bad Character):
在BM算法从右向左扫描的过程中,若发现某个字符x不匹配,则按如下两种情况讨论:
i. 如果字符x在模式P中没有出现,那么从字符x开始的m个文本显然不可能与P匹配成功,直接全部跳过该区域即可。
ii. 如果x在模式P中出现且出现次数>=1,则以该字符所在最右边位置进行对齐。
用数学公式表示,设Skip(x)为P右移的距离,m为模式串P的长度,max(x)为字符x在P中最右位置。
可以总结为字符x出现与否,将max(x)=0作为初值即可。
例1:
下图红色部分,发生了一次不匹配。
计算移动距离Skip(c) = m-max(c)=5 - 3 = 2,则P向右移动2位。
移动后如下图:
2)好后缀规则(Good Suffix):
若发现某个字符不匹配的同时,已有部分字符匹配成功,则按如下两种情况讨论:
i. 如果在P中位置t处已匹配部分P'在P中的某位置t'也出现,且位置t'的前一个字符与位置t的前一个字符不相同,则将P右移使t'对应t方才的所在的位置。
ii. 如果在P中任何位置已匹配部分P'都没有再出现,则找到与P'的后缀P''相同的P的最长前缀x,向右移动P,使x对应方才P''后缀所在的位置。
用数学公式表示,设Shift(j)为P右移的距离,m为模式串P的长度,j 为当前所匹配的字符位置,s为t'与t的距离(以上情况i)或者x与P''的距离(以上情况ii)。
以上过程有点抽象,所以我们继续图解。
例2:
下图中,已匹配部分cab(绿色)在P中再没出现。
再看下图,其后缀T'(蓝色)与P中前缀P'(红色)匹配,则将P'移动到T'的位置。
移动后如下图:
自此,两个规则讲解完毕。
在BM算法匹配的过程中,取SKip(x)与Shift(j)中的较大者作为跳跃的距离。
BM算法预处理时间复杂度为O(m+s),空间复杂度为O(s),s是与P, T相关的有限字符集长度,搜索阶段时间复杂度为O(m·n)。
最好情况下的时间复杂度为O(n/m),最坏情况下时间复杂度为O(m·n)。
BM模式匹配算法-实现(C语言)
下面是SNORT2.7.0中提取出的代码。
1. /*
2. 函数:int* MakeSkip(char *, int)
3. 目的:根据坏字符规则做预处理,建立一张坏字符表
4. 参数:
5. ptrn => 模式串P
6. PLen => 模式串P长度
7. 返回:
8. int* - 坏字符表
9. */
10. int* MakeSkip(char *ptrn, int pLen)
11. {
12. int i;
13. //为建立坏字符表,申请256个int的空间
14. /*PS:之所以要申请256个,是因为一个字符是8位,
15. 所以字符可能有2的8次方即256种不同情况*/
16. int *skip = (int*)malloc(256*sizeof(int));
17.
18. if(skip == NULL)
19. {
20. fprintf(stderr, "malloc failed!");
21. return 0;
22. }
23.
24. //初始化坏字符表,256个单元全部初始化为pLen
25. for(i = 0; i < 256; i++)
26. {
27. *(skip+i) = pLen;
28. }
29.
30. //给表中需要赋值的单元赋值,不在模式串中出现的字符就不用再赋值了
31. while(pLen != 0)
32. {
33. *(skip+(unsigned char)*ptrn++) = pLen--;
34. }
35.
36. return skip;
37. }
38.
39.
40. /*
41. 函数:int* MakeShift(char *, int)
42. 目的:根据好后缀规则做预处理,建立一张好后缀表
43. 参数:
44. ptrn => 模式串P
45. PLen => 模式串P长度
46. 返回:
47. int* - 好后缀表
48. */
49. int* MakeShift(char* ptrn,int pLen)
50. {
51. //为好后缀表申请pLen个int的空间
52. int *shift = (int*)malloc(pLen*sizeof(int));
53. int *sptr = shift + pLen - 1;//方便给好后缀表进行赋值的指标
54. char *pptr = ptrn + pLen - 1;//记录好后缀表边界位置的指标
55. char c;
56.
57. if(shift == NULL)
58. {
59. fprintf(stderr,"malloc failed!");
60. return 0;
61. }
62.
63. c = *(ptrn + pLen - 1);//保存模式串中最后一个字符,因为要反复用到它
64.
65. *sptr = 1;//以最后一个字符为边界时,确定移动1的距离
66.
67. pptr--;//边界移动到倒数第二个字符(这句是我自己加上去的,因为我总觉得不加上去会有BUG,大家试试“abcdd”的情况,即末尾两位重复的情况)
68.
69. while(sptr-- != shift)//该最外层循环完成给好后缀表中每一个单元进行赋值的工作
70. {
71. char *p1 = ptrn + pLen - 2, *p2,*p3;
72.
73. //该do...while循环完成以当前pptr所指的字符为边界时,要移动的距离
74. do{
75. while(p1 >= ptrn && *p1-- != c);//该空循环,寻找与最后一个字符c匹配的字符所指向的位置
76.
77. p2 = ptrn + pLen - 2;
78. p3 = p1;
79.
80. while(p3 >= ptrn && *p3-- == *p2-- && p2 >= pptr);//该空循环,判断在边界内字符匹配到了什么位置
81.
82. }while(p3 >= ptrn && p2 >= pptr);
83.
84. *sptr = shift + pLen - sptr + p2 - p3;//保存好后缀表中,以pptr所在字符为边界时,要移动的位置
85. /*
86. PS:在这里我要声明一句,*sptr = (shift + pLen - sptr) + p2 - p3;
87. 大家看被我用括号括起来的部分,如果只需要计算字符串移动的距离,那么括号中的那部分是不需要的。
88. 因为在字符串自左向右做匹配的时候,指标是一直向左移的,这里*sptr保存的内容,实际是指标要移动
89. 距离,而不是字符串移动的距离。我想SNORT是出于性能上的考虑,才这么做的。
90. */
91.
92. pptr--;//边界继续向前移动
93. }
94.
95. return shift;
96. }
97.
98.
99. /*
100. 函数:int* BMSearch(char *, int , char *, int, int *, int *)
101. 目的:判断文本串T中是否包含模式串P
102. 参数:
103. buf => 文本串T
104. blen => 文本串T长度
105. ptrn => 模式串P
106. PLen => 模式串P长度
107. skip => 坏字符表
108. shift => 好后缀表
109. 返回:
110. int - 1表示成功(文本串包含模式串),0表示失败(文本串不包含模式串)。
111. */
112. int BMSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)
113. {
114. int b_idx = plen;
115. if (plen == 0)
116. return 1;
117. while (b_idx <= blen)//计算字符串是否匹配到了尽头
118. {
119. int p_idx = plen, skip_stride, shift_stride;
120. while (buf[--b_idx] == ptrn[--p_idx])//开始匹配
121. {
122. if (b_idx < 0)
123. return 0;
124. if (p_idx == 0)
125. {
126. return 1;
127. }
128. }
129. skip_stride = skip[(unsigned char)buf[b_idx]];//根据坏字符规则计算跳跃的距离
130. shift_stride = shift[p_idx];//根据好后缀规则计算跳跃的距离
131. b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;//取大者
132. }
133. return 0;
134. }
经典单模式匹配算法:KMP、BM;经典多模式匹配算法:AC、Wu-Manber。貌似实用中,KMP跟C库strstr()效率相当,而BM能快上3x-5x。于是小女不才花了小天的功夫来研究这个BM算法。BM如何快速匹配模式?它怎么跳跃地?我今儿一定要把大家伙儿讲明白了,讲不明白您佬跟帖,我买单,包教包会。
模式,记为pat,用j作为索引; 文本,记为string(或text),用i作为索引。
Input: pat, string Algorithm: BM,在string中进行pat匹配。 Output: 匹配上则返回匹配地址,否则返回-1。 |
图1
图1是一简单示意图。左对齐pat与string,小指针(记为p)指向对齐后的右end,开始比对。如果pat[p]= string[p],那么小指针往左挪(挪到左end说明匹配上了),否则就要滑动pat进行重新对齐,重新对齐后,小指针当然也要跟着溜到末位进行重新比对。那么究竟怎么个滑法?分四个case:
1. 末位不匹配,且string[p]在pat中不存在,那么pat可以一下子右移patlen个单位。因为你一个一个右移只是徒劳,没人跟string[i]能匹配上。比如,图1中F与T不匹配,且F在pat中不存在,那么我们可以把pat右滑patlen,小指针也跟着移至末位,移动后如图2所示。
图2
2. 末位不匹配,但string[p]在pat中存在(如果有多个,那就找最靠右的那个),距离pat右端为delta1。那么右移pat使得它们对齐。比如,图2中减号与T不匹配,但减号存在于pat中,数数知道delta1=4,那就右移pat使得两个减号对上,移动后如图3所示。
图3
总结:从1、2可以得到, dealta1 = patlen, 当string[p]在patlen中不存在 = patlen – 最右边那个string[p]的位置, 当string[p]在patlen中存在
delta1()是所有字符的函数,例如pat和string对应26个字母,那么dealta1(‘a’)…dealta1(‘z’)。只需扫描一下pat,就能记录下值了。别地儿管这个叫“坏字符规则”。 |
3. 末m位都匹配上了(m
1) 图4中示例1,string中的c在pat中的最右出现居然还在小指针靠后的位置,总不至于为了让string中c跟pat中最右c匹配上就把pat往回倒滑一个位置吧,才不要那么瓜,遇到这种情况就让pat往右滑k=1个位置好了,此时小指针为了滑至最后需要滑k+m=5个位置。
2) 图4中示例2,string中c在pat中的最右出现在小指针前面,那好吧,就让此a跟彼a对齐吧。即让pat向右滑k=delta1(‘a’)-m=6-4=2个位置,此时小指针为了滑至最后需要滑k+m={dealta1(‘a’)-m}+m=dealta1(‘a’)=6个位置。
3) 图4中示例3,string中y在pat中未出现。那么将patlen向右移k=delta1(‘y’)-m=6-4=2个位置,此时小指针为了滑至最后需要滑dealta1(‘y’)=6个位置。
图4
总结:从3可以得到, pat右移位数 = 1, 当示例1 = k =delta1(‘char’)-m, 当示例2、3。. String右移位数 = k+m |
4. 照着3那么移挺对也挺好地,但某些情况下,如图7的情况,能不能让pat右移地更快呢?图7示例1,按3的分析只能将pat右滑1位,实际上我们可以放心右滑pat成示例2的样子,然后再将小指针移至末位开始匹配。
图7
下面的部分会比较绕,请读者用心看。图7示例1,末m(m=3)位即abc匹配上了,记为subpat,那么pat中出现的最右abc且不由mismatched char引导的位置,记为末subpat的“重现位置”,如”gabcfabceabceabc”重现位置应该是f引导的subpat,可以理解么?因为g引导的subpat不是最右的,倒数第2个e引导的subpat是由mismatched char引导的。
于是我们引入delta2(j)函数,j是发生mismatched的位置,我们记subpat的“重现位置”为rpr(j),那么pat应该右移k,相应地string右移k+m。如何计算k?
预处理pat,j=1…patlen,那么rpr(j)是指以j为mismatched的位置,以j+1…patlen为subpat的“重现位置”。 rpr(j) = max{k| k<=patlen && [pat(j+1) ... pat(patlen)]= [pat(k) ... pat(k+patlen-j-1)] && (k<=1 || pat(k-1) != pat(j) } rpr(patlen)=patlen。 其中对于“=”的判断,要么pat(x)=pat(j)要么pat(x)=NULL要么pat(y)=NULL。 举个例子就明白了:
下面解释rpr(j):
上图您能接受么?呵呵,$表示空元素。例如j=1时,要跟pat[j+1]…pat[patlen]匹配,那么pat[k]…p[k+patlen-j-1]最多就是如图所示,此时k+patlen-j-1=3即k+9-1-1=3,于是k= -4,k再大您可以试试,不好使了就。其它依此类推。读者可练习求一下下面这个rpr(j)。
|
OK,如何求滑动距离k呢?现在小指针指在j的位置上,“重现位置”在rpr(j),那么k=j+1-rpr(j),小指针需要挪至最后所以k+m={j+1-rpr(j)}+{patlen-j}=patlen+1-rpr(j),即有delta2(j)=patlen+1-rpr(j)。
总结:从3、4可以得到, 末m个元素已经匹配的情况,string需要右滑多少呢?计算delta1(string(i)),delta2(j),谁大取谁,就说滑的越多越好,反正都有匹配不上的理由。 |
OK,现在给出算法伪码,加油,就快结束了:
实现上,可以更快一点。看到delta0()不要惊讶,它和delta1()基本相同,除了delta0(pat(patlen))被设置为>stringlen+patlen的一个数。因为1、2两种case在匹配中遇到的频率很高,我们抽出fast部分,匹配时间的70%-80%都在走fast部分。自己举个例子把伪码过一遍,不明白地方跟帖。
别地儿都称 “坏字符规则” “好后缀规则”,嘛回事?fatdog如是写:
哈哈,好不好笑?坏字符规则就是我们的delta1(char)计算,好后缀规则就是我们的delta2(j)计算,本来就一码事儿。
//预处理 计算bmGS[]和bmBC[]表;//BM的Good Suffix、Bad Character while(text { //从当前匹配点text开始匹配关键词 for(i=m;(i>=0)&&(text[i]=pattern[i]);i--) ; if(i<0) { //匹配成功 报告一个成功的匹配; text+=bmGS[0];//选择下一个匹配入口点 } else //匹配失败,此时i指示着不匹配的位置点text[i]!=pat[i] { //使用两种启发式方法选择下一个匹配入口点 text+=Max(bmGS[i]-m+1,bmBC[i]); } } |
BM通常是sublinear的复杂度,最好O(n/m),最坏O(n)。一般会匹配string中的c*(i+patlen)个字符,其中c<1,并且patlen越大c越小,通常在longer pat下BM表现更出色。
BM算法概念
BM算法是一种精确字符串匹配算法(区别于模糊匹配)。
BM算法采用从右向左比较 的方法,同时应用到了两种启发式规 则,即坏字符规则 和好后缀规则 ,来决定向右跳跃的距离。
BM算法思想
1、三个shift函数:d1,d2,d3,函数的作用是决定当匹配不成功时窗口的 移动位数。
2、假设一个情况:已经读入了一个既是搜索窗口中的 文本的后缀,同时也是模式串后缀的字符串u,并且读入的下一个文本字符σ与模式串的下一个字符a不相等。
3、窗口安全移动是指窗口移动意味着读入新的字符, 放弃上一个窗口的前面几个字符,要保证放弃的字符确实无法参与匹配。窗口移动方向是从前向后。算法的核 心思想是对于模式串,可能至少有2个相同部分,这些部分肯定有一个在模式串的后缀,其它的部分可能在模式串的中间, 也可能在模式串的前缀,在后缀搜索时,发现了文本串和模式串的部分匹配X,此时,如果模式串除了后缀外,其它部分还含有X,则使文本串和模式中发生不匹配的读入的字符加上原来的匹配的X形成的部分有可能与模式串其它部分的X发生匹配(如果与模式串 所有的X不匹配,则说明这个窗口内不可能发生匹配),安全地向后移动窗口,放弃的部分肯定 不会发生匹配了。
1)d1:后缀u在模式串p中的另一个位置是最右出现位置是j(不包括在模式串尾的出现 ),文本串的窗口安全移动方法是将窗口移动m-j字符,使文本中的 u与模式串中最右边的u的出现位置相对齐。对模式中的每个后缀,计算它到 它的下一个出现之间的距离,即shift的d1,如果P的后缀u不在P中重复出现,则d1(u)被置为模式串长度m
2)d2:后缀u不出现在p中的任何其他位置。但u的后缀v可能是模式串p的一个前缀,需要对模式串所有的后缀计算第二个函 数d2。对于P的每个后缀u,d2(u)表示既是P的前缀,同时也是u的后缀的最长字符串v的长度.
3)d3:在搜索窗口中从后向前搜索时,在文本字符σ处不能成功匹配。保证下一次验证时文本 字符σ一定与模式串中的一个字符σ相对应(即:使上次匹配不成功的那个字符能在模式串的第二个 X部分匹配成功,在模式串中找到这个字符,该字符是X的前面一个字符),对每个字母表中的每个字符σ,d3(σ)表示σ在模式串的最右出现位置到模式串末尾的距离, 如果σ不在P中,d3为m
4、读入文本字符串u并在字符σ上不匹配时,进行如下几次比较:
1) 第一次:取 d1(u)和d3(σ)中较大值。
2)第二次:以上面的比较结果与m-d2(u)中的较小者,因为后者是最大的安全移动距离 。
5、如果抵达了窗口的起始位置,说明发现阶段一个成 功匹配,用d2计算窗口的下一次移动距离,进行继续匹配。
BM算法的基本流程图解
设文本串T,模式串为P。首先将T与P进行左对齐,然后进行从右向左比较 ,如下图所示:
若是某趟比较不匹配时,BM算法就采用两条启发式规则,即坏字符规则 和好后缀规则 ,来计算模式串向右移动的距离,直 到整个匹配过程的结束。
下面,来详细介绍一下坏字符 规则 和好后缀规则 。
首先,诠释一下坏字符和好后缀的概念。
请看下图:
图中,第一个不匹配的字符(红色部分)为坏字符,已匹配部分(绿 色)为好后缀。
1)坏字符规则 (Bad Character):
在BM算法从右向左扫描的过程中,若发现某个字符 x不匹配,则按如下两种情况讨论:
i. 如果字符x在模式P中没有出现,那么从字符x开始的m个文本显然不可能与P匹配成功,直接全部跳过该区域即可。
ii. 如果x在模式P中出现,则以该字符进行对齐。
用数学公式表示,设Skip(x)为P右移的距离,m为模式串P的长度,max(x)为字符x在P中最右位置。
例 1:
下图红色部分,发生了一次不匹配。
计算移动距离Skip(c) = 5 - 3 = 2,则P向右移动2位。
移动后如下图:
2)好后缀规则 (Good Suffix):
若发现某个字符不匹配的同时,已有部分字符匹配成功,则按如下两种情况讨论:
i. 如果在P中位置t处已匹配部分P'在P中的某位置t'也出现,且位置t'的前一个字符与位置t的前一个字符不相同,则将P右移使t'对应t方才的所在的位置。
ii. 如果在P中任何位置已匹配部分P'都没有再出现,则找到与P'的后缀P''相同的P的最长前缀x,向右移动P,使x对应方才P''后缀所在的位置。
用数学公式表示,设Shift(j)为P右移的距离,m为模式串P的长度,j 为当前所匹配的字符位置,s为t'与t的距离(以上情况i)或者x与P''的距离(以上情况ii)。
以上过程有点抽象,所以我们继续图解。
例2:
下图中,已匹配部分cab(绿色)在P中再没出现。
再看下图,其后缀T'(蓝色)与P中前缀P'(红色)匹配,则将P'移动到T'的位置。
移动后如下图:
自此,两个规则讲解完毕。
在BM算法匹配的过程中,取SKip(x)与Shift(j)中的较大者作为跳跃的距离。
BM算法预处理时间复杂度为O(m+s),空间复杂度为O(s),s是与P, T相关的有限字符集长度,搜索阶段时间复杂度为O(m·n)。
最好情况下的时 间复杂度为O(n/m),最坏情况下时间复杂度为O(m·n)。
BM模式匹配算法-实现C 语言代码
下面是SNORT中提取出的代码。
#include
using namespace std;
//#define u_char unsigned char
/* ****************************************************************
函数:int* MakeSkip(char *, int)
目的:根据坏字符规则做预处理,建立一张坏字符表
参数:
ptrn => 模式串P
PLen => 模式串P长度
返回:
int* - 坏字符表
****************************************************************/
int* makeskip(char *ptrn, int pLen)
{
int i;
//为建立坏字符表,申请256个int的空间
/*PS:要申请256个空间胡原因,是因为一个字符是8位,所以字符可能有2的8次方即256种不同情况 */
int *skip = (int*)malloc(256*sizeof(int));
if(skip == NULL)
{
fprintf(stderr, "malloc failed!");
return 0;
}
//初始化坏字符表,256个单元全部初始化为pLen
for(i = 0; i < 256; i++)
{
*(skip+i) = pLen;
}
//给表中需要赋值的单元赋值,不在模式串中出现的字符就不用再赋值了
while (pLen != 0)
{
*(skip+(unsigned char)*ptrn++) = pLen--;
}
return skip;
}
/****************************************************************
函数:int* MakeShift(char *, int)
目的:根据好后缀规则做预处理,建立一张好后缀表
参数:
ptrn => 模式串P
PLen => 模式串P长度
返回:
int* - 好后缀表
****************************************************************/
int* MakeShift(char* ptrn,int pLen)
{
//为好后缀表申请pLen个int的空间
int *shift = (int*)malloc(pLen*sizeof(int));
int *sptr = shift + pLen - 1;//方便给好后缀表进行赋值的指标
char *pptr = ptrn + pLen - 1;//记录好后缀表边界位置的指标
char c;
if(shift == NULL)
{
fprintf(stderr,"malloc failed!");
return 0;
}
c = *(ptrn + pLen - 1);//保存模式串中最后一个字符,因为要反复 用到它
*sptr = 1;//以最后一个字符为边界时,确定移动1的距离
// pptr--;//边界移动到倒数第二个字符(这句是我自己加上去的,因为我总觉得不加上去会有 BUG,大家试试"abcdd"的情况,即末尾两位重复的情况)
while (sptr-- != shift)//该最外层循环完成给好后缀表中每一个单元进行赋值 的工作
{
char *p1 = ptrn + pLen - 2, *p2,*p3;
//该do...while循环完成以当前pptr所指的字符为边界时,要移动的距离
do{
while(p1 >= ptrn && *p1-- != c);//该空循环,寻找与 最后一个字符c匹配的字符所指向的位置
p2 = ptrn + pLen - 2;
p3 = p1;
while(p3 >= ptrn && *p3-- == *p2-- && p2 >= pptr);//该空循环,判断在边界内字符匹配到了什么位置
}while(p3 >= ptrn && p2 >= pptr);
*sptr = shift + pLen - sptr + p2 - p3;//保存好后缀表中,以 pptr所在字符为边界时,要移动的位置
/*
PS:在这里我要声明一句,*sptr = (shift + pLen - sptr) + p2 - p3;
大家看被我用括号括起来的部分,如果只需要计算字符串移动的 距离,那么括号中的那部分是不需要的。
因为在字符串自左向右做匹配的时候,指标是一直向左移的,这里 *sptr保存的内容,实际是指标要移动
距离,而不是字符串移动的距离。我想SNORT是出于性能上的考虑,才这么做的。
*/
pptr--;//边界继续向前移动
}
return shift;
}
/****************************************************************
函数:int* BMSearch(char *, int , char *, int, int *, int *)
目的:判断文本串T中是否包含模式串P
参数:
buf => 文本串T
blen => 文本串T长度
ptrn => 模式串P
PLen => 模式串P长度
skip => 坏字符表
shift => 好后缀表
返回:
int - 1表示成功(文本串包含模式串),0表示失败(文本串不包含模式串)。
****************************************************************/
int BMSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)
{
int b_idx = plen;
if (plen == 0)
return 1;
while (b_idx <= blen)//计算字符串是否匹配到了尽头
{
int p_idx = plen, skip_stride, shift_stride;
while (buf[--b_idx] == ptrn[--p_idx])//开始匹配
{
if (b_idx < 0)
return 0;
if (p_idx == 0)
{
return 1;
}
}
skip_stride = skip[(unsigned char)buf[b_idx]];//根据坏字符规则计算跳 跃的距离
shift_stride = shift[p_idx];//根据好后缀规则计算跳跃的距离
b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;//取大者
}
return 0;
}
int main(int argc, char* argv[])
{
//char test[] = "\0\0\0\0\0\0\0\0\0CKAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA \0\0";
//char find[] = "CKAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\0\0";
//printf("%d",sizeof(int));
/* char test[] = "\x90\x90\x90\x90\x90\x90\xe8\xc0\xff\xff\xff/bin/sh \x90\x90\x90\x90\x90\x90\x90\x90\x90\x90";
char find[] = "\xe8\xc0\xff\xff\xff/bin/sh"; */
char test[] = "avbcatelmaddd";
char find[] = "lmaddd";
// int i;
// int toks;
int *shift;
int *skip;
shift=MakeShift(find,sizeof(find)-1);
skip=makeskip(find,sizeof(find)-1);
int ret = BMSearch(test, sizeof(test)-1, find, sizeof(find)-1, skip,shift);
printf ("test:%s\n",test);
printf ("find:%s\n",find);
printf ("Result:");
if(ret ==0)
{
printf("not found\n");
}
if (ret == 1)
{
printf("have found\n");
}
getchar();
return 0;
}
村里有50个人,每个人有一条狗,即有50只狗,这些狗中有病狗(不是传染病),每个人可以看除了自己的狗以外的所有狗,即49只狗。有病的狗一看就知道了,当有人推断出自己的狗是病狗的话则开枪打死自己的狗(当天知道),每人看后不准相互交流!第一天,没有枪响,第二天也没枪响,第三天,听见一阵枪响,请问村里有几只病狗?
这道题我花了两个小时思考,最后答案是此题无解,
看分析。
1·有人说三条:
理由:
这个据说是IBM的面试题,正解如下
1.若只有1条病狗,那么该狗的主人第一天就能发现,并毙之;
(解释:意思是说,如果有1条病狗,那么有一个人不会看到病狗,就是病狗的主人因为不能查看自己的狗,则知道自己的是病狗,简言之:“自己看到了0条,但还存在病狗,那么自己没看的也就是自己的狗,就是病狗”)
2.若只有2条病狗,设这两条狗的主人分别是A,B,第一天,A和B分别发现对方的狗是病狗,那么到第二天A和B就会明白,如果只有一条病狗,那么根据假设1第一天就会有枪声,所以自己的狗也是病的。于是第二天就会有枪响并有2条病狗;
(解释:意思是说,A知道我看到了一条,却没有按照一条的情况处理,所以我看到的少一条病狗,也就是说我自己的是病狗,,简言之:“自己看到了一条,但是如果只有一条,但实际上有一条以上,那么自己没看的也就是自己的狗,就是病狗”)
3.若有3条病狗,设其主人是A,B,C,第一天A发现B和C的狗是病的,B发现A和C的狗是病的,C发现A和B的狗是病的,如果A,B,C都认为只有2条狗是病的话,那么按照假设2,第二天就会有枪响。然而第二天没有动静,那么A,B,C就会认识到自己的狗也是病的,因此第三天会有枪响,并有3条狗病。
(解释:如果三条病狗,这三条病狗的主人会看到两条病狗,认为理应按照2的情况来处理,则第二天有人开枪杀狗,但是第二天没有人杀狗,则表示不是两条,不是一条,应该是两条以上,蛋是自己看到了两条,所以自己的那条狗是病狗。)
依此类推,第几天有枪声,就表明有几条病狗。 不知道直接根据这条写的程序算不算
分析原题:
1·每个人可以看除了自己的狗以外的所有狗,表示每个人只能看别人的49条狗,重点是别人,则不知道别人看到自己的狗是有没有病。
2·有病的狗一看就知道了,当有人推断出自己的狗是病狗的话则开枪打死自己的狗(当天知道),表示没有发现病狗就不杀狗,发现病狗就杀狗,并且自己只能杀死自己的狗。
3·每人看后不准相互交流,表示比如A看到了2条病狗,C看到了四条病狗,A不知道C看到了4条病狗。
4·第一天,没有枪响,第二天也没枪响,表示第一条没有人能判断自己的狗是不是病狗,第二天发现别人都不能判断自己的狗是不是病狗。
5·第三天,听见一阵枪响,表示第三天有人判断自己的狗是不是病狗,但是没人知道是不是所有的病狗都死了,好狗都活着。
最重点问题在于:
4和5,表示第一天都看到村子还有病狗,但是不确定自己的是不是病狗,于是都回家等着没有看到病狗的人杀死自己的狗。
第一天没有枪声,这样存如下结果:
∙ 如果所有人看到=1条病狗,那个养着病狗的人直接杀死自己的狗,毫无疑问问题解决;(否决,不符合题意)
∙ 如果所有人看到>1&&<49条病狗,第一天不能判断自己的狗有没有病,都不能确定自己的狗是否有病,于是第一天不杀自己的狗;(第一天没有枪声正常)
∙ 如果所有人看到=49条病狗,都不能确定自己的狗是否有病,于是第一天不杀自己的狗。(第一天没有枪声正常)
当第二天过后,依然没有枪声,这样存如下结果:
不管看到多少病狗,他们都能知道第一天没有任何人判断出那条狗是病狗,所以所有人都看到了病狗,就是在两只以上。