= Solution
Store one maximizing predecessor together with every table value. For <alignment traceback>, start at $(m,n)$ and follow these pointers:
* $(i-1,j-1)$ emits `x[i-1]` opposite `y[j-1]`; the letters are equal because that diagonal candidate was allowed only on a match.
* $(i-1,j)$ emits `x[i-1]` opposite a gap.
* $(i,j-1)$ emits a gap opposite `y[j-1]`.
Continue to $(0,0)$, including boundary moves, then reverse the collected columns. Any deterministic choice among tied predecessors gives an optimal alignment. Each step decreases at least one index, so reconstruction costs \b[$O(m+n)$] additional time and output space. The full score table or predecessor table requires $O(mn)$ storage for positive lengths.
Back to article page
