49 lines
1.3 KiB
Text
49 lines
1.3 KiB
Text
include "ConsoleWindow"
|
|
|
|
local fn LevenshteinDistance( aStr as Str255, bStr as Str255 ) as long
|
|
dim as long m, n, i, j, min, k, l
|
|
dim as long distance( 255, 255 )
|
|
|
|
m = len(aStr)
|
|
n = len(bStr)
|
|
|
|
for i = 0 to m
|
|
distance( i, 0 ) = i
|
|
next
|
|
|
|
for j = 0 to n
|
|
distance( 0, j ) = j
|
|
next
|
|
|
|
for j = 1 to n
|
|
for i = 1 to m
|
|
if mid$( aStr, i, 1 ) == mid$( bStr, j, 1 )
|
|
distance( i, j ) = distance( i-1, j-1 )
|
|
else
|
|
min = distance( i-1, j ) + 1
|
|
k = distance( i, j - 1 ) + 1
|
|
l = distance( i-1, j-1 ) + 1
|
|
if k < min then min = k
|
|
if l < min then min = l
|
|
distance( i, j ) = min
|
|
end if
|
|
next
|
|
next
|
|
end fn = distance( m, n )
|
|
|
|
dim as long i
|
|
dim as Str255 testStr( 5, 2 )
|
|
|
|
testStr( 0, 0 ) = "kitten" : testStr( 0, 1 ) = "sitting"
|
|
testStr( 1, 0 ) = "rosettacode" : testStr( 1, 1 ) = "raisethysword"
|
|
testStr( 2, 0 ) = "Saturday" : testStr( 2, 1 ) = "Sunday"
|
|
testStr( 3, 0 ) = "FutureBasic" : testStr( 3, 1 ) = "FutureBasic"
|
|
testStr( 4, 0 ) = "here's a bunch of words"
|
|
testStr( 4, 1 ) = "to wring out this code"
|
|
|
|
for i = 0 to 4
|
|
print "1st string = "; testStr( i, 0 )
|
|
print "2nd string = "; testStr( i, 1 )
|
|
print "Levenshtein distance ="; fn LevenshteinDistance( testStr( i, 0 ), testStr( i, 1 ) )
|
|
print
|
|
next
|