сорри, не совсем понял где этот переход делается

я к тому, что решение задачи для надмножества можно переделать в решение задачи про подмножества, просто взяв у всех множеств из задачи дополнения

а почему это работает? (сорри, я до сих пор не понял как это работает)

A подмножество B <=> дополнение B подмножество дополнения A

а, понятно, спасибо

trie (в частности это set-trie) ведь только расти могут?

из префиксного дерева можно и удалять что-нибудь (отмечая вершины, соответсвующие добавленным строкам и храня количество отметок в поддереве)

Можно и нативно удалять

Ну да, можно

Но отметки всё равно нужны

в set-trie нет

там нужно тогда будет хранить отдельно пометки о том что в поддереве есть что-то

Ну преф дерево - это все-таки бор)

Или я что-то путаю?

вот такой сет-три

круг - терминал

проверь, что есть подмножество множества {1, 2, 3}

ребятки, есть такого рода задачка:

A B
B F
C E
D E
E G
F G
G _

где первое значение - ключ, второе - переход по ключу.

Цель - минимизировать по одинаковым буквам в значениях.  И необязательно соседние и могут быть много.
Чтобы получилось:
A a2
a2 a3
a3 G
G _

То есть сначала берем E F обьединяем в одно, назовем a3 и переход на G (так и остается)
Потом потом видим что в B C D заменились F E E на a3 a3 a3 и соответственно обьедияем их в a2 и переход на a3. Ну и у A меняется на a2 переход.

Я пробовал тупо в лоб итерацией от начала до конца, но тогда оно сначала обьединит С и D а потом уже E и F а B останется без внимания, так что такой вариант не подходит.
Есть идеи алгоритма?

PS: Лучше не спрашивайте зачем это)) В универе есть предмет - теория вычислительных процессов, там какие-то автоматы, буковки непонятные, я так и не понял зачем и я решил по приколу написать прогу для вычисления. Там как раз вот такая же фигня только больше столбцов и строк. Я привел сильно упрощенный пример.

теория вычислений.... реально фигня такая. ненужная прям