1. Prefix hash
Each prefix hash extends the previous one by one character.
prefix[i + 1] = (prefix[i] * base + s.charCodeAt(i)) % modTyporithm · hard
String Hashing
▷ Interactive algorithm labstring-hashingstring-algorithmspolynomial-hashprefix-hashconstant-query
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn String Hashing
String Algorithms
Precompute prefix hashes and base powers so any substring's hash is one O(1) formula.
A polynomial hash treats a string as a number in a chosen base, modulo a large prime.
Storing prefix hashes lets any substring hash be derived by subtracting an aligned prefix.
After an O(n) build, every substring comparison becomes an O(1) hash lookup.
Preparing algorithm lab…
01
Prefix hashes build in O(n).
02
Align with precomputed powers.
03
Substring hash is O(1).
function buildHashes(s) {
const n = s.length;
const base = 131;
const mod = 1000000007;
const prefix = new Array(n + 1).fill(0);
const power = new Array(n + 1).fill(1);
for (let i = 0; i < n; i += 1) {
prefix[i + 1] = (prefix[i] * base + s.charCodeAt(i)) % mod;
power[i + 1] = (power[i] * base) % mod;
}
return function substringHash(left, right) {
const span = right - left + 1;
return ((prefix[right + 1] - prefix[left] * power[span]) % mod + mod) % mod;
};
}Read the implementation
Connect each part of the code to the concept before you type.
2. Powers of base
Precompute base^k to align prefix hashes during subtraction.
power[i + 1] = (power[i] * base) % mod3. Substring hash
Combine two prefix hashes to get any substring's hash in O(1).
return ((prefix[right + 1] - prefix[left] * power[span]) % mod + mod) % modA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.