Привет. Помогите придумать алгоритм, желательно в рамках STL/Boost функций и алгоритмов. Нужно вот что: 1. Имеется массив пар "ключ(строка) -> объект". Можно считать, что этот массив упорядочен по "ключ" любым удобным образом. Ключи могут повторяться. 2. На вход приходит строка, назовем ее "значение". 3. Нужно найти все пары "ключ -> объект" в имеющемся массиве, в которых "значение" начинается с "ключ". 4. Среди найденных пар нужно найти пары, у которых длина "ключ" максимальна. Таких пар может быть несколько. Решить надо за O(ln(n)). Догадываюсь что надо сделать что-то типа std::equal_range с собственным предикатом, и заставить его искать методом бинарного поиска, но вот что-то не связать алгоритмы вместе чтобы получилось то что надо. Edit: поправил термины, было не совсем верно)
_DEN_ Я эту же задачу решал на haskell. Подходящая структура называется префиксное дерево. Edit: согласно поправке добавляется возможность поиска по хэш-таблице, перебирая все префиксы "значения". Но префиксное дерево всё ещё в силе (и, очевидно, эффективнее). Сложность в обоих случаях константная (не зависит от числа пар в выбранном ассоциативном контейнере).
_DEN_ поиск по multi-pattern search должен помочь. n -- это у вас что? от кол-ва ключей время поиска не зависит (если есть память), а зависит оно только от длины строки, которая приходит на вход. и зависит оно как O(n). быстрее -- нельзя. но если длинной строки можно пренебречь, то получаем O(1). как всегда для ответа на вопрос не хватает данных. "значение" какой длинны? какое мы имеем распределение по str[m..k]? если можно выделить часть строки, которая для большинства строк разная и коллизий будет немного, то считаем хэш, делаем первичную выборку и дальше уже доруливаем сравнением элементов. при этом мы в идеале имеем O(1) и минимальный оверхид на память.
l_inc kaspersky Все же немного не ясно. Приведу пример. Ключи - это урлы: / -> 1 /about/ -> 2 /contact/ -> 3 /forum/ -> 4 /forum/ -> 5 /forum/thread/ -> 6 /forum/thread/ -> 7 /logout/ -> 8 На вход приходит строка /forum/message/. Наиболее подходящие пары - это 4 и 5. Они удовлетворяют обоим условиям: 1) входящая строка начинается с ключа. Ключ имеет максимальную длину (среди пар, удовлетворяющих п.1). n = 8 = количество пар. Можно на пальцах, как получить 4 и 5 за o(ln(n))?
_DEN_ Префиксное дерево. Идём по дереву посимвольно (переход к следующему поддереву — минимальная константная сложность). Первый символ "\" не отсеивает ни одного элемента (но он сразу отображается на 1, запомним это). Второй символ "f" отсеивает половину элементов. Третий символ "o" и т.д. Когда переходим ко второму слешу, натыкаемся на множество с элементами 4 и 5 (запомним это). Следующее поддерево с символом "m" отсутствует (указатель NULL или просто отсутствие элемента в зависимости от реализации дерева). Последнее найденное отображение отображает самый длинный префикс. Сложность константная, никаких логарифмов. Линейная относительно длины входной строки, но лучше линейной сделать невозможно. Хеш-таблица Опрашиваем таблицу на префикс "/" (сложность опроса каждого символа константная). Находим отображение на 1 (запоминаем). Опрашиваем таблицу на префикс "/f" (ничего не находим). Опрашиваем таблицу на префикс "/fo" (ничего не находим) и т.д. Когда подходим к префиксу "/forum/", натыкаемся на отображение на множество с 4 и 5 (запоминаем). Далее проходим оставшиеся префиксы до конца входной строки и ничего не находим. Последнее найденное отображение отображает самый длинный префикс. Как видно, опять сложность константная. Но теперь с учётом хеширования квадратичная относительно длины строки. Кроме того, в отличие от варианта с префиксным деревом строку нужно проходить до конца, чтобы убедиться в отсутствии отображений более длинных префиксов. Поэтому, как я и сказал в предыдущем посте, очевидно, что вариант с префиксным деревом эффективнее.
_DEN_ совместимость пунктов 2 и 3 после фразы: " в которых 'значение' начинается с 'ключ'.", просто выносит мозг. Только после примера стало болемене чета ясно. Предлагаю использовать предикат, и менять критерий поиска в зависимости от того ищешь для инсерта или для поиска ключа с которого начинается твое значение че та типа как то так: Код (Text): class sort_cr { public: bool operator () (const std::string lhs, const std::string rhs) { if (rhs[0] == '@') { if (rhs.find(lhs) == 1) return false; return lhs > (rhs.c_str() + 1); } else if (lhs[0] == '@') { if (lhs.find(rhs) == 1) return false; return rhs < (lhs.c_str() + 1); } return rhs < lhs; } }; int main() { sort_cr pr; std::multimap<std::string, int, sort_cr> m(pr); m.insert(std::make_pair("/",1)); m.insert(std::make_pair("/about/",2)); m.insert(std::make_pair("/contact/",3)); m.insert(std::make_pair("/forum/",4)); m.insert(std::make_pair("/forum/mess",5)); m.insert(std::make_pair("/forum/thread/",6)); m.insert(std::make_pair("/forum/thread/",7)); m.insert(std::make_pair("/logout/",8)); BOOST_TYPEOF(m)::iterator it = m.find("@/forum/message"); // приаттаченый символ собаки для распознания что в чем ищем return 0; }
l_inc Ага, спасибо, теперь понял. letopisec Ай, шайтан! Клевая идея с приаттаченным символом. Я тоже думал что решение было бы простым, если бы можно было юзать разные предикаты на вставку и на поиск, но через аттач символа как-то не догадался Несколько вопросов: 1) Зачем предикат объявляется объектом на стеке? Разве просто так нельзя? 2) Я правильно понимаю что поиск найдет гарантированно первый итератор от нужного range? 3) Наверно вместо string::find лучше юзать boost::starts_with? Ведь первый будет искать до упора, а второй - до первой разницы? 3) UPD: Наверно лучше даже свой starts_with написать, чтобы избежать создания временных строк и учесть символ '@'?
Решил '@' не включать в функцию сравнения - имхо ничего хорошего это не дает. В общем оформил все по уставу, вот что получилось: Код (Text): template <typename T> class less : std::binary_function<std::basic_string<T>, std::basic_string<T>, bool> { public: typedef T value_type; typedef std::basic_string<value_type> string_type; bool operator () (string_type const& lhs, string_type const& rhs) const { if(rhs[0] == static_cast<value_type>('@')) // Каст законный, ASCII нам гарантирует это :) { if(starts_with(rhs.c_str() + 1, lhs.c_str())) { return false; } else { return lhs > (rhs.c_str() + 1); } } else if(lhs[0] == static_cast<value_type>('@')) { if(starts_with(lhs.c_str() + 1, rhs.c_str())) { return false; } else { return rhs < (lhs.c_str() + 1); } } else { return rhs < lhs; } } private: // Давно не писал подобные штуки, надеюсь что получилось не слишком страшно :) // UPD: работа над ошибками static bool starts_with(value_type const* str, value_type const* target) { for(; *target && *str == *target; ++str, ++target); return !*target; } };
letopisec Решил что вместо '@' можно сохранять указатель за строку-find внутри предиката, и в operator () просто сравнивать значения указателей. Тогда логика получается чище.
letopisec Ну это как в анекдоте про клетку и пять обезьян Так делают в STL и Boost. Х.з., возможно - это прадедушка концептов ) Статик каст - на случай если где-нибудь какой-нибудь компилятор на максимальном уровне варнингирования решит написать ахтунг о том, что сравниваются разнотипные элементы (если класс будет для std::wstring).
