Polynomial String Hashing
Compare substrings in constant time.
Polynomial String Hashing is a free Coding Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Comparing Substrings Fast
You often need to ask if two substrings are equal. Character-by-character checks are slow, so we turn each string into a number. 🔢
The Hashing Idea
A hash maps a string to a single integer. If two strings differ, their hashes almost always differ too.
Treat Strings as Polynomials
We read each character as a digit in base p. This polynomial view turns the string into one big weighted sum.
h = ord(s[0]) + ord(s[1]) * p + ord(s[2]) * p * pPick a Base and a Modulus
Choose a prime base like 31 and a large prime modulus. The mod keeps numbers small and avoids overflow.
BASE = 31
MOD = 10**9 + 9Computing One Hash
Walk the string and fold each character in with Horner's rule, taking the modulus at every step.
h = 0
for c in s:
h = (h * BASE + ord(c)) % MODPrefix Hashes
Store a prefix hash for every position. Then any substring hash comes from a quick subtraction.
pre[i + 1] = (pre[i] * BASE + ord(s[i])) % MODPowers of the Base
You also precompute powers of the base. They line up the two prefixes when you subtract.
pw[i] = (pw[i - 1] * BASE) % MODSubstring Hash in O(1)
The hash of s[l..r] is a subtraction of two prefix hashes, scaled by a power. Constant time per query.
def sub(l, r):
return (pre[r] - pre[l] * pw[r - l]) % MODWatch Out for Collisions
Two different strings can share a hash; that is a collision. Rare, but contests sometimes craft inputs to trigger it.
Double Hashing for Safety
Use two independent moduli and compare both hashes. A collision in both at once is practically impossible.
Where Hashing Shines
Hashing powers substring comparison, finding repeats, and pattern search. It is a flexible Swiss-army tool.
Quick Check
Pick the right tool for comparing many substrings safely.
Recap: Hashing Wins
You can now turn strings into polynomial hashes, query any substring in O(1), and guard against collisions. 🚀
Frequently asked questions
Is the “Polynomial String Hashing” lesson free?
Yes — the full text of “Polynomial String Hashing” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Polynomial String Hashing”?
Compare substrings in constant time. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Polynomial String Hashing” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- KMP Prefix Function
- Polynomial String Hashing
- Z-Function for Pattern Search
- Tries for Prefix Lookups