Как стать автором
Обновить
19
0

Пользователь

Отправить сообщение

Полиномиальные хеши и их применение

Время на прочтение9 мин
Количество просмотров87K
Здравствуй, хабр. Сегодня я напишу, как можно использовать полиномиальные хеши (далее просто хеши) при решении различных алгоритмических задач.

Введение


Начнем с определения. Пусть у нас есть строка s0..n-1. Полиномиальным хешем этой строки называется число h = hash(s0..n-1) = s0 + ps1 + p2s2 +… + pn-1sn-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а si — код i-ого символа строки s (почти во всех современных языках он записывается s[i]).

Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство.
Читать дальше →
Всего голосов 74: ↑69 и ↓5+64
Комментарии41

Информация

В рейтинге
Не участвует
Зарегистрирован
Активность