那些经典算法：字符串匹配算法BM算法( 三 ) _BM算法

真实环境中，我们如何根据好后缀和坏字符的规则移动那。假设好后缀的长度是k 。我们先拿到好后缀，在suffix数组中查找其匹配的子串，如果suffix[k]不等于-1，我们就将模式串向后移动j-suffix[k] +1 位（j标识坏字符串对应的模式串中字符的下标）。

文章插图

如果suffix[k] = -1 ,标识模式串中不存在另一个跟好后缀子串片段，可以用下面规则来处理：好后缀的后缀子串b[r,m-1]（其中，r取值从j+2到m-1）的长度k = m-r，如果prefix[k]= true，标识长度为k的后缀子串，有可以匹配的前缀子串，我们可以把模式串后移r位。

文章插图

如果两条规则都没有找到可以匹配的好后缀及其后缀子串的匹配的前缀子串，将整个模式串后移m位：

文章插图

最终JAVA版本的完整代码：

// a,b 表示主串和模式串；n，m 表示主串和模式串的长度 。public int bm(char[] a, int n, char[] b, int m) {int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置generateBC(b, m, bc); // 构建坏字符哈希表int[] suffix = new int[m];boolean[] prefix = new boolean[m];generateGS(b, m, suffix, prefix);int i = 0; // j 表示主串与模式串匹配的第一个字符while (i <= n - m) {int j;for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j}if (j < 0) {return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置}int x = j - bc[(int)a[i+j]];int y = 0;if (j < m-1) { // 如果有好后缀的话y = moveByGS(j, m, suffix, prefix);}i = i + Math.max(x, y);}return -1;}// j 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {int k = m - 1 - j; // 好后缀长度if (suffix[k] != -1) return j - suffix[k] +1;for (int r = j+2; r <= m-1; ++r) {if (prefix[m-r] == true) {return r;}}return m;}

代码实例

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;}void suffixes(char *x, int m, int *suff) {int f, g, i;suff[m - 1] = m;g = m - 1;for (i = m - 2; i >= 0; --i) {if (i > g && suff[i + m - 1 - f] < i - g)suff[i] = suff[i + m - 1 - f];else {if (i < g)g = i;f = i;while (g >= 0 && x[g] == x[g + m - 1 - f])--g;suff[i] = f - g;}}} 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;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 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);/* Searching */j = 0;while (j <= n - m) {for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);if (i < 0) {OUTPUT(j);j += bmGs[0];}elsej += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);}}

三、性能分析BM算法，还需要额外的三个数组，其中bc数组的大小和字符集有关系，suffix数组和prefix数组大小和模式串大小m有关，如果我们要处理字符集很大，则bc数组对内存占用大，可以只使用好后缀规则，不使用坏字符规则。

【那些经典算法：字符串匹配算法BM算法】