Boyer Moore搜索无法返回memcmp全部结果，求排查原因

你的Boyer-Moore实现存在致命的指针偏移错误，导致大量匹配被遗漏，和算法本身无关。

核心错误点 #

原代码中，你将文本指针设置为const unsigned char* text = startAddress + index，然后用text[j]和pattern.bytes[j]比较——这意味着你在比较文本中index位置向后的j个字节，但正确的逻辑应该是比较index位置向前的patternLength个字节（从后往前匹配的核心是对齐模式末尾与当前文本位置）。

这个错误会导致：

• 越界访问文本内存（当index + j超出endAddress时）
• 完全跳过文本前半部分的匹配区域，自然找不到原本存在的匹配

修正后的Boyer-Moore实现 #

uintptr_t BoyerMooreSearch(const Data& pattern, const unsigned char* startAddress, const unsigned char* endAddress) {
#undef max
    if (startAddress == nullptr) return 0;
    size_t patternLength = pattern.siglen;
    if (patternLength == 0 || patternLength > (size_t)(endAddress - startAddress)) return 0;

    // 构建坏字符表
    std::vector<int> badCharTable(256, -1);
    for (size_t i = 0; i < patternLength; ++i) {
        badCharTable[pattern.bytes[i]] = static_cast<int>(i);
    }

    // index是文本中当前待匹配的末尾位置的偏移量（相对于startAddress）
    size_t index = patternLength - 1;
    const size_t textLength = (size_t)(endAddress - startAddress);

    while (index < textLength) {
        // 待匹配区域的起始指针
        const unsigned char* matchStart = startAddress + (index - patternLength + 1);
        int j = static_cast<int>(patternLength - 1);

        // 从后往前逐个比较
        while (j >= 0 && matchStart[j] == pattern.bytes[j]) {
            --j;
        }

        if (j < 0) {
            // 匹配成功，返回起始地址
            return reinterpret_cast<uintptr_t>(matchStart);
        }

        // 计算坏字符偏移量
        unsigned char currentTextChar = startAddress[index];
        int badCharShift = j - badCharTable[currentTextChar];
        index += std::max(1, badCharShift);
    }

    return 0;
}

补充说明 #

1. 算法适用性：Boyer-Moore非常适合你的场景——模式长度3000属于较长模式，坏字符规则能大幅减少比较次数，比memcmp的暴力扫描效率高很多。KMP适合模式较短或有大量重复前缀的场景，你觉得KMP慢是正常的。
2. 匹配数差异的原因：原实现的指针偏移错误导致很多本该匹配的区域根本没被检查到，修正后应该能和memcmp得到一致的44次匹配结果。

内容的提问来源于stack exchange，提问作者Peter Lustig