Algorithm dossier

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

Why this snippet is Knuth-Morris-Pratt

Why KMP. Two phases. Phase one builds the *failure function* f over the pattern: f[i] is the length of the longest proper prefix of p[0..i] that's also a suffix. Phase two walks the text and uses f to skip redundant comparisons on a mismatch. Distinguisher. Two near-identical loops with while (k > 0 && p[k] !== ...) k = f[k - 1] — the prefix-table fallback. Boyer-Moore would scan right-to-left.

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.