Background
Wu, Manber, Myers, Miller (1990): O(NP) variant where P is the number of deletions — up to ~2x fewer diagonals explored than O(ND) when insertions dominate (short→long comparisons, append-heavy logs).
Task (research spike)
- Prototype the O(NP) search behind the existing middle-snake interface.
- Benchmark against the current core on: symmetric edits, append-heavy, delete-heavy, and the pathological worst case.
- Adopt only if it wins clearly somewhere without regressing the typical case; otherwise document the finding and close.
Background
Wu, Manber, Myers, Miller (1990): O(NP) variant where P is the number of deletions — up to ~2x fewer diagonals explored than O(ND) when insertions dominate (short→long comparisons, append-heavy logs).
Task (research spike)