#define min(a, b) iif((a) < (b), (a), (b))

Sub LevenshteinAlignment(s1 As String, s2 As String)
    Dim As String align1 = "", align2 = ""
    Dim As Integer i, j, len1, len2
    len1 = Len(s1):

    len2 = Len(s2)
    Dim As Integer dp(len1+1, len2+1)

    For i = 0 To len1
        dp(i, 0) = i
    Next i
    For j = 0 To len2
        dp(0, j) = j
    Next j

    For i = 1 To len1
        For j = 1 To len2
            If Mid(s1, i, 1) = Mid(s2, j, 1) Then
                dp(i, j) = dp(i-1, j-1)
            Else
                dp(i, j) = min(min(dp(i-1, j), dp(i, j-1)), dp(i-1, j-1)) + 1
            End If
        Next j
    Next i

    i = len1: j = len2
    While i > 0 And j > 0
        If Mid(s1, i, 1) = Mid(s2, j, 1) Then
            align1 = Mid(s1, i, 1) + align1
            align2 = Mid(s2, j, 1) + align2
            i -= 1: j -= 1
        Elseif dp(i, j) = dp(i-1, j-1) + 1 Then
            align1 = Mid(s1, i, 1) + align1
            align2 = Mid(s2, j, 1) + align2
            i -= 1: j -= 1
        Elseif dp(i, j) = dp(i-1, j) + 1 Then
            align1 = Mid(s1, i, 1) + align1
            align2 = "-" + align2
            i -= 1
        Else
            align1 = "-" + align1
            align2 = Mid(s2, j, 1) + align2
            j -= 1
        End If
    Wend

    While i > 0
        align1 = Mid(s1, i, 1) + align1
        align2 = "-" + align2
        i -= 1
    Wend
    While j > 0
        align1 = "-" + align1
        align2 = Mid(s2, j, 1) + align2
        j -= 1
    Wend

    Print "Levenshtein Distance: "; dp(len1, len2)
    Print align1
    Print align2
    Print
End Sub

LevenshteinAlignment("rosettacode", "raisethysword")
LevenshteinAlignment("place", "palace")

Sleep