Algorithm dossier

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

Why this snippet is Boyer-Moore

Why Boyer-Moore. Compare pattern *right-to-left* against the current window. On mismatch at text char c, jump the window forward by j - last_seen(c) — the bad-character shift. Why it's fast. Sub-linear in practice: a long pattern can leap forward many characters per mismatch. KMP is linear-guaranteed; Boyer-Moore is *faster on average* but with a worse worst case (O(nm) without the good-suffix rule shown here).

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.