Хэши

1. Основные понятия и определения

• Хэш-функция — это функция, сопоставляющая объектам из некоторого множества числовые значения из ограниченного промежутка.

Глобальные области применения:

• Криптография

• Кэширование

• Хранение паролей

Применение в алгоритмических задачах:

• Подсчёт количества различных подстрок

• Поиск подстроки в строке

• Проверка подстроки на палиндромность

---

2. Полиномиальное хэширование

Пусть задана строка $S$, символы которой сопоставляются числам от $1$ до $m$. Выбирается модуль $p$ (например, $p={10}^9+7$) и основание (база) $k>m$.

Виды полиномиального хэша:

1. Прямой полиномиальный хэш строки:

$$h_f=(s_0+s_1\cdot k+s_2\cdot k^2+\cdots +s_n\cdot k^n)(\mathrm{mod}p)$$

2. Обратный полиномиальный хэш строки:

$$h_b=(s_0\cdot k^n+s_1\cdot k^{n-1}+\cdots +s_n)(\mathrm{mod}p)$$

3. Сравнение подстрок за $O(1)$

Для эффективного вычисления и сравнения хэшей подстрок используется следующий алгоритм:

1. Массив степеней основания (баз): Предварительно вычисляются и сохраняются степени основания $k^0,k^1,k^2,\dots (\mathrm{mod}p)$.

2. Массив префиксных хэшей: Строится массив $p$, где $p_i$ — это хэш префикса строки от начала до символа $s_i$ включительно.

3. Вычисление хэша произвольной подстроки $[i,j]$: Хэш подстроки определяется с использованием значения префиксного хэша предыдущей части строки, умноженного на соответствующую степень основания $k$, за время $O(1)$.

4. Решение типовых задач с помощью хэшей

1. Поиск подстроки в строке

• Подход: Алгоритм скользящего окна (проход окном по всей строке).

• Временная сложность: $O(n)$.

2. Количество различных подстрок

• Подход: Вычисляются хэши для всех возможных подстрок строки и помещаются в структуру данных set (множество).

• Ответ: Размер множества set.size().

3. Проверка подстроки на палиндромность

• Подход: Сравнивается значение прямого хэша подстроки со значением её обратного хэша. Если хэши совпадают, подстрока с высокой вероятностью является палиндромом.