Skip to content

Strings -> Hashing

Rolling hashes for substring equality, borders, Rabin-Karp style matching, and collision-aware verification.

  • Topic slug: strings/hashing
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 1
  • Repo companion pages: 0
  • Curated external problems: 7

Microtopics

  • rolling-hash
  • prefix-hash
  • substring-equality
  • double-hash
  • Rabin-Karp
  • collision-analysis

Learning Sources

Source Type
cp-algorithms string hashing Reference
USACO Guide hashing Reference
Princeton substring search Course

Practice Sources

Source Type
CSES Finding Periods Practice
CSES Finding Borders Practice

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
String Hashing Kattis Easy Rolling Hash, Substring Comparison - - LCS; Equality Direct, judge-style hashing practice with low overhead and clean input.
Good Substrings Codeforces Medium Distinct Substrings Enumeration; Deduplication Rolling Hash; Set Or Map Deduplication Trie; Substrings; Hash Or Trie A standard distinct-substring counting problem where hashing trims the search space.
Watto and Mechanism Codeforces Medium Dictionary Matching - - One-Change; String-Lookup; Collision-Safe Canonical one-edit string membership problem; hashing is a standard solution.
rolling_hash Library Checker Medium Rolling Hash - - Substring Comparison Purpose-built official hashing benchmark; very close to the core technique.
Palindrome Queries CSES Hard Rolling Hash, Dynamic Queries Data-Structure-Heavy; Offline/Online Hybrid Prefix Hashes; Modular Arithmetic; Segment Trees Palindrome; Range Queries; Substring-Equality; Updates Classic rolling-hash use case for fast substring equality under updates.

Challenge

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
"a" String Problem Codeforces Hard - Query Processing; Invariant Maintenance Rolling Hash; Suffix Structures; Substring Comparison Suffix Structures A modern hard string problem where hashing is one of the intended tools.
String Set Queries Codeforces Hard - Online; Dynamic Data Structures Rolling Hash; Online Processing; Prefix Sums Online Queries; String Sets Strong fit for hash-based substring matching in a fully online setting.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
FINDINGBORDERS Finding Borders primary easy rolling hash; prefix-suffix equality; proper borders enumeration Note Code

Regeneration

python3 scripts/generate_problem_catalog.py