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