Хеширование против суффиксных структур: что выбрать и каков риск анти-хеш тестов?
Многие строковые задачи решаются и хешами, и суффиксным массивом/автоматом. Когда что выбирать на олимпиаде? Боюсь, что напишу хеши, а жюри положит анти-хеш тест и я получу WA на последнем тесте. Насколько это реальный риск?
2 ответа
Сравнение по осям:
Хеши — плюсы: пишутся за 5 минут, сравнение подстрок O(1), бинпоиск по LCP даёт O(n log n) для многих задач, гибкость. Минусы: вероятностные (риск коллизии), и существуют анти-хеш тесты под популярные базы/модули.
Суффиксный массив/автомат — плюсы: детерминированы, O(n) или O(n log n) гарантированно, никаких коллизий. Минусы: дольше писать, легче ошибиться в индексах.
Практическая стратегия: если задача требует именно «сравнить произвольные подстроки / найти повтор / число различных подстрок» и ограничения средние — берите хеши, но защитите их: модуль 2^61-1, случайная база (mt19937_64 от времени). Заготовленный анти-хеш тест строится под КОНКРЕТНУЮ базу; случайная база его обходит почти наверняка. Двойной хеш — дополнительная страховка.
Риск реален в основном при фиксированной базе вроде 31/131 и модуле 1e9+7: под них есть готовые генераторы коллизий, и на Codeforces их регулярно применяют (взлом в open hacking). С рандомизацией и 2^61-1 шанс провалиться — порядка q^2/2^61, то есть практически ноль.
Итог: хеши — быстро и почти всегда безопасно ПРИ рандомизации; суффиксные структуры — когда нужна гарантия или хеши не выражают задачу.
Добавлю конкретику про «последний тест»: классический провал — это когда вы захардкодили base=31, mod=1e9+7 и сдали задачу, где доступен hacking. Соперники прогоняют ваш сабмит через известный антитест и валят его. Лечится одной строкой: uint64_t base = uniform_int_distribution<uint64_t>(256, M-1)(rng);. После этого построить контртест под вашу базу нельзя, не зная сид.