适应Boyer-Moore实现

Question

我正在尝试修改Boyer-Moore c(++) Wikipedia implementation，以获得字符串中模式的所有匹配。实际上，Wikipedia实现返回第一个匹配项。主代码如下所示：

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单元的载体隐藏在那里；不可能的。

例如，如果你在第11个位置找到一个'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，索引大小为indexes数组，然后将偏移量old_index_size-1处的新数组传递给函数，new_num作为新大小，以及从索引old_index_size-1处的match的偏移量开始的干草堆字符串加1(而不是，正如我在以前的版本中所写的，加上针形字符串的长度；请参阅注释)。

这种方法还将报告重叠的匹配，例如在香蕉中搜索ana将找到b*ana*na并禁止*ana*。

更新

我测试了上面的内容，它似乎可以工作。我修改了维基百科的代码，添加了这两个include，以防止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;
    }