Lesson 280
String Hashing
Rolling Hash · Rabin-Karp
1:00How polynomial rolling hashes let you compare, search, and deduplicate strings in O(1) per comparison — the engine behind Rabin-Karp pattern matching.
By the end, you can
- Explain why hashing enables O(1) string comparison and state the one-sided guarantee (unequal hashes → unequal strings).
- Compute the polynomial hash of a short string using Horner's rule with a given base.
- Justify the choice of prime base, 1-based character mapping, and large prime modulus.
- Apply the rolling-window formula to update a hash in O(1), including the fix for negative subtraction.
- Trace Rabin-Karp on a small example, identifying real matches and spurious hits.
- Explain why spurious hits require character verification, and how double hashing reduces their probability.
- Compare Rabin-Karp and KMP by average complexity, worst-case complexity, and the multi-pattern use case.
Up next in String Algorithms, Advanced DP & Competitive Techniques
