求Boyer-Moore-Horspool算法反向搜索示例（附正向实现代码）

我太懂你这种正向BMH跑的顺风顺水，一改成反向就各种报错的憋屈了——反向搜索的核心逻辑看着和正向类似，但细节上的差异很容易踩坑，尤其是坏字符规则的适配和搜索方向的处理。下面给你一个完整的反向BMH实现示例，同时拆解关键的差异点：

核心思路差异 #

反向BMH和正向的核心区别集中在这几点：

• 搜索方向：正向从文本start位置从左到右匹配，反向从start位置从右到左往文本开头找
• 匹配顺序：正向从模式串的开头开始对比，反向从模式串的末尾开始对比
• 步长计算：移动步长的基准从模式串开头变成了模式串末尾

反向BMH完整实现代码 #

对应你正向的FindNext，这里实现FindPrevious函数：

POSITION_T cDocument::FindPrevious(std::string needle, POSITION_T start) {
    size_t bufferSize = mBuffer.GetByteSize();
    size_t needleSize = needle.length();

    // 边界处理：空模式串或起始位置超出文本范围直接返回无效值
    if (needleSize == 0 || start >= bufferSize) {
        return -1;
    }

    // 构建坏字符表，逻辑和正向完全一致
    vector<int> badChars(256, -1);
    for (size_t i = 0; i < needleSize - 1; ++i) {
        badChars[static_cast<unsigned char>(needle[i])] = i;
    }

    // 反向搜索的起始位置：从start开始，确保模式串能完整放下
    size_t currentPos = start;
    while (currentPos >= needleSize - 1) {
        size_t needleIdx = needleSize - 1;
        // 从模式串末尾开始，逐个对比文本字符
        while (needleIdx != static_cast<size_t>(-1) && 
               mBuffer[currentPos - (needleSize - 1 - needleIdx)] == needle[needleIdx]) {
            if (needleIdx == 0) {
                // 完全匹配，返回匹配串在文本中的起始左端点
                return currentPos - needleSize + 1;
            }
            needleIdx--;
        }

        // 计算移动步长：基于不匹配字符在模式串中的位置到末尾的距离
        unsigned char mismatchChar = mBuffer[currentPos];
        int shift = needleSize - 1 - badChars[mismatchChar];
        // 确保步长至少为1，避免死循环
        if (shift <= 0) {
            shift = 1;
        }

        // 处理无符号数下溢问题，防止currentPos变成超大值
        if (currentPos < static_cast<size_t>(shift)) {
            break;
        }
        currentPos -= static_cast<size_t>(shift);
    }

    // 未找到匹配
    return -1;
}

关键细节说明 #

• 坏字符表：和正向逻辑完全相同，记录模式串中每个字符最后出现的位置（排除最后一个字符，因为它不匹配时的移动规则特殊）
• 匹配索引计算：文本中对应的字符位置是currentPos - (needleSize - 1 - needleIdx)，简单说就是从currentPos往左，对应模式串从末尾到开头的每个字符
• 步长计算：反向的步长公式是needleSize - 1 - badChars[mismatchChar]，和正向的needleSize - badChars[mismatchChar] - 1看起来类似，但基准是模式串的末尾，这点要注意
• 无符号数处理：因为size_t是无符号类型，移动时必须判断currentPos < shift，否则会出现下溢，导致循环异常
• 返回位置：返回的是匹配串在文本中的起始左端点，和正向FindNext的返回位置含义一致，方便调用方统一处理

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