基于Boyer-Moore算法的代码优化：加速匹配后循环执行

针对你遇到的超时问题，结合C++特性和文本匹配场景，以下是具体的优化方向，重点解决匹配后循环的性能瓶颈：

核心优化点 #

• 提前过滤无效行：在进入Boyer-Moore匹配前，先判断当前行长度是否小于子串长度，直接跳过这类行，避免不必要的匹配计算。
• 复用BM预处理表：将Boyer-Moore的坏字符/好后缀表移到行遍历循环外，只初始化一次。不要在每行匹配时重新生成预处理表——这是最容易被忽略的性能浪费点。
• 预计算词位映射：不要在每次匹配后再回溯统计词位，而是遍历行时同步维护词位索引：遇到单词分隔符（空格、标点等）时更新词位，用数组记录每个字符位置对应的词位，匹配时直接查表获取，避免重复遍历。
• 减少内存拷贝：用std::string_view代替std::string传递行内容，避免逐行读取时的字符串拷贝开销；如果是从文件读取，直接用内存映射（mmap）或者一次性读取全部文本到内存，减少磁盘IO次数。
• 批量IO操作：不要每次匹配都立即输出结果，先收集当前行的所有匹配词位，再一次性输出行号和所有词位。频繁的cout调用是IO性能瓶颈，可配合std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);关闭C/C++流同步进一步加速。
• 循环扁平化与编译器优化：简化匹配后处理循环的分支嵌套，避免深层条件判断；编译时开启-O3优化，让编译器自动做循环展开、指令重排、死代码消除等优化；也可以手动展开小循环（比如词位统计循环）提升缓存命中率。
• 避免冗余变量操作：行号用一个简单的递增变量维护，不要从外部结构查询；匹配结果的存储用轻量容器（比如std::vector<int>），避免用复杂数据结构带来的额外开销。

代码优化示例 #

假设你的原匹配后循环存在重复生成BM表、回溯计算词位的问题，优化后的核心代码片段如下：

#include <iostream>
#include <vector>
#include <string>
#include <cctype>

// 假设你的BoyerMoore类已实现，接收pattern初始化预处理表
class BoyerMoore {
public:
    BoyerMoore(const std::string& pattern) { /* 初始化坏字符/好后缀表 */ }
    std::vector<int> search(const std::string_view& line) { /* 匹配逻辑，返回匹配起始位置 */ }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr); // 加速IO

    std::string pattern;
    std::getline(std::cin, pattern);
    BoyerMoore bm(pattern); // 仅初始化一次BM表
    const int pattern_len = pattern.size();

    std::string line;
    int line_num = 1;
    while (std::getline(std::cin, line)) {
        if (line.size() < pattern_len) {
            line_num++;
            continue;
        }

        std::vector<int> matches = bm.search(std::string_view(line));
        if (matches.empty()) {
            line_num++;
            continue;
        }

        // 预计算每个位置的词位
        std::vector<int> pos_to_word(line.size(), 1);
        int current_word = 1;
        bool in_word = false;
        for (size_t i = 0; i < line.size(); ++i) {
            if (std::isspace(static_cast<unsigned char>(line[i])) || std::ispunct(static_cast<unsigned char>(line[i]))) {
                in_word = false;
            } else if (!in_word) {
                in_word = true;
                current_word++;
            }
            pos_to_word[i] = current_word;
        }

        // 批量输出
        std::cout << line_num;
        for (int pos : matches) {
            std::cout << " " << pos_to_word[pos];
        }
        std::cout << "\n";
        line_num++;
    }

    return 0;
}

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