Ukkonen’s O(ND) algorithm for edit distance (wavefront style)

Each wave d has two phases. Expand: every unassigned right, down or diagonal neighbour of an ed = d−1 cell gets ed = d. Extend: from every ed = d cell, walk down the diagonal while A[j] = B[i]; those cells also have ed = d. After wave d, all cells with ed ≤ d are known. Stop when the bottom-right cell is reached; cells never visited are never computed. Click a cell to jump to the phase that assigns it. Keys: step, back, w next wave, f run all, r reset, g grey values, a keep arrows.

2earlier waves (ed < d) 3current wave (ed = d) 3extended along a matching diagonal in this phase 4reference value, not computed by the algorithm A[j] = B[i] assigned in this phase expand (+1) extend (+0, match)