Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

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

Полиномиальное хэширование позволяет преобразовать последовательность $S$ длины $N$ в число $H$, представив $S$ в виде полинома:

$H = \sum_{i = 1}^{N}{int(S_i)\ \bullet\ P^i}$

где:

• $int(x)$ - функция преобразования члена последовательности в целое число

• $P$ - некоторое число; при этом должно выполняться условие $P > max(int(S_i))$

Элементы строк - символы - преобразуются в числа по их индексу в таблице кодировки символов.

---

Псевдокод

Аннотация:
si_int - индекс символа в таблице кодировки символов

функция полиномиального хеширования(строка, простое число)
    хэш-значение_строки = 0
    число N = длина строки
    для i от 1 до N
        символ_строки = символ на позиции i в строке
        число si_int = индекс символ_строки в таблице кодировки символов
        хэш-значение_строки = хэш-значение_строки + простое_число^i * si_int
    вернуть хэш-значение_строки

---

Реализация на Python

Аннотация:
polynomial_hash - Полиномиальный хэш
string - строка, которую нужно захэшировать 
number - простое число
result - хэш-значение строки
i - степень простого числа
char - символ строки

def polynomial_hash(string, number):
    result = 0
    for i, char in enumerate(string):
        result += ord(char) * number ** i
    return result

---

Олимпиадная реализация на C++

Аннотация:
pol_hash - Полиномиальный хэш
str - строка, которую нужно захэшировать 
num - простое число
res - хэш-значение строки
i - индекс символа числа и степень простого числа
size - размер

#include <cmath>
#include <string>

uint64_t pol_hash(const std::string &str, uint64_t num) {
  uint64_t res = 0;
  for (int i = 0; i < s.size(); ++i) res += std::pow(num, str) * str[i];
  return res;
}