Пересечение двух наборов строк с подстрокой сравнения

Question

Я знаю, что это сброс велосипеда, но есть ли способ получить набор строк C, между двумя (отсортированными) наборами A, B строк, где 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);
    }

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 и помещает внутрь упорядоченный B. Префикс меньше, чем prefix + end, поэтому, если соответствующий префикс существует, он произойдет до a в B. Поскольку ключи не являются самосогласованными, мы знаем, чтопрефикс будет предшествовать a в B. Таким образом, мы уменьшаем итератор от a и сравниваем.Обратите внимание, что префикс может быть равен a, поэтому нам нужен мультисет.