Skip to main content
📜 WAYPOINT LESSON

Rolling Hash

⭐⭐⭐ advanced⏳ 30 min read📍 Lesson 165 of 281

Treat a string as a base-B number mod a prime; any substring's hash pops out in O(1) from two prefix values.

Substring fingerprints

h[i+1] = h[i]*B + s[i] makes every prefix a number; subtracting scaled prefixes isolates any window. Equality of hashes is a PROXY for equality of strings — double-mod hashing makes collision odds vanishingly small but never zero. Know the failure mode.