= Local sequence alignment without mismatches
{title2=$L_{i,j}=\max(0,L_{i-1,j}-g,L_{i,j-1}-g,L_{i-1,j-1}+1\text{ if }x_i=y_j)$}
Choose one contiguous <substring> from each <string> and align them under the same matching and gap rules as <global sequence alignment without mismatches>. Let $L_{i,j}$ maximize the score over aligned suffixes of the two prefixes. Zero permits a fresh empty alignment; the other cases extend one ending at adjacent prefix indices. The answer is the largest table entry, which can occur before either input ends. Starting all boundaries at zero yields $O(mn)$ time for positive lengths. <Alignment traceback> stops on reaching zero.
Back to article page
