Polynomial Rolling Hash for Strings
You'll learn: How to compute a single numeric hash value for a string by treating it as a polynomial expression.
The Core Idea
The basic string hashing approach you learned earlier (like summing character values) has a big problem: it produces the same hash for anagrams. "abc" and "cab" would collide constantly!
Polynomial rolling hash solves this by making position matter. We treat the string as coefficients of a polynomial, where each character's position gives it a different "weight."
The formula is:
h(s) = s[0] × p^(n-1) + s[1] × p^(n-2) + ... + s[n-1]
Where:
s[i]is the numeric value of character at positioni(like ASCII value)pis a prime number base (commonly 31 or 53)nis the string length
Why This Works
Think of it like place values in our number system. In decimal, "123" means 1×100 + 2×10 + 3×1. Each digit's position changes its contribution. Similarly, 'a' at position 0 contributes much more (p^(n-1)) than 'a' at the last position.
For string "abc" with p=31:
h = 'a'×31² + 'b'×31¹ + 'c'×31⁰
h = 97×961 + 98×31 + 99×1
h = 93,217 + 3,038 + 99 = 96,354
String "cab" would give a completely different hash because each character appears at different positions with different weights.
The word "rolling" hints at an optimization you'll learn later: you can update the hash efficiently when sliding through a string.
Key Takeaway: Polynomial rolling hash computes h(s) = s[0]*p^(n-1) + s[1]*p^(n-2) + ... + s[n-1], giving each character a position-dependent weight to minimize collisions between similar strings.