Анаграммы Толстого
Составитель кроссвордов ищет в «Войне и мире» анаграммы — разные слова из одних и тех же букв, как «краем», «рамке» и «мраке». Он выписал слова романа подряд, как они идут в тексте, с повторами. Помогите ему: найдите все группы анаграмм и самую большую из них.
Важно, какие буквы и сколько раз стоят в слове, а порядок не важен: «кот», «ток» и «кто» образуют одну группу, а «тот» и «то» — нет, потому что букв «т» у них разное число. Одно и то же слово, встреченное в тексте несколько раз, — это одно слово. Группой считаются хотя бы два разных слова.
Один из тестов — весь словарь романа, 47 585 разных слов, другой — его английский перевод.
Вход
В первой строке число n (1 ≤ n ≤ 200 000). Дальше n слов через пробелы и переводы строк. Слово состоит из строчных русских букв (а–я, ё) или строчных латинских букв, его длина от 1 до 30.
Выход
В первой строке — число групп анаграмм. Если оно больше нуля, во второй строке — самая большая группа: её слова в порядке возрастания через пробел. Слова сравниваются по кодам символов, поэтому латиница идёт раньше кириллицы, а «ё» — после «я». Если самых больших групп несколько, выведите ту, чьё первое слово меньше.
Примеры
Пример 1
8 кот ток кто сон нос лев вел кот
3 кот кто ток
Пример 2
6 мир рим мир то тот мир
1 мир рим
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сравнивать каждое слово с каждым — 47 585² / 2, больше миллиарда пар. Нужен способ сразу сказать, в какую группу попадает слово, не глядя на остальные.
2Подсказка 2
Придумайте для слова «паспорт» — строку, которая одинакова у всех анаграмм и различна у всех остальных слов. Тогда группы — это просто слова с одинаковым паспортом, а собрать их поможет словарь «паспорт → множество слов».
3Подсказка 3
Подойдёт ли сумма кодов букв? У анаграмм она одинакова. Посчитайте суммы у «ад» и «бг».
4Идея
Паспорт слова — его буквы, отсортированные по алфавиту: у «краем», «рамке» и «мраке» это «акемр». Два слова — анаграммы ровно тогда, когда их отсортированные буквы совпадают, поэтому такой ключ не ошибается ни в одну сторону. Кладём каждое слово в хеш-таблицу по этому ключу, в множество — чтобы повторы из текста не считались разными словами. Группы — множества, где хотя бы два слова.
5Разбор
Один проход по словам: ключ "".join(sorted(w)), множество groups[key] пополняется словом. Потом выбираем множества размера от двух, сортируем слова внутри и берём наибольшее; при равенстве размеров — то, где первое слово меньше. В Go строки сравниваются по байтам, а в UTF-8 порядок байтов совпадает с порядком кодов символов, так что «ё» и там окажется после «я».
Почему не сумма кодов: это хеш, а не паспорт. Равные суммы бывают у слов, которые вовсе не анаграммы: у «ад», «бг» и «вв» сумма 2148. В словаре романа таких склеек сотни, и вместо 1126 групп получается 1558. Хеш годится, чтобы быстро разложить слова по корзинам, но решать, равны ли ключи, должно точное сравнение — так устроена любая хеш-таблица.
Можно и без сортировки: паспортом служит вектор из 33 счётчиков букв. Для длинных слов это быстрее, для слов из романа — всё равно.
5+Решение
6Сложность
Сортировка букв слова длины L — O(L log L), операции со словарём в среднем O(L) на хеширование ключа. Итого O(N log L), где N — суммарная длина всех слов, плюс сортировка слов внутри групп.
7Типичные ошибки
- Сумма кодов или произведение простых вместо отсортированных букв. Сумма склеивает чужие слова (третий тест). Произведение простых чисел, по одному на букву, — честный паспорт, но в 32 или 64 битах оно переполняется, и снова появляются ложные совпадения.
- Множество букв вместо отсортированного списка.
set("тот")равноset("то"), хотя это не анаграммы: теряется, сколько раз встречается буква. - Список вместо множества. «мир» трижды в тексте — это не группа из трёх слов (второй пример).