最详细最容易理解的BM算法简介.ppt

预处理-好后缀 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; // 对bmGs数组的初始化 j = 0; for (i = m - 1; i = 0; --i) if (suff[i] == i + 1) //如果找到一个最大前缀 for (; j m - 1 - i; ++j) if (bmGs[j] == m) bmGs[j] = m - 1 - i; for (i = 0; i = m - 2; ++i) bmGs[m - 1 - suff[i]] = m - 1 - 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; // 对bmGs数组的初始化 j = 0; for (i = m - 1; i = 0; --i) if (suff[i] == i + 1) //如果找到一个最大前缀 for (; j m - 1 - i; ++j) if (bmGs[j] == m) bmGs[j] = m - 1 - i; for (i = 0; i = m - 2; ++i) bmGs[m - 1 - suff[i]] = m - 1 - i; } 算法主体 Int BM_Search(char* S ,char* T) { j = 0； while (j = strlen(S) - strlen(T)) { for (i = strlen(T) - 1; i = 0 T[i] ==S[i + j]; --i) if (i 0) match； else j += max(bmGs[i], bmBc[T[i]]-（m-1-i))； } } 算法主体 Int BM_Search(char* S ,char* T) { j = 0； while (j = strlen(S) - strlen(T)) { for (i = strlen(T) - 1; i = 0 T[i] ==S[i + j]; --i) if (i 0) match； else j += max(bmGs[i], bmBc[T[i]]-（m-1-i))； } } 总结 BM算法的关键主要在于对于两个数组的预处理。 坏字符串 与 好后缀 都是尽可能的将模式串尽可能地往右移动。 Bob Boyer和J Strother Moore设计于1977 * N,S,N都是坏字符 * 这里的position[T]= 2 ,从左往右 * * i=5 T[5]=‘b’ bmBC[T[5]] = bmBC[‘b’] = 0 shift = 0- (6) * 当然，仅仅只用倒退的坏字符算法是有时候效率很低下甚至陷入死循环的。在我提供的demo中大家可以试一试，改成只用坏字符算法，会可以发现陷入死循环 * 与kmp算法类似，bm算法也是要预处理的 * Boyer-M