Поиск анаграмм и сабанаграмм во всех словах языка

[petropavel]

Тут trie неестественно смотрится. Для [саб]анаграмм порядок букв в слове не важен, поэтому каждое «слово» это просто мешок букв. А trie для строк/слов. В данной задаче каждое слово можно представить как 33-мерный вектор, каждая координата — сколько раз встречается соответствующая буква. Например, «карета» будет <2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 >. Слово является [саб]анаграммой другого слова, если у него значения по всем координатам не больше чем у другого слова. Или, можно сказать, если каждое слово представить кубом <0,0,0...,0>—<a1,a2,...,a33>, то слово будет [саб]анаграммой другого слова, когда его куб полностью лежит внутри другого куба.

То есть логично хранить слова в какой-нибудь структуре данных для многомерных точек. Например, в R-tree.

Чтобы не заморачиваться с операцией удаления, вначале надо отсорировать словарь по длине слова ­— от длинных к коротким. После этого для каждого слова — проверить есть ли оно в R-tree, если есть, то выбросить, если нет, то вставить и вывести как не-анаграмму.

[Lemko]

Изящное решение. Я аплодирую.

[fougasse]

Прямо как на собеседовании в гугл.
Супер!

[Sumor]

Для быстрого определения анаграммы или субанаграммы я использовал для слов построенные индексы длиной uint32 (unsigned int) — если буква в принципе встречается, то её бит установлен, если нет — не установлен (Е=Ё). Для анаграммных слов этот индекс будет совпадать. Для субанаграммных — один индекс включается в другой. Требуется дополнительная проверка слов, но индекс позволяет очень сильно отсеять неподходящие слова.
https://qna.habr.com/q/712389#answer_1528267