Hashing

Hashing de strings

Recursos
Fuente	Recurso	Notas
CPH	26.3 - String Hashing
cp-algo	String Hashing	código
PAPS1	19.3 - Hashing	muchas aplicaciones
rng-58	Hashing and Probability of Collision

Plantilla

Como se menciona en los artículos de arriba, no hace falta calcular inversos modulares.

C++JavaPython


class HashedString {
  private:
	// change M and B if you want
	static const long long M = 1e9 + 9;
	static const long long B = 9973;
 
	// pow[i] contains B^i % M
	static vector<long long> pow;
 
	// p_hash[i] is the hash of the first i characters of the given string
	vector<long long> p_hash;
 
  public:
	HashedString(const string &s) : p_hash(s.size() + 1) {
		while (pow.size() <= s.size()) { pow.push_back((pow.back() * B) % M); }
 
		p_hash[0] = 0;
		for (int i = 0; i < s.size(); i++) {
			p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
		}
	}
 
	long long get_hash(int start, int end) {
		long long raw_val = (p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
		return (raw_val % M + M) % M;
	}
};
vector<long long> HashedString::pow = {1};


import java.util.*;
 
public class HashedString {
	// Change M and B if you want
	public static final long M = (long)1e9 + 9;
	public static final long B = 9973;
 
	// pow[i] contains B^i % M
	private static ArrayList<Long> pow = new ArrayList<>();
 
	// pHash[i] is the hash of the first i characters of the given string
	private long[] pHash;
 
	public HashedString(String s) {
		if (pow.isEmpty()) { pow.add(1L); }
		while (pow.size() <= s.length()) { pow.add((pow.get(pow.size() - 1) * B) % M); }
 
		pHash = new long[s.length() + 1];
		pHash[0] = 0;
		for (int i = 0; i < s.length(); i++) {
			pHash[i + 1] = ((pHash[i] * B) % M + s.charAt(i)) % M;
		}
	}
 
	public long getHash(int start, int end) {
		long rawVal = pHash[end + 1] - (pHash[start] * pow.get(end - start + 1));
		return (rawVal % M + M) % M;
	}
}


class HashedString:
	# Change M and B if you want
	M = int(1e9) + 9
	B = 9973
 
	# pow[i] contains B^i % M
	_pow = [1]
 
	def __init__(self, s: str):
		while len(self._pow) <= len(s):
			self._pow.append((self._pow[-1] * self.B) % self.M)
 
		# p_hash[i] is the hash of the first i characters of the given string
		self._p_hash = [0 for _ in range(len(s) + 1)]
		for i in range(len(s)):
			self._p_hash[i + 1] = (
				((self._p_hash[i] * self.B) % self.M + ord(s[i]))
			) % self.M
 
	def get_hash(self, start: int, end: int) -> int:
		raw_val = self._p_hash[end + 1] - (
			self._p_hash[start] * self._pow[end - start + 1]
		)
		return raw_val % self.M

Esta implementación calcula

\texttt{hsh}[i + 1] = \left(\sum_{x = 0}^i B^{i - x} \cdot S[x]\right) \bmod M

El hash de cualquier subcadena particular $S[a : b]$ se calcula entonces como

\left(\sum_{x = a}^b B^{b - x} \cdot S[x] \right) \bmod M = (\texttt{hsh}[b + 1] - \texttt{hsh}[a] \cdot B^{b - a + 1}) \bmod M

usando sumas de prefijos. Esto es conveniente porque la potencia más alta de $B$ en ese polinomio siempre será $B^{b - a}$ .

Como $10^9 + 9$ es primo, la probabilidad de colisión al usar este hash es a lo sumo $\frac{N}{10^9 + 9} < 10^{-4}$ , por el lema de Schwarz-Zippel. Esto significa que si se seleccionan dos strings distintos cualesquiera de longitud a lo sumo $N=10^5$ y una base aleatoria módulo $10^9 + 9$ (p. ej. $9973$ en el código), la probabilidad de que hasheen al mismo valor es a lo sumo $10^{-4}$ .

C++

En C++, una forma prácticamente imposible de hackear para generar $B$ en la implementación de arriba es usar un generador de números aleatorios sembrado con un reloj de alta precisión, como se describe aquí .


mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const ll B = uniform_int_distribution<ll>(0, M - 1)(rng);

Búsqueda de strings

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CCC	Searching For Strings	Fácil	Hashing	en el módulo

Explicación - Un hash

Usaremos una ventana deslizante sobre $H$ para encontrar las “coincidencias” con $N$ .

Como no nos importa el orden relativo al comparar dos subcadenas, podemos guardar tablas de frecuencias de los caracteres en la ventana actual y en $N$ . Al deslizar la ventana, a lo sumo dos valores de esa tabla cambian. Para comparar dos subcadenas, simplemente comparamos los 26 valores de cada tabla.

Si solo necesitáramos contar el número de coincidencias, lo anterior bastaría (de hecho, IOI 2006 Writing es justo eso). Sin embargo, necesitamos contar las permutaciones distintas de $N$ en $H$ , así que hay que ser un poco más ingeniosos.

Una forma de resolverlo es guardar los hashes polinómicos de cada coincidencia en un conjunto, ya que esperamos que permutaciones distintas tengan hashes polinómicos distintos. La respuesta sería simplemente el tamaño de ese conjunto al final.

Usar un módulo relativamente pequeño como $M=10^9+9$ no pasará (ver la nota de arriba sobre la paradoja del cumpleaños). En su lugar, usamos $M=2^{61}-1$ .

Implementación

Complejidad temporal: $\mathcal O((|N| + |H|) \cdot \Sigma)$ , donde $\Sigma$ es el tamaño del alfabeto.

Probabilidad de fallo: $\mathcal O\left(\frac{|N||H|^2}{M}\right)$

C++


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
// BeginCodeSnip{HashedString}
class HashedString {
  private:
	// change M and B if you want
	static const ll M = (1LL << 61) - 1;
	static const ll B;
 
	// pow[i] contains B^i % M
	static vector<ll> pow;
 
	// p_hash[i] is the hash of the first i characters of the given string
	vector<ll> p_hash;
 
	__int128 mul(ll a, ll b) { return (__int128)a * b; }
	ll mod_mul(ll a, ll b) { return mul(a, b) % M; }
 
  public:
	HashedString(const string &s) : p_hash(s.size() + 1) {
		while (pow.size() < s.size()) { pow.push_back(mod_mul(pow.back(), B)); }
		p_hash[0] = 0;
		for (int i = 0; i < s.size(); i++) {
			p_hash[i + 1] = (mul(p_hash[i], B) + s[i]) % M;
		}
	}
 
	ll get_hash(int start, int end) {
		ll raw_val = p_hash[end + 1] - mod_mul(p_hash[start], pow[end - start + 1]);
		return (raw_val + M) % M;
	}
};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
vector<ll> HashedString::pow = {1};
const ll HashedString::B = uniform_int_distribution<ll>(0, M - 1)(rng);
// EndCodeSnip
 
int freq_target[26], freq_curr[26];
string n, h;
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> h;
	if (n.size() > h.size()) {
		cout << 0 << '\n';
		return 0;
	}
	HashedString hs(h);
 
	set<ll> good;
	for (int i = 0; i < n.size(); i++) {
		// Update frequency table
		freq_target[n[i] - 'a']++;
		freq_curr[h[i] - 'a']++;
	}
	for (int i = n.size() - 1; i < h.size(); i++) {
		if (i >= n.size()) {
			// Update frequency table
			freq_curr[h[i] - 'a']++;
			freq_curr[h[i - n.size()] - 'a']--;
		}
		bool match = true;
		for (int j = 0; j < 26; j++) { match &= freq_curr[j] == freq_target[j]; }
		if (match) { good.insert(hs.get_hash(i + 1 - n.size(), i)); }
	}
 
	cout << good.size() << endl;
}

Explicación - Dos hashes

Una solución alternativa sin tablas de frecuencias sería hashear las subcadenas que estamos intentando emparejar. Como el orden no importa, hay que modificar un poco la función de hash.

En particular, en lugar de calcular el hash polinómico de las subcadenas, calcular el producto $(B + s_1)(B + s_2) \dots (B + s_k) \bmod M$ como hash (de nuevo, usando dos módulos). Este hash es conveniente porque el orden relativo de las letras no importa, ya que la multiplicación es conmutativa. Además, como cualesquiera dos strings con tablas de frecuencias distintas se mapean a polinomios distintos en $B$ , hashean al mismo valor con probabilidad a lo sumo $\frac{|N|}{M}$ sobre la elección de $B$ .

Como este hash requiere el inverso modular, hay un factor extra $\log M$ en la complejidad temporal.

Implementación

Complejidad temporal: $\mathcal O((|N| + |H|) \log M)$

Probabilidad de fallo: $\mathcal O\left(\frac{|N||H|^2}{M}\right)$

C++


#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
// BeginCodeSnip{HashedString}
class HashedString {
  public:
	// change M and B if you want
	static const ll M = (1LL << 61) - 1;
	static const ll B;
	static __int128 mul(ll a, ll b) { return (__int128)a * b; }
	static ll mod_mul(ll a, ll b) { return mul(a, b) % M; }
 
  private:
	// pow[i] contains P^i % M
	static vector<ll> pow;
 
	// p_hash[i] is the hash of the first i characters of the given string
	vector<ll> p_hash;
 
  public:
	HashedString(const string &s) : p_hash(s.size() + 1) {
		while (pow.size() < s.size()) { pow.push_back(mod_mul(pow.back(), B)); }
		p_hash[0] = 0;
		for (int i = 0; i < s.size(); i++) {
			p_hash[i + 1] = (mul(p_hash[i], B) + s[i]) % M;
		}
	}
 
	ll get_hash(int start, int end) {
		ll raw_val = p_hash[end + 1] - mod_mul(p_hash[start], pow[end - start + 1]);
		return (raw_val + M) % M;
	}
};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
vector<ll> HashedString::pow = {1};
const ll HashedString::B = uniform_int_distribution<ll>(0, M - 1)(rng);
// EndCodeSnip
 
const auto M = HashedString::M;
const auto B = HashedString::B;
const auto mul = HashedString::mul;
const auto mod_mul = HashedString::mod_mul;
ll inv(ll base, ll MOD) {
	ll ans = 1, expo = MOD - 2;
	while (expo) {
		if (expo & 1) { ans = mod_mul(ans, base); }
		expo >>= 1;
		base = mod_mul(base, base);
	}
	return ans;
}
 
string n, h;
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> h;
	if (n.size() > h.size()) return cout << 0, 0;
	HashedString hs(h);
 
	set<ll> good;
	ll h_hsh = 1, n_hsh = 1;
	for (int i = 0; i < n.size(); i++) {
		// Compute product hashes
		h_hsh = mod_mul(h_hsh, B + h[i] - 'a');
		n_hsh = mod_mul(n_hsh, B + n[i] - 'a');
	}
 
	for (int i = n.size() - 1; i < h.size(); i++) {
		if (i >= n.size()) {
			// Update product hashes using modular inverse
			h_hsh = mod_mul(h_hsh, inv(B + h[i - n.size()] - 'a', M));
			h_hsh = mod_mul(h_hsh, B + h[i] - 'a');
		}
		if (n_hsh == h_hsh) { good.insert(hs.get_hash(i + 1 - n.size(), i)); }
	}
 
	cout << good.size() << '\n';
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CSES	Finding Periods	Muy fácil	Hashing	Solución
Silver	Censoring	Fácil	Hashing	—
CEOI	2017 - Palindromic Partitions	Fácil	Greedy, Hashing	Solución
CF	Check Transcription	Fácil	Hashing	Solución
CF	Fullmetal Alchemist II	Fácil	Hashing	Solución
Gold	Bovine Genomics	Normal	Hashing, Binary Search	Solución
Gold	Lights Out	Normal	Hashing, Simulation	Solución
RMI	2017 - Hangman 2	Normal	Hashing	Solución
COCI	2017 - Osmosmjerka	Normal	Hashing, Probability	Solución
COCI	★ 2021 - Sateliti	Difícil	Hashing, Binary Search	Solución
CF	Liar	Difícil	DP, Hashing	—
Baltic OI	★ 2018 - Genetics	Difícil	Hashing	Solución
COCI	2016 - Zamjene	Muy difícil	Hashing, DSU	Solución
COI	2016 - Palinilap	Muy difícil	Hashing, Binary Search	Solución

Hashing XOR / hashing de Zobrist

Recursos
Fuente	Recurso	Notas
CF	XOR Hashing

El hashing también se puede usar para comprobar si conjuntos de elementos son iguales. Para ello, primero generamos al azar un valor de hash para cada elemento único. Típicamente, el valor de hash es un entero en el rango $[0, 2^{63}-1]$ porque $2^{63}-1$ es el valor máximo de un entero con signo de 64 bits. El hash de un conjunto $S$ es la suma XOR de los valores de hash de todos los elementos de $S$ . Como $x \oplus x = 0$ para todo $x$ , podemos borrar un elemento $s$ del conjunto $S$ aplicando de nuevo el valor de hash de $s$ sobre el hash. La probabilidad de una colisión de $N$ conjuntos es aproximadamente $\frac{N^2}{M}$ , donde $M$ es el valor de hash máximo posible.

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	AC	Prefix Equality	Fácil	XOR Hashing	en el módulo

Explicación

Para cada valor numérico distinto en los arreglos, generamos un entero positivo aleatorio de 64 bits. Con este mapa, podemos construir los hashes XOR de prefijos de $a$ y $b$ .

Un problema que hay que tratar son los elementos duplicados, ya que hacer XOR de un elemento consigo mismo da un valor de $0$ y será equivalente a que nunca hubiera existido. Para corregirlo, usamos un conjunto para detectar valores posteriores duplicados y solo hacemos XOR de un elemento con el hash de prefijo si es nuevo.

Ahora, para responder una consulta, comprobamos si los hashes XOR en los índices dados son iguales.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N + Q)$

C++


#include <chrono>
#include <iostream>
#include <map>
#include <random>
#include <set>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
constexpr long long MAX_VAL = 1e18;
 
/** @return a random integer between 0 and MAX_VAL */
long long rng() {
	static std::mt19937_64 gen(
	    std::chrono::steady_clock::now().time_since_epoch().count());
	return std::uniform_int_distribution<long long>(0, MAX_VAL)(gen);
}
 
int main() {
	int len;
	std::cin >> len;
 
	std::map<int, long long> hash_vals;
	vector<int> a(len);
	for (int &i : a) {
		std::cin >> i;
		// assign a hash value to each unique number in the array
		if (!hash_vals.count(i)) { hash_vals[i] = rng(); }
	}
	vector<int> b(len);
	for (int &i : b) {
		std::cin >> i;
		if (!hash_vals.count(i)) { hash_vals[i] = rng(); }
	}
 
	std::set<int> seen;
	vector<long long> a_xor(len);
	for (int i = 0; i < len; i++) {
		// only add to prefix xor if not encountered before
		if (!seen.count(a[i])) {
			a_xor[i] = hash_vals[a[i]];
			seen.insert(a[i]);
		}
		if (i > 0) { a_xor[i] ^= a_xor[i - 1]; }
	}
 
	seen.clear();
	// do the same thing for b
	vector<long long> b_xor(len);
	for (int i = 0; i < len; i++) {
		if (!seen.count(b[i])) {
			b_xor[i] = hash_vals[b[i]];
			seen.insert(b[i]);
		}
		if (i > 0) { b_xor[i] ^= b_xor[i - 1]; }
	}
 
	int query_num;
	std::cin >> query_num;
	for (int q = 0; q < query_num; q++) {
		int a_set, b_set;
		std::cin >> a_set >> b_set;
		// check if the prefix xors are equal
		cout << (a_xor[--a_set] == b_xor[--b_set] ? "Yes" : "No") << '\n';
	}
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CF	Three Occurrences	Difícil	Two Pointers, XOR Hashing	—
CF	Hyperregular Bracket Strings	Difícil	Combinatorics, XOR Hashing	—
JOI	Mergers	Muy difícil	Trees, XOR Hashing	Solución