Set-trie
Задача
Дано $S$ множеств, суммарного размера $sum$, дается множество $x$, требуется проверить есть ли среди $S$ множеств хотя бы одно его подмножество.
Решение
Отсортируем все множества в лексикографическрм порядке, затем сложим их в бор, теперь отсортируем также множество $x$, заметим, что подмножество $x$ есть в $S$ тогда и только тогда, когда есть хоть один путь, заканчивающийся в терминальной вершине бора, который является подмножеством $x$, тогда давайте идти по множеству $x$, пусть мы сейчас смотрим на $x_{i}$ и стоим в вершине $v$, пусть в боре из $v$ есть переход по $x_{i}$, запустимся рекурсивно в него, уже рассматривая $(i+1)$-ый элемент, если мы не нашли подмножество, то запустимся из вершины v, рассматривая $(i+1)$-ый элемент.
Асимптотика
Асимптотика данного решения - $O(sum)$, если множества уже отсортированы, несложно придумать решение двумя указателями за такую же асимптотику, интереснее константа этого решения на случайных данных.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin