Hashing Ladder

Who This Is For

Use this ladder when exact string tools feel too rigid, and you want a flexible way to compare many arbitrary substrings quickly.

Warm-Up

• compare two substrings quickly
• binary search on longest common prefix

Core

• prefix hash + powers
• double hashing or strong 64-bit style hashing

Stretch

• distinct-substring style counting

Retrieval Layer

• exact quick sheet -> String Hashing hot sheet
• rolling fingerprint starter -> rolling-hash.cpp
• compare against exact string-family chooser -> String cheatsheet

Exit Criteria

You are ready to move on when you can:

• write a correct get(l, r) hash extractor
• explain why equal hash does not prove equality
• use hashing inside binary search safely
• decide when KMP or Z is a better exact tool

External Practice

• USACO Guide - Hashing
• CP-Algorithms - String Hashing

Tutorial Link

• String Hashing