String Hashing Algorithms - Preparation to IOI Part 5
String Hashing Algorithms
String Hashing Algorithms
Introduction
Many string problems repeatedly ask whether two pieces of text are equal. Comparing the characters directly is simple, but doing it again for thousands of long substrings can become too slow.
String hashing gives every string a compact numeric fingerprint called its hash. Equal strings always receive equal hashes. Therefore, instead of comparing all characters, we can usually compare two numbers.
The most useful version for competitive programming is polynomial hashing together with prefix hashes. After O(n) preprocessing, we can calculate the hash of any substring in O(1) time. This idea is used for substring comparison, pattern matching, palindrome queries, repeated strings, and many other string problems.
Hashing is probabilistic: two different strings can theoretically have the same hash. This is called a collision. We will first understand one hash, then use two independent moduli in the implementation to make collisions extremely unlikely.
Problem and motivation
Suppose we are given a lowercase string s of length n and queries. Each query gives two segments and . We must determine whether the two substrings are equal.
q
[l1,r1]
[l2,r2]
For example, let s=abacaba.
s[1…3]=aba and s[5…7]=aba, so they are equal.
s[2…4]=bac and s[4…6]=cab, so they are different.
We use 1-based positions in this lecture. Assume that both n and q can be as large as 2⋅105.
Naive approach
For each query, first compare the substring lengths. If the lengths are equal, compare the characters one by one from left to right.
In this small function, the string has a leading space so that its useful characters are 1-indexed.
This method is correct, but one query may inspect O(n) characters. With q queries, the total complexity can reach O(nq), which is too slow for the given limits.
Core concept
Turning a string into a number
First, assign a positive number to every character: map a to 1, b to 2, and so on until z is mapped to 26.
We choose a base B, similar to the base of an ordinary number system. For lowercase English letters, B=31 is a common simple choice.
The hash of abc can be written as
1⋅B2+2⋅B+3
It can also be built from left to right:
begin with 0;
append a: 0⋅B+1;
append b: 1⋅B+2;
append c: (1⋅B+2)⋅B+3.
Appending one character is therefore easy. If the current hash is x and the new character has value c, the new hash is x⋅B+c.
The real number grows extremely quickly, so we store it modulo a large number M:
new_hash=(old_hash⋅B+c)modM
Taking the remainder keeps every value small enough to store and does not change the way we extend a hash.
Prefix hashes
Let h[i] be the hash of the first i characters of s. We keep h[0]=0. For every i from 1 to n,
h[i]=(h[i−1]⋅B+value(s[i]))modM
We also precompute powers of the base:
pw[0]=1
pw[i]=(pw[i−1]⋅B)modM
Thus,
pw[i]=BimodM
Removing a prefix
Now consider a substring s[l…r] of length len=r−l+1.
The value h[r] contains the whole prefix s[1…r]. Inside it, the earlier prefix s[1…l−1] is followed by len more characters. Therefore, its contribution has been multiplied by Blen.
We remove this contribution:
get(l,r)=h[r]−h[l−1]⋅Br−l+1
With the modulus included, the formula becomes
get(l,r)=(h[r]−h[l−1]⋅pw[r−l+1])modM
The subtraction may become negative, so we add M before taking the final remainder.
The important result is that get(l,r) is the hash of the substring as if that substring had been hashed on its own. Equal substrings at different positions therefore receive the same value without any additional shifting.
Collisions and double hashing
Because we take values modulo M, the number of possible strings is much larger than the number of possible hashes. Two different strings can occasionally receive the same hash. This is a collision.
One large modulus is often enough for simple tasks, but relying on one hash can be risky. A standard solution is double hashing: calculate the same polynomial hash using two different large moduli. We represent each substring by the pair
(hash1,hash2)
Two substrings are considered equal only when both values are equal. The algorithm remains the same, while an accidental collision becomes extremely unlikely in ordinary competitive programming problems.
Main algorithm
We maintain two prefix-hash arrays h1 and h2, and two power arrays pw1 and pw2. They use the same base but different moduli.
During preprocessing, h1[i] and h2[i] store the two hashes of s[1…i]. The function get(l,r) removes the prefix ending at l−1 under both moduli and returns the resulting pair.
For every query, we first check the lengths. Substrings of different lengths cannot be equal. If the lengths match, we compare their two hash pairs.
Algorithm:
Preprocessing visits every character once. After that, each substring hash uses a constant number of arithmetic operations, so every query is answered in O(1) time instead of comparing the characters one by one.
Applications
Pattern matching
Hash the pattern once. Then calculate the hash of every text substring with the same length. A matching hash pair marks a likely occurrence of the pattern. The total complexity is O(n+m) for a text of length n and a pattern of length m.
Palindrome queries
Build prefix hashes for the string and for its reversed copy. A substring is a palindrome when its forward hash equals the hash of the corresponding reversed segment. This allows each palindrome query to be checked in O(1) time.
Longest common prefix of two suffixes
To find how many first characters of two suffixes are equal, binary search the answer. For every tested length, compare the two substring hashes in O(1). One longest-common-prefix query then takes O(logn) time.
Implementation
Complexity
Build:O(n).
Each substring hash:O(1).
Each equality query:O(1).
Memory:O(n).
1. Define build(s):
1.1. Set pw1[0] = 1 and pw2[0] = 1.
1.2. Set h1[0] = 0 and h2[0] = 0.
1.3. For i = 1..n:
1.3.1. Let x = value of s[i].
1.3.2. Set pw1[i] = pw1[i-1] * base % mod1.
1.3.3. Set pw2[i] = pw2[i-1] * base % mod2.
1.3.4. Set h1[i] = (h1[i-1] * base + x) % mod1.
1.3.5. Set h2[i] = (h2[i-1] * base + x) % mod2.
2. Define get(l, r):
2.1. Let len = r-l+1.
2.2. Set x1 = h1[r] - h1[l-1] * pw1[len] % mod1.
2.3. Set x2 = h2[r] - h2[l-1] * pw2[len] % mod2.
2.4. Add the corresponding modulus and take the remainder for x1 and x2.
2.5. Return the pair (x1, x2).
3. Run build(s).
4. For every query (l1, r1, l2, r2):
4.1. If r1-l1 != r2-l2, output No.
4.2. Otherwise, compare get(l1, r1) and get(l2, r2).
4.3. If both hash values are equal, output Yes. Otherwise, output No.
bool equal_slow(const string &s, int l1, int r1, int l2, int r2){ if(r1 - l1 != r2 - l2){ return false;} while(l1 <= r1){ if(s[l1] != s[l2]){ return false;} l1++; l2++;} return true;}
#include <bits/stdc++.h>using namespace std;const int N = 200200;const int base = 31;const int mod1 = 1000000007;const int mod2 = 1000000009;int n;string s;int h1[N], h2[N];int pw1[N], pw2[N];void build(){ pw1[0] = 1; pw2[0] = 1; for(int i = 1; i <= n; i++){ int x = s[i] - 'a' + 1; pw1[i] = 1ll * pw1[i - 1] * base % mod1; pw2[i] = 1ll * pw2[i - 1] * base % mod2; h1[i] =(1ll * h1[i - 1] * base + x) % mod1; h2[i] =(1ll * h2[i - 1] * base + x) % mod2;}}pair<int, int> get(int l, int r){ int len = r - l + 1; int x1 =(h1[r] - 1ll * h1[l - 1] * pw1[len] % mod1 + mod1) % mod1; int x2 =(h2[r] - 1ll * h2[l - 1] * pw2[len] % mod2 + mod2) % mod2; return{x1, x2};}int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> s; n = s.size(); s = " " + s; build(); int q; cin >> q; while(q--){ int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2; if(r1 - l1 != r2 - l2){ cout << "No"<< endl;} else if(get(l1, r1) == get(l2, r2)){ cout << "Yes"<< endl;} else{ cout << "No"<< endl;}} return 0;}