在Boyer-Moore算法中，为什么“if (bmGs[j] == m)”是必要的？

Question

代码如下所示：http://www-igm.univ-mlv.fr/~lecroq/string/node14.html

我的问题是在void preBmGs(char *x, int m, int bmGs[])函数中

为了更好地阅读，我粘贴了下面的函数：

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)     //--here is my question, remove it, is ok ? --
               bmGs[j] = m - 1 - i;
   for (i = 0; i <= m - 2; ++i)
      bmGs[m - 1 - suff[i]] = m - 1 - i;
}

我的理由是：j是渐进式的，所以j肯定不会后退。

我读了很多关于BM的博客，但他们的代码都包含if (bmGs[j] == m)。

Answer 1

我想你是对的。它没有任何意义，因为对于m的范围，数组被初始化为m，直到语句if (bmGs[j] == m) bmGs bmGs[]没有被修改。而且也没有理由去检查bmGs[j] == m

因为它将总是等于m的范围(m)，并且两个for循环都在有效范围内。