抄来的BM算法思想
BM算法实际上包含两个并行的算法，坏字符算法和好后缀算法。
这两种算法的目的就是让模式串每次向右移动尽可能大的距离（j+=x，x尽可能的大）。
几个定义：
例主串和模式串如下：
主 串: mahtavaatalomaisemaomalomailuun
模式串: maisemaomaloma
好后缀：模式串中的aloma为“好后缀”。
坏字符：主串中的“t”为坏字符。
首先明确两个概念,
坏字符跳转BadSkip,好后缀移位GoodShift;(这个两个英文我觉得算比较好帮助理解的了)
BM算法就是取坏字节跳转和好后缀移位中较大的进行偏移的…
什么叫坏字符跳转呢?
先说明下,这个是一个空间换时间的简单算法.
建立一张包含所有目标字符串中字符的表,一般来说例如ASCII.
这样就有一个含有256个数据的数组了,其中特别的,数组的下标使用字符来标记的(0-255(字符的表示)).
这样是为了方便直接通过字符直接获取跳转量…特别的,当模式串中不存在此字符时,可以直接跳过剩下的所有字符的比较,Sunday算法就是基于这样的方式(但是它是匹配后面一个字符的)
上图:
~~~
一般的理解,是各个字符相对最后一个字符的位置偏移位置.
如上图中P
c的跳转对应的是c排除最后字符的b(其实可以看做0 )…从后往前数第一个c 的位置..(2)
特别的,b的跳转值应该为3而不是0.. a的跳转值为1而不是a…
公式如下:
实现代码可以自己写个了…
下面介绍 好后缀移位 GoodShift.
这个是BM算法比较难的一点,但也是核心的部分.
好后缀移位用于从后往前匹配时已经部分匹配,但最近的一次不匹配的情况下的偏移量.
类似KMP算法.但是它是从后往前匹配的.
(因为发现字符串整体是从前往后匹配,那么后面的字符必然会要取匹配,当发生前面匹配而后面不匹配的情况很多的时候,实为浪费)
设模式字符串P[len],
在i(正方向计数 用下标表示的)
位置发生了不匹配,(当然,前面步骤中都是匹配的)
那么匹配的字符串为P[i+1 ~ len ],
那么往前(从i-1开始)寻找一个等于
P[ i+1~ len ]的子串 , (如果模式串没有匹配这个子串,那其实整个匹配的部分都可以跳过去的)
(len-i-1)用来表示匹配的串长度
如果模式串中存在 一个P[ x-(len-i-1) ~ x ](x-m+i+1>0)(按照搜索方向得到的x值)
和 P[ i+1 ~ len ] 一致
那么检查P[ x-(len-i-1) ~ x ] 前面一个字符 P[x-(len-i-1)-1]
与 P[i]是否相同.(这个和KMP的改进方式是一致的原理)
如果相同,则跳过此次子串,继续往前搜寻.
如果不同,则需要的偏移为 (总长度 减去 匹配的长度)i 再减去 (前面剩余的长度)
偏移量为 len – (len - i) – (x-(len-i-1))= len – x –1;
第二种情况,如果没有找到这样一个子串,那么就用另外的一种方式:叫做 模式串前缀串中匹配串的最长后缀子串...看图好理解.
偏移量为 len – 2*x
第三种情况,当然就是第二种情况也没发生后的结果…即整个串移过匹配串的位置..
偏移量为 len
上代码:
int* MakeShift(char* pStart,int pLen)
{
//为好后缀表申请pLen个int的空间
int *shift =(int*)malloc(pLen*sizeof(int));
int *pShiftCurrent = shift +pLen - 1;//方便给好后缀表进行赋值的指标
char *pCurrent = pStart + pLen - 1;//记录好后缀表边界位置的指标
char c;
if(shift == NULL)
{
fprintf(stderr,"malloc failed!");
return 0;
}
c = *(pStart + pLen - 1);//保存模式串中最后一个字符，因为要反复用到它
*pShiftCurrent = 1;//以最后一个字符为边界时，确定移动1的距离
pCurrent--;//边界移动到倒数第二个字符（这句是我自己加上去的，因为我总觉得不加上去会有BUG，大家试试“abcdd”的情况，即末尾两位重复的情况）
while(pShiftCurrent-- != shift)//该最外层循环完成给好后缀表中每一个单元进行赋值的工作
{
char *p1 = pStart + pLen - 2, *p2,*p3;
//该do...while循环完成以当前pCurrent所指的字符为边界时，要移动的距离
do{
while(p1 >= pStart && *p1-- != c){};//该空循环，寻找与最后一个字符c匹配的字符所指向的位置
//找到了这么一个与尾字符匹配的字符.
p2 = pStart + pLen - 2; //p2 貌似指向已经匹配的子串的尾字符
p3 = p1; //p3指向找到的字符串的尾字符
//开始干活了...从后往前 连续比较...
while( (p3 >= pStart && *p3-- == *p2--) && p2 >=pCurrent){};//该空循环，判断在边界内字符匹配到了什么位置
}while(p3 >= pStart && p2 >= pCurrent);
//*pShiftCurrent
*pShiftCurrent = shift + pLen - pShiftCurrent + p2 - p3;//保存好后缀表中，以pCurrent所在字符为边界时，要移动的位置
/*
PS:在这里我要声明一句，*pShiftCurrent= （shift + pLen- pShiftCurrent） + p2 - p3;
大家看被我用括号括起来的部分，如果只需要计算字符串移动的距离，那么括号中的那部分是不需要的。
因为在字符串自左向右做匹配的时候，指标是一直向左移的，这里*pShiftCurrent保存的内容，实际是指标要移动距离，而不是字符串移动的距离。
我想SNORT是出于性能上的考虑，才这么做的。
*/
pCurrent--;//边界继续向前移动
}
return shift;
}
未完待续...
后面介绍suff[]方法,求BmGc的过程...其实它本身的发展应该 类似 KMP中 next到nextval的过程吧...纯属猜测...