Хеширование строк. Полиномиальный хеш.
Пререквизиты:
🔙 Сумма, вычитание, произведение, деление по модулю
🔙 Бинарное возведение в степень
Теория:
📚 Algocode wiki - описание, реализация на C++, пример задач с решением (идейным)
📚 Статья на Codeforces - подробное описание, примеры использования, трюки и лайфхаки
📼 Павел Маврин - описание, реализация на псевдокоде
Первые задачи:
💻 ACMP 1
💻 TIMUS 1
💻 ACMP 2
💻 ACMP 3
KIT контест по теме с периодически пополняемыми задачами:
🔄 Контест - сейчас там
уже 5 задач. Для решения нужно вступить в группу на кф -
ссылка
Вопросы на понимание темы:
❓ Почему число p рекомендуется брать строго больше, чем максимальной код символа из задачи?
❗ Если это не так, то при хеше, когда степени p возрастают, появится много очевидных коллизий, когда у вас первые буквы у двух строк разные, но по модулю они равны
❓ Что можно сделать, чтобы уменьшить вероятность коллизии и не получить WA в задаче?
❗ Хороший способ - считать два хеша: один по модулю m1, а второй по модулю m2. Считать строчками равными, если совпадают оба хеша
❓ Допустим в задаче требуется часто умножать на разные степени числа p и мы их каждый раз вычисляем бинарным возведением в степень. Как можно ускорить программу?
❗ Чаще всего в задачах степени будут не больше длины строки (n). Поэтому давайте предпосчитаем все степени числа p за O(n) - один for без использования бинарного возведения в степень. Дальше достаем нужную степень из предпосчитанных значений
Делитесь с друзьями, задачи будут интересны любому уровню!
💬 Следующие темы смело предлагайте в комментариях
Автор:
https://www.tgoop.com/KogutIvanTutoring 
