求可复用子串的多字符串合并为单缓冲区的算法或C++库

你描述的问题本质是**最短超串构造（Shortest Superstring Problem）**的变体——通过最大化字符串间的重叠子串，将多个字符串合并为单个最小体积的缓冲区，同时保留原字符串的视图（string_view）。

算法背景 #

最短超串问题属于NP-hard问题，无法在多项式时间内找到全局最优解。实际场景中通常使用贪心启发式算法来获得近似最优结果：

1. 计算每对字符串的最大重叠长度（即A的后缀与B的前缀的最长匹配部分）
2. 每次选择重叠长度最大的一对字符串进行合并，生成新的字符串
3. 重复上述步骤，直到所有字符串合并为一个主缓冲区
4. 回溯记录每个原字符串在主缓冲区中的起始位置，生成对应的string_view

这种贪心策略虽然不能保证全局最优，但实现简单、效率较高，在大多数场景下能显著减少最终缓冲区的体积。

C++实现思路 #

以下是一个简化的贪心算法实现示例，可直接用于生成最小化的主缓冲区及对应的string_view集合：

#include <vector>
#include <string>
#include <string_view>
#include <algorithm>
#include <cstddef>

// 计算字符串s1后缀与s2前缀的最大重叠长度
size_t calculate_max_overlap(const std::string& s1, const std::string& s2) {
    const size_t min_len = std::min(s1.size(), s2.size());
    size_t max_overlap = 0;
    for (size_t len = 1; len <= min_len; ++len) {
        if (s1.compare(s1.size() - len, len, s2, 0, len) == 0) {
            max_overlap = len;
        }
    }
    return max_overlap;
}

std::string CompressStrings(std::vector<std::string> inputs, std::vector<std::string_view>& outputs) {
    // 保存原始字符串的引用，用于后续生成string_view
    std::vector<const std::string*> original_strs;
    original_strs.reserve(inputs.size());
    for (const auto& s : inputs) {
        original_strs.push_back(&s);
    }

    // 贪心合并字符串
    while (inputs.size() > 1) {
        size_t best_overlap = 0;
        size_t merge_from = 0, merge_to = 0;
        bool append_to_target = false;

        // 遍历所有字符串对，寻找最大重叠
        for (size_t i = 0; i < inputs.size(); ++i) {
            for (size_t j = 0; j < inputs.size(); ++j) {
                if (i == j) continue;
                // 检查i的后缀与j的前缀的重叠
                const size_t overlap = calculate_max_overlap(inputs[i], inputs[j]);
                if (overlap > best_overlap) {
                    best_overlap = overlap;
                    merge_from = i;
                    merge_to = j;
                    append_to_target = true;
                }
                // 检查j的后缀与i的前缀的重叠
                const size_t reverse_overlap = calculate_max_overlap(inputs[j], inputs[i]);
                if (reverse_overlap > best_overlap) {
                    best_overlap = reverse_overlap;
                    merge_from = j;
                    merge_to = i;
                    append_to_target = false;
                }
            }
        }

        // 执行合并
        std::string merged;
        if (append_to_target) {
            merged = inputs[merge_from] + inputs[merge_to].substr(best_overlap);
        } else {
            merged = inputs[merge_to] + inputs[merge_from].substr(best_overlap);
        }

        // 移除原字符串，添加合并后的新字符串
        inputs.erase(inputs.begin() + std::max(merge_from, merge_to));
        inputs.erase(inputs.begin() + std::min(merge_from, merge_to));
        inputs.push_back(std::move(merged));
    }

    std::string main_buffer = std::move(inputs[0]);

    // 为每个原始字符串生成对应的string_view
    outputs.reserve(original_strs.size());
    for (const auto* s : original_strs) {
        const size_t pos = main_buffer.find(*s);
        outputs.emplace_back(main_buffer.data() + pos, s->size());
    }

    return main_buffer;
}

注意事项 #

• 上述实现中，若存在重复的输入字符串，find会返回首次出现的位置，若需要区分不同实例，需调整位置查找逻辑
• 若需要更优的结果（接近全局最优），可考虑使用动态规划或分支定界算法，但时间复杂度会显著提升
• 该问题的研究确实始于20世纪60年代，属于早期组合优化与字符串算法的研究方向

内容的提问来源于stack exchange，提问作者Lukáš Kužel