Given: Strings X,Y ,
Table[0..x,0..y]
BestAlignment (x,y)
Compute
Table[x-1,y] if necessary
Compute
Table[x,y-1] if necessary
Compute
Table[x-1,y-1] if necessary
If X[x]=Y[y] Then
// matches –
no underscores
Table[x,y]=Table[x-1,y-1]
Else
Table[x,y]=min(Table[x-1,y],Table[x,y-1])+1
End If