两个带有子字符串比较的字符串集之间的交集

Question

我知道这是自行车脱落，但有一种方式来获得一组琴弦C，两者之间（分类）设置，字符串，其中B是A的子串，具有复杂性比的更好的说明B 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);
    }

Answer 1

假设我们有两组字符串：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|) ，它比 O(|A|+|B|) 更有效，如果 |A| 很小，就像你的例子一样。仍然假设 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，因此我们需要多重集。