我知道这是 bike shedding 但有没有办法在两个(排序的)字符串集 A、B 之间获取字符串集 C，其中 B 是 A 的子字符串，其复杂性优于 A.size * B.size * comp_substr，作为我想出的天真的解决方案？

    std::copy_if(devices.cbegin(), devices.cend(),
                          std::back_inserter(ports),
                          [&comport_keys] (const auto& v) {
        return std::any_of(comport_keys.begin(),comport_keys.end(), [&v](auto& k) {
           return v.find(k) != std::string::npos;
        });
    });

更简单的情况是 B 是 A 的字符串，使用 std::set_intersection 会非常简单，复杂度为 (A.size + B.size) * comp_substr ，如果必须在 (n * log(n)) 之前对其进行排序会更好，但我不知道如何为它编写比较函数，或者更确切地说两者兼而有之。

    #define BOOST_TEST_MODULE My Test

    #include <boost/test/included/unit_test.hpp>

    #include <vector>
    #include <string>
    #include <algorithm>
    #include <iterator>
    #include <set>

    BOOST_AUTO_TEST_CASE(TEST) {
        std::vector<std::string> devices{
                "tty1",
                "ttyOfk",
                "ttyS05",
                "bsd",
        }, ports{};

        const std::set<std::string> comport_keys{
                "ttyS",
                "ttyO",
                "ttyUSB",
                "ttyACM",
                "ttyGS",
                "ttyMI",
                "ttymxc",
                "ttyAMA",
                "ttyTHS",
                "ircomm",
                "rfcomm",
                "tnt",
                "cu",
                "ser",
        };

        std::sort(devices.begin(), devices.end());
        std::set_intersection(devices.cbegin(), devices.cend(),
                              comport_keys.cbegin(), comport_keys.cend(),
                              std::back_inserter(ports),
                              [&comport_keys] (auto a, auto b) {
            return a.find(b) != std::string::npos; //This is wrong
        });

        const std::vector<std::string>test_set {
                "ttyOfk",
                "ttyS05",
        };

        BOOST_TEST(ports == test_set);
    }

最佳答案

假设我们有两组字符串:A 和 B。B 包含 A 中字符串的一组潜在前缀。因此我们想从 A 中获取每个元素 a，并尝试将其与 B 的所有潜在前缀相匹配。 如果找到匹配的前缀，我们将结果 a 存储在 C 中。简单的解决方案在 O(|A| |B|) 中有效。你问:我们可以优化这个吗？

你说，B已经排好序了。然后我们可以在线性时间内在B上建立一个广义前缀树，并用A中的每个字符串查询它，以O(|A|+|B)求解。问题是，对 B 进行排序需要 O(|B| log|B|) 并且树是非平凡的。

所以我提供了一个 O(|A| log|B|) 的简单解决方案，如果 |A|，它比 O(|A|+|B|) 更有效很小，就像你的例子一样。仍然假设 B 已排序(排序实际上是这里的上限...)。

bool
validate_prefixes(const std::multiset<std::string>& keys) {
    auto itb = keys.begin(), it = itb;
    if(it == keys.end()) return false; //no keys
    for(++it; it != keys.end(); ++it) {
        if( (*it).find(*itb) != std::string::npos ) return false; //redundant keys
        itb++;
    }
    return true;
}

bool
copy_from_intersecting_prefixes(const std::vector<std::string>& data, 
                                std::multiset<std::string>& prefix_keys,
                                std::vector<std::string>& dest, bool check = false) {
    if(check && !validate_prefixes(prefix_keys)) return false;

    for(auto it_data = data.begin(); it_data != data.end(); ++it_data) {
        auto ptr = prefix_keys.insert(*it_data), ptrb = ptr;
        if(ptrb != prefix_keys.begin()) {  //if data is at the start, there is no prefix
            if( (*ptr).find(*(--ptrb)) != std::string::npos ) dest.push_back(*it_data);
        }
        prefix_keys.erase(ptr);
    } //Complexity: O(|data|) * O( log(|prefix_keys|) ) * O(substr) = loop*insert*find
    return check;
}

//.... in main()
std::multiset<std::string> tmp(comport_keys.begin(), comport_keys.end()); //copy const    
copy_from_intersecting_prefixes(devices, tmp, ports);

validate_prefixes 强制执行前提条件。它检查我们是否有至少一个有效的前缀，并且这些键不是自匹配的。例如。我们可以有键 cu 和 cu2，但是 cu 是 cu2 的前缀，所以它们不能两个有效前缀，要么 cu 过于笼统，要么 cu2 过于具体。如果我们尝试将 cu3 与 cu 和 cu2 匹配，这是不一致的。这里 validate_prefixes(comport_keys) 返回 true，但最好自动检查它。

copy_from_intersecting_prefixes 完成实际要求的工作。它遍历A，把a放在有序的B里面。前缀小于前缀+结尾，所以如果存在相应的前缀，它会出现在B之前的a之前。因为键不是自匹配的，我们知道前缀将在 B 中的 a 之前。因此我们从 a 递减迭代器并进行比较。请注意，前缀可能等于 a，因此我们需要多重集。

关于c++ - 使用子串比较的两个字符串集之间的交集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55969798/