无双: 注释
上面的算法对于模式串的匹配都是从左到右的 如果从右向左进行匹配的话 应该可以得到更大的移动量
boyer-moore算法是从右向左移动的例子
算法的介绍可以看这里
http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides03.pdf
或是相关的算法书(本文中引用了 数据结构与算法 java实现第二版的内容)
BM算法的要点:
假设模式串是P 主串是T, m=strlen(P),n=strlen(T)
1 从左向右移动模式串
2 对于模式串的匹配, 从右向左检查, 也就是P[m-1],p[m-2]...
3 当发现不匹配时, 使用好后缀和/或坏字符来决定模式串移动的距离 通常同时使用两个来加快查找速度
当发现一个不匹配时 如下:
Consider a mismatch at P[n - 5]:
T: mahtava talomaisema omalomailuun
P:maisemaomaloma
上面 m != t ,
这时 T 中的 t字符叫做坏字符
P 中的字符 "aloma" 叫做好后缀
坏字符算法:
当出现一个坏字符时, BM算法向右移动模式串, 让模式中最靠右的对应字符与坏字符相对 然后继续匹配
好后缀算法:
如果程序匹配了一个好后缀, 并且在模式中还有另外一个相同的后缀, 那把下一个后缀移动到当前后缀位置(类似KMP 只是KMP是从左向右移动)
BM算法在查找开始时 先根据 模式串中所有字符建立一个坏字符表
然后创建一张好后缀表
具体的可以看上面介绍的pdf文件
下面是代码
/* * ===================================================================================== * * Filename: bmtest.cpp * * Description: * * Version: 1.0 * Created: 03/24/06 14:25:58 China Standard Time * Revision: none * Compiler: gcc * * Author: Zhonglei Li (), Zhonglei_Li@trendmicro.com.cn * Company: Trend Micro Incorporated * * ===================================================================================== */#include <stdio.h>#include <string.h>#include <string>using namespace std;#define PatternStr "gcagagag"//"gcagagag"#define MainStr "gcatcgcagagagtatacagtacg"#define XSIZE 256#define ASIZE 256#define MAX(x,y) (x) > (y)? (x):(y)#define DUMP(x) printf ## x#define DUMP_ARRAY(next,size) do{ \ printf("next:\n\t"); \ for(int i =0;i<size;i++){ \ printf("% 2d ",next[i]); \ } \ printf("\n");}while(0)void preBmBc(char *x, int m, int bmBc[]) { int i; for (i = 0; i < ASIZE; ++i) bmBc[i] = m; for (i = 0; i < m - 1; ++i) bmBc[x[i]] = m - i - 1;}// 生成每个边界的suffix值// suff[i] = 以i为边界, 与pattern x 的后缀匹配的最大长度// 可以运行程序查看输出void suffixes(char *x, int m, int *suff) { suff[m - 1] = m; // 最后一个字符匹配的是整个T串 int f = 0; // 记录上次匹配发生时的边界 int g = m - 1; // 记录当前未匹配的位置 int i = m - 2; // 当前的边界,用来计算suff[i]的值 DUMP(("suffixes:%s:%d\n",x,m)); for (i = m - 2; i >= 0; --i) { //printf("current i %d | %d |%d %s | %s\n",i,g,f,x+i,x+g); char fmt[256]; sprintf(fmt,">>>>>>\ti:%d g:%d f:%d\n%%%ds\n%%%ds\n", i,g,f,m+2+m,m+2+i+1); DUMP((fmt,x,x)); // 如果利用上次的匹配结果 // 可以利用上次匹配结果的条件是: // 当前部分前面已经检查过( i > g ,可见上次已经检查过i对应的字符) // 上次匹配时匹配了足够的suffix 这时认为 P[i -> f] = P[g -> m-1] // 可以利用相似来对 suff[i]做判断 bool skip = i > g; if( skip ){ sprintf(fmt,"%%%ds => suff[f]\n%%%ds =>suff[%d]:%d < %d\n", m + 2 + f + 1, m + 2 + m - 1 - (f-i)+1, i + m - 1 - f,suff[i + m - 1 - f] , i - g); DUMP((fmt,x,x)); if( suff[i + m - 1 - f] < i - g ){ DUMP(("skip checking,use value[%d]\n",i + m - 1 - f)); suff[i] = suff[i + m - 1 - f]; } else skip = false; } if( !skip ){ if (i < g) g = i; // 保证从最后开始匹配 f = i; // 记录这次开始匹配的位置 const char* p1 = x+g; const char* p2 = x + g + m - 1 - f; int pos1 = g; int pos2 = g + m - 1 - f; // 从当前边界开始,向前尽可能的匹配后缀 while (g >= 0 && x[g] == x[g + m - 1 - f]) --g; suff[i] = f - g; // 记录匹配的后缀的长度 } DUMP(("val[%d]: %d\n",i,suff[i])); }}void preBmGs(char *x, int m, int bmGs[]) { int i, j, suff[XSIZE]; suffixes(x, m, suff); for (i = 0; i < m; ++i) bmGs[i] = m; j = 0; // 下面的两图图摘自数据结构 java实现第二版/** i < m-j-1（失配位置）* |* 0 | m-j-1 m-1* | | | |* ............A#########************************ | | |* | <---- Suffix Size ----><------ GS Shift ------>* | <---- SS[j] = j+1 ----><-------- m-j-1 ------->* | | | |* ***********************........................* | | |* 0 j m-1* <--<--<--<--<--<--< 自右向扫描 <--<--<--<--<--<*************************************************************************/ for (i = m - 1; i >= -1; --i) if (i == -1 || suff[i] == i + 1){ // 如果前缀与后缀相匹配,那保存偏移到bmGs // 或是已到最后,把还没有设置的bmGs设置成m // 如果值已经设置,那不需要再设置一次,保证最靠右的匹配子串优先 DUMP(("i: %d j: %d < %d suff[%d] = %d\n",i,j,m - 1 - i,i,suff[i])); for (; j < m - 1 - i; ++j) if (bmGs[j] == m){ bmGs[j] = m - 1 - i; DUMP(("bmGs[%d] = %d,m:%d\n",j,m - 1 - i,m)); } } // 上一步是为了保证每个字符都会引起移动, 并且移动是把最靠右的匹配串移支对应的串上 // 下一步会设置失配量, 失配量是对应它后面的匹配块的, // 移动量是把后面的匹配块移动到对应的后缀中/** m-SS[j]-1（失配位置）* |* 0 |m-SS[j] m-1* | || |* ....................A*********************** || |* |<--- Suffix Size ----><-- GS Shift ->* |<------- SS[j] ------><--- m-j-1 --->* || | |* .....B**********************...............* | | | |* 0 j-SS[j]+1 j m-1* >-->-->-->-->--> 自左向右扫描 --->-->-->-->*************************************************************************/ // 设置失配位置的移动量 for (i = 0; i <= m - 2; ++i){ bmGs[m - 1 - suff[i]] = m - 1 - i; DUMP(("i: %d bmgs[%d] = %d\n",i,m - 1 - suff[i],bmGs[m - 1 - suff[i]])); }}void BM(char *x, int m, char *y, int n) { int i, j, bmGs[XSIZE], bmBc[ASIZE]; /* Preprocessing */ preBmGs(x, m, bmGs); preBmBc(x, m, bmBc); DUMP_ARRAY(bmGs,m); /* Searching */ j = 0; while (j <= n - m) { for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i); if (i < 0) { printf("MATCH:%d\n",j); j += bmGs[0]; } else j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i); }}int main(){ BM(PatternStr,strlen(PatternStr),MainStr,strlen(MainStr)); printf("demo finish,press key to exit\n"); getchar(); return 0;}Trackback: http://tb.donews.net/TrackBack.aspx?PostId=790922