32 lines
786 B
Text
32 lines
786 B
Text
print levenshteinDistance("kitten", "sitting")
|
|
print levenshteinDistance("rosettacode", "raisethysword")
|
|
end
|
|
function levenshteinDistance(s1$, s2$)
|
|
n = len(s1$)
|
|
m = len(s2$)
|
|
if n = 0 then
|
|
levenshteinDistance = m
|
|
goto [ex]
|
|
end if
|
|
if m = 0 then
|
|
levenshteinDistance = n
|
|
goto [ex]
|
|
end if
|
|
dim d(n, m)
|
|
for i = 0 to n
|
|
d(i, 0) = i
|
|
next i
|
|
for i = 0 to m
|
|
d(0, i) = i
|
|
next i
|
|
for i = 1 to n
|
|
si$ = mid$(s1$, i, 1)
|
|
for j = 1 to m
|
|
tj$ = mid$(s2$, j, 1)
|
|
if si$ = tj$ then cost = 0 else cost = 1
|
|
d(i, j) = min((d(i - 1, j) + 1),min((d(i, j - 1) + 1),(d(i - 1, j - 1) + cost)))
|
|
next j
|
|
next i
|
|
levenshteinDistance = d(n, m)
|
|
[ex]
|
|
end function
|