Searching a grid for many target sequences at once, why prune on prefixes rather than full matches?

## The setting You are scanning a genomics-style letter grid for not one target sequence but a whole panel of them — say a few hundred motifs, each ten to twenty bases long — and reporting which ones can be spelled by an adjacent-cell path. The naive composition is one independent search per target: `M` targets times `rows * cols` starts times `3^L` paths. Every one of those searches re-walks the same first two cells of the same grid, because the searches know nothing about each other. ## Where the cost lives, and therefore where pruning must happen In a branching search with factor `b` and depth `L`, the number of nodes at depth `d` is `b^d`, and the number of descendants of one such node is about `b^(L-d)`. The tree is overwhelmingly bottom-heavy: the last level contains more nodes than every level above it combined. Two consequences follow, and they are the whole answer. **A test that only fires at depth `L` saves nothing.** Full-match membership is exactly that test. By the time you can ask "is the accumulated string one of my targets", you have already walked to the bottom of a branch; the answer changes what you report but not what you spent. **A test that fires at depth `d` saves `b^(L-d)` nodes.** So the value of a pruning test is set by how early it can say no. A prefix test — "does any live target begin with the letters I have accumulated?" — can say no at depth two on a panel where no motif starts with those two bases, and that single answer erases the entire subtree beneath. On a four-symbol alphabet with a few hundred targets, most branches die at depth two or three. The search stops being exponential in `L` in practice and becomes roughly proportional to the number of grid positions where some target could plausibly begin. ## Soundness first A pruning test is only allowed to cut branches that **cannot** contain a solution. Prefix testing is sound because of a monotone property of strings: if the accumulated letters are not a prefix of any target, then no extension of them is a prefix either, and in particular no extension equals a target. Pruning is therefore lossless — it changes runtime and nothing else. This is the property to check before adopting any pruning idea, and the place candidates go wrong is with heuristics that feel safe but are not. "Give up if we have not matched a target within `L` steps" is fine; "give up if the remaining unvisited cells contain fewer of the next symbol than the target needs" is also fine and genuinely useful; "give up on branches that revisit an area we searched a moment ago" is **not** sound, because a different path through the same area is a different candidate. ## Incrementality, or the pruning costs more than it saves A test that fires early is worthless if it is expensive. Recomputing, at every node, whether the accumulated string is a prefix of any of `M` targets by scanning them costs `O(M * L)` per node. Multiply that by the node count and the pruning can cost more than the subtree it removes — the classic "my optimisation made it slower" result. The fix is to make the prefix state **incremental and reversible**, which is the same discipline as the visited mark: 1. Carry a small piece of state down the recursion representing "the set of targets still consistent with the letters so far". 2. On stepping into a cell, **extend** that state by one symbol — a constant or near-constant operation against a prefix index built once from the panel, not a rescan of all targets. 3. If the extension leaves no live target, return immediately. 4. On backtracking out of the cell, **restore** the previous state, exactly as you un-mark the cell. The index over the target panel is built once, up front, and amortised across every cell of every search. That build cost is why the technique pays on a panel of hundreds of targets and does not pay on a panel of one. ## Two operational details seniors are expected to raise **Retire targets as they are found.** Once a motif has been reported, drop it from the live set so its subtrees stop being explored and it cannot be reported twice by a different path. On a panel with many hits this is a large win late in the scan, and it turns the search's cost curve downward over time rather than flat. **Know when not to do this.** For a single short target the prefix machinery is pure overhead: an index to build, extra state to thread through the recursion, and a second data structure that must stay consistent with a grid someone may mutate. The plain per-target search is simpler and, at `M = 1`, faster. The crossover is a judgment call, and the honest version of it names the maintenance cost as well as the runtime: a colleague debugging a wrong result now has to reason about two structures and their synchronisation, not one. ## The transferable rule Pruning is worth exactly what it removes, and what it removes is a subtree whose size is exponential in the depth *remaining*. So the question to ask of any candidate pruning test is not "is it clever" but "how early can it say no, is it sound when it does, and what does it cost me at every node where it says yes?"