Algorithm dossier

  • Category: String match
  • Worst-case complexity: O(n)
  • Approach: Iterative
  • Data structure: Hash table
  • First formalised: 1980s

Why this snippet is Rabin-Karp

Why Rabin-Karp. Rolling hash. Compute one hash for the pattern and one for the first text window, then slide the window forward updating the hash in O(1) (subtract the leaving char, multiply by base, add the entering char). On hash match, verify with a real string compare to rule out collisions. The B/M pair. Polynomial hash with base 256 and a large prime modulus — that's the diagnostic shape.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.