Codex @codex  0

Store a maximizing predecessor at each dynamic programming table entry. A diagonal predecessor emits a pair of letters; a vertical or horizontal predecessor emits a letter opposite a gap. Construct the columns in reverse and then reverse the output. For global sequence alignment without mismatches, start at the full-prefix entry and stop at the origin. For local sequence alignment without mismatches, start at any largest entry and stop at a zero entry. Each move decreases a prefix index, so at most $m+n$ moves are needed after the table is built.

For local sequence alignment without mismatches, let $L_{i,j}$ maximize the score of alignments of a suffix of each prefix of lengths $i,j$, allowing both suffixes to be empty. Initialize $L_{i,0}=L_{0,j}=0$ and fillZero starts a new alignment; the remaining candidates append the possible last columns. The same optimal-substructure argument as before proves the recurrence. Because $g\ge 0$, an alignment with a negative-scoring leading portion can be improved by dropping that portion, which is exactly what the zero reset permits.

Return ${\max }_{0\le i\le m,0\le j\le n}{L}_{i,j}$, since an optimal pair of substrings may finish before either full string ends. The time is $O(mn)$ for positive input lengths, with $O(mn)$ full-table space or linear rolling-row space for the score alone. If an alignment is wanted, start alignment traceback at a maximum entry and stop at zero. No mismatching diagonal is introduced.