修改Boyer-Moore的實現

Question

我在嘗試修改Boyer-Moore c（++）Wikipedia implementation以獲取字符串中模式的所有匹配項。事實上，維基百科的實施返回了第一場比賽。主要的代碼如下所示：

char* boyer_moore (uint8_t *string, uint32_t stringlen, uint8_t *pat, uint32_t patlen) { 
    int i; 
    int delta1[ALPHABET_LEN]; 
    int *delta2 = malloc(patlen * sizeof(int)); 
    make_delta1(delta1, pat, patlen); 
    make_delta2(delta2, pat, patlen); 

    i = patlen-1; 
    while (i < stringlen) { 
     int j = patlen-1; 
     while (j >= 0 && (string[i] == pat[j])) { 
      --i; 
      --j; 
     } 
     if (j < 0) { 
      free(delta2); 
      return (string + i+1); 
     } 

     i += max(delta1[string[i]], delta2[j]); 
    } 
    free(delta2); 
    return NULL; 
} 

我試圖修改塊if (j < 0)後索引添加到一個數組/向量，並讓外部循環繼續下去，但它似乎沒有奏效。在測試修改後的代碼中，我仍然只獲得一個匹配。也許這個實現不是爲了返回所有的匹配而設計的，它需要不止一些快速的改變來實現。我不太瞭解算法本身，所以我不知道如何使這項工作。如果任何人都可以指出我正確的方向，我將不勝感激。

注意：函數make_delta1和make_delta2在源代碼的早期定義（查看維基百科頁面），並且max（）函數調用實際上也是一個宏，這個宏在前面的源代碼中也有定義。

Answer 1

Boyer-Moore的算法利用了這樣一個事實，即當在一個較長的字符串內搜索「HELLO WORLD」時，如果要找到匹配，在給定位置中找到的字母會限制該位置周圍的內容完全可以說是海軍戰鬥遊戲：如果你在邊界的四個單元格中發現大海，你就不需要測試剩餘的四個單元格，以防在那裏隱藏一個5格的載體;不可能有。

如果您在第十一位發現了例如'D'，它可能是HELLO WORLD的最後一個字母;但是如果你發現'Q'，'Q'不在HELLO WORLD內部的任何地方，這意味着搜索到的字符串不能在前11個字符中的任何地方，並且你可以避免在那裏完全搜索。另一方面，'L'可能意味着HELLO WORLD在那裏，從11-3位置（HELLO WORLD的第三個字母是L），11-4或11-10開始。

搜索時，使用兩個增量數組記錄這些可能性。

所以，當你找到一個模式，你應該做的，

if (j < 0) 
{ 
    // Found a pattern from position i+1 to i+1+patlen 
    // Add vector or whatever is needed; check we don't overflow it. 
    if (index_size+1 >= index_counter) 
    { 
     index[index_counter] = 0; 
     return index_size; 
    } 
    index[index_counter++] = i+1; 

    // Reinitialize j to restart search 
    j = patlen-1; 

    // Reinitialize i to start at i+1+patlen 
    i += patlen +1; // (not completely sure of that +1) 

    // Do not free delta2 
    // free(delta2); 

    // Continue loop without altering i again 
    continue; 
} 
i += max(delta1[string[i]], delta2[j]); 
} 
free(delta2); 
index[index_counter] = 0; 
return index_counter; 

這將返回索引的零結尾的名單，只要你通過像一個size_t *indexes的功能。

函數將返回0（未找到），index_size（過多匹配）或1和index_size-1之間的匹配數。

這允許例如添加額外的匹配，而不必重複已找到的（index_size-1）子字符串的整個搜索;你通過new_num增加num_indexes，realloc的indexes陣列，然後傳遞給函數的新的數組，在偏移old_index_size-1，new_num作爲新的大小，以及從開始草堆串中的所述索引old_index_size-1加一個（不匹配的偏移量，正如我在之前的修訂版中寫的，加上針串的長度;請參閱評論）。

這種方法將報告還重疊的匹配，例如搜索ANA在香蕉會發現B * ANA * NA和禁令* ANA *。

UPDATE

我測試以上，它似乎工作。我加入這兩個包括讓GCC從嘴裏嘟囔着

#include <stdio.h> 
#include <string.h> 

然後我修改了if (j < 0)修改維基百科代碼簡單地輸出它發現了

if (j < 0) { 
      printf("Found %s at offset %d: %s\n", pat, i+1, string+i+1); 
      //free(delta2); 
      // return (string + i+1); 
      i += patlen + 1; 
      j = patlen - 1; 
      continue; 
    } 

，最後我用這個

測試

int main(void) 
{ 
    char *s = "This is a string in which I am going to look for a string I will string along"; 
    char *p = "string"; 
    boyer_moore(s, strlen(s), p, strlen(p)); 
    return 0; 
} 

得到，如預期：

Found string at offset 10: string in which I am going to look for a string I will string along 
Found string at offset 51: string I will string along 
Found string at offset 65: string along 

如果字符串包含兩個重疊的序列，兩者都發現：

char *s = "This is an andean andeandean andean trouble"; 
char *p = "andean"; 

Found andean at offset 11: andean andeandean andean trouble 
Found andean at offset 18: andeandean andean trouble 
Found andean at offset 22: andean andean trouble 
Found andean at offset 29: andean trouble 

爲了避免重疊的匹配，最快的方法是不存儲的重疊。它可以在函數中完成，但它意味着重新初始化第一個增量矢量並更新字符串指針;我們還需要將第二個i索引存儲爲i2，以使保存的索引不會變得非單調。這不值得。更好：

if (j < 0) { 
     // We have found a patlen match at i+1 
     // Is it an overlap? 
     if (index && (indexes[index] + patlen < i+1)) 
     { 
      // Yes, it is. So we don't store it. 


      // We could store the last of several overlaps 
      // It's not exactly trivial, though: 
      // searching 'anana' in 'Bananananana' 
      // finds FOUR matches, and the fourth is NOT overlapped 
      // with the first. So in case of overlap, if we want to keep 
      // the LAST of the bunch, we must save info somewhere else, 
      // say last_conflicting_overlap, and check twice. 
      // Then again, the third match (which is the last to overlap 
      // with the first) would overlap with the fourth. 

      // So the "return as many non overlapping matches as possible" 
      // is actually accomplished by doing NOTHING in this branch of the IF. 
     } 
     else 
     { 
      // Not an overlap, so store it. 
      indexes[++index] = i+1; 
      if (index == max_indexes) // Too many matches already found? 
       break; // Stop searching and return found so far 
     } 
     // Adapt i and j to keep searching 
     i += patlen + 1; 
     j = patlen - 1; 
     continue; 
    }