Полиномиальные хеши на строках

• Строки
• Хеши

Полиномиальная хэш-функция от строки $S$: $h(S) = S_0 + S_1 b + S_2 b^2 + S_3 b^3 + ... + S_N b^N$

Чтобы не происходило переполнения надо считать этот хеш по модулю большого простого числа $P$ (или, хотя бы числа взаимно простого с $b$). $h(S) = (S_0 + S_1 b + S_2 b^2 + S_3 b^3 + ... + S_N b^N) \mod P$

В качестве $P$ удобно использовать, например, простое число: $10^9+7$

Как найти подходяшие простые числа? Можно просто запомнить несколько подходящих. Или поискать с помощью программы.

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

# -*- utf-8 -*-
# Полиномиальное хеширование строк

from math import *


def is_prime(a):
    """ Простое ли число a? """
    return all(a % i for i in range(2, int(a**0.5 + 0.1) + 1))
    # all возвращает True только если все элементы множества не 0

# Генерируем все простые числа < 100
primes = [x for x in range(2, 100) if is_prime(x)]
print(*primes)

# Простые числа больше миллиарда
primes = [x for x in range(10 ** 9, 10 ** 9 + 1000) if is_prime(x)]
print(*primes)
    

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

// Поиск простых чисел пробным делением: O(sqrt(n)) на одно число

// Простое ли число n: перебираем делители d, пока d * d <= n
pub fn is_prime(n: u64) -> bool {
    if n < 2 {
        return false;
    }
    let mut d = 2;
    while d * d <= n {
        if n % d == 0 {
            return false;
        }
        d += 1;
    }
    true
}

fn main() {
    // Простые числа меньше 100
    let small: Vec<u64> = (0..100).filter(|&n| is_prime(n)).collect();
    println!("{:?}", small);
    // Количество простых чисел в промежутке [10^9, 10^9 + 1000)
    let count = (1_000_000_000..1_000_001_000).filter(|&n| is_prime(n)).count();
    println!("{}", count);
}

Реализация на C++

// Поиск простых чисел пробным делением: O(sqrt(n)) на одно число
#include <iostream>

// Простое ли число n: перебираем делители d, пока d * d <= n
bool is_prime(long long n) {
  if (n < 2) return false;
  for (long long d = 2; d * d <= n; ++d) {
    if (n % d == 0) return false;
  }
  return true;
}

int main() {
  // Простые числа меньше 100
  for (long long n = 0; n < 100; ++n) {
    if (is_prime(n)) std::cout << n << ' ';
  }
  std::cout << '\n';
  // Количество простых чисел в промежутке [10^9, 10^9 + 1000)
  int count = 0;
  for (long long n = 1000000000LL; n < 1000001000LL; ++n) {
    if (is_prime(n)) ++count;
  }
  std::cout << count << '\n';
  return 0;
}

Пример вычисления хеша на C++

const int p = 31;
long long hash = 0, p_pow = 1;
for (size_t i=0; i

Реализация на Python
# Полиномиальный хеш строки h(S) = S_0 + S_1*b + S_2*b^2 + ... mod P: O(|S|)
B = 31  # основание b, как в примере на C++
P = 10 ** 9 + 7  # большое простое число


def poly_hash(s):
    """Хеш строки: буква 'a' дает 1, 'b' - 2 и т.д., чтобы у строки 'aaa' хеш был ненулевым."""
    result = 0
    power = 1  # b^i mod P
    for ch in s:
        result = (result + (ord(ch) - ord("a") + 1) * power) % P
        power = power * B % P
    return result


if __name__ == "__main__":
    print(poly_hash("abc"))  # 1 + 2*31 + 3*31^2 = 2946
    print(poly_hash("ab"))  # 1 + 2*31 = 63
    print(poly_hash("ba"))  # 2 + 1*31 = 33


Реализация на Rust
// Полиномиальный хеш строки h(S) = S_0 + S_1*b + S_2*b^2 + ... mod P: O(|S|)
pub const B: u64 = 31; // основание b, как в примере на C++
pub const P: u64 = 1_000_000_007; // большое простое число

// Хеш строки: буква 'a' дает 1, 'b' - 2 и т.д., чтобы у строки "aaa" хеш был ненулевым
pub fn poly_hash(s: &str) -> u64 {
    let mut result = 0;
    let mut power = 1; // b^i mod P
    for ch in s.bytes() {
        let value = ch as u64 - b'a' as u64 + 1;
        result = (result + value * power) % P;
        power = power * B % P;
    }
    result
}

fn main() {
    println!("{}", poly_hash("abc")); // 1 + 2*31 + 3*31^2 = 2946
    println!("{}", poly_hash("ab")); // 1 + 2*31 = 63
    println!("{}", poly_hash("ba")); // 2 + 1*31 = 33
}