Всем привет! Многие видели статью пользователя Zlobober, в которой говорилось о том, что строка Туэ-Морса с ужасающей силой валит хеши по модулю 2^64. Одиночные же хэши оказались слишком небезопасными из-за парадокса Дней Рождения. Единственное оставшееся спасение от инфернальных суффиксных структур было двойное хэширование. Однако, скоро и ему прийдёт конец. Основательно изучив строку Туэ-Морса и её возможные модификации, я пришёл к выводу, что тест, ломающий даже решения с двойным хэшем возможен.

Здесь я подробнее описал построение теста, его использование против реальных решений с различных контестов и обоснование его работы.

Теперь же предлагаю пользователям codeforces обсудить, что следует делать в сложившейся ситуации. Неужели больше совсем не осталось способов решать задачи полиномиальными хэшами? У кого какие мысли по этому поводу?