在博耶 - 穆爾算法，爲什麼「如果（非晶合金[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

我認爲你是對的。它沒有意義，因爲bmGs []初始化爲m，範圍爲m，直到語句 if (bmGs[j] == m) bmGs數組未被修改。並且沒有理由與bmGs[j] == m

檢查012因爲它總是等於m的範圍（m）並且兩個for循環都在有效範圍內。