Hash

6 Oct 2025

1.Introduction

A hash is a mapping from a relatively large domain to a smaller one, making comparisons convenient.
Its most direct application is determining whether two strings are identical; each comparison takes O(1) time after preprocessing.
Two properties hold: different hash values mean different strings; equal hash values mean the strings are very likely the same.
A hash collision occurs when different original strings have the same hash value.

2.Principle

For a string, convert it into a number. If two numbers differ, their original strings differ; if the numbers are equal, the original strings are very likely the same.

A common choice is to interpret a string as a base-131 or base-13331 number and take it modulo M. M is usually a large prime such as 1e9+537. Choosing prime values for both the base and M greatly reduces the chance of a collision.

3.Implementation

The following iterative process converts a string into a base-131 number.

long long Hash(const string& s) {
	const long long base = 131;
	const long long M = 1000000537LL;
	long long res = 0;
	for(char c : s) {
		res = (res * base) + c;
		res %= M;
	}
	return res;
}

Repeatedly comparing complete strings this way is expensive, and obtaining a substring hash is inconvenient. Instead, maintain a prefix array h, where h[i] is the hash of the first i characters (s[1…i]), and a power array g, where g[i] stores base to the i-th power modulo M. The power array is used to calculate substring hashes.

Preprocess as follows in O(n) time.

for(int i = 1; i <= n; i++) {
		h[i] = (1LL * h[i-1] * base + s[i]) % M;
		g[i] = 1LL * g[i-1] * base % M;
}

The hash of the substring from index l to r can then be obtained in O(1).

auto get = [&](int l, int r) -> int {
		return (h[r] - 1LL * h[l-1] * g[r - l + 1] % M + M) % M;
};

String indices start at 0 while the arrays above start at 1. To make indexing convenient, prepend a blank character:

s = " " + s;

4.Example

Example 1: Luogu P10468

Given a string and q queries, each query provides ranges for two substrings of the original string and asks whether they are equal.

This is a standard application of the technique: use the functions above directly.

Hash

Related Posts