70 lines
1.7 KiB
Plaintext
70 lines
1.7 KiB
Plaintext
#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
|