两个字符串集合的交集，涉及子串比较。

Question

我知道这是一个很细节的问题，但在两个（排序过的）字符串集合A、B中，是否有一种方法可以获取字符串C的集合，其中B是A的子串，并且复杂度比我的简单解法 A.size * B.size * comp_substr 更好？请注意，保留HTML标记。

    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);
    }

- Superlokkus

---

是的，您可以在B上构建一个广义后缀树，并使用A中的每个字符串查询它，以在O（|A|+|B|）时间内解决此问题。但是，在您的示例代码中，除非其中至少一个集合比实现复杂性大几十万或几百万倍，否则这将不值得实现。 - j_random_hacker

顺便说一句，我不会把寻找更好的算法称为“自行车棚讨论”。辩论是否使用lambda还是手动循环来实现它将是自行车棚讨论的一个例子。 - j_random_hacker

“comport_keys” 在编译时已知吗？将其转换为正则表达式可能是一个解决方案。 - Jarod42

你需要“子串匹配”还是仅仅是“以...开始”？ - Jarod42

将A放入后缀数组中。检查B中的每个字符串，看看A的后缀数组是否包含它。 - geza

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|)，如果 |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，因此我们需要multiset。

- BlueLemon