Sorry your browser is not supported!

hide mouse

print "This program calculates the Levenshtein distance between two strings."
print "PRESS ANY KEY TO PROCEED"
wait key

do
   cls
   input "Please enter the source string: "; a$
   input "Please enter the target string: "; b$
   print
   print "String A: "; a$
   print "String B: "; b$
   print "Levenshtein Distance from A to B: "; LevDist(a$, b$)
   print
   print "PRESS ANY KEY TO RESTART OR ESC TO EXIT"
   wait key
loop

end

rem Levenshtein Distance
function LevDist(s$, t$)
   m = len(s$)
   n = len(t$)

   rem for all i and j, d[i,j] will hold the Levenshtein distance between
   rem the first i characters of s$ and the first j characters of t$
   rem note that d has (m+1)*(n+1) values.
   dim d(m, n)

   rem source prefixes can be transformed into empty string by dropping all characters
   for i = 1 to m
      d(i, 0) = i
   next i

   rem target prefixes can be reached from empty source prefix by inserting every characters
   for j = 1 to n
      d(0, j) = j
   next j

   for j = 1 to n
      for i = 1 to m
         if mid$(s$, i) = mid$(t$, j)
            d(i, j) = d(i-1, j-1)   :`no operation required
         else
            rem find the lowest of the three values
            del = d(i-1, j) + 1     :` a deletion
            ins = d(i, j-1) + 1     :` an insertion
            sub = d(i-1, j-1) + 1   :` a substitution

            if del < ins then min = del else min = ins
            if min > sub then min = sub

            d(i, j) = min
         endif
      next i
   next j
endfunction d(m, n)

rem latch
rem 11/12/2006
rem beginning spell checker

dim position$(0)

gap = wordgap("darkbasicclassic","darkwaterclassic")

print gap
print "Differences at positions: ";position$(0)

end
function wordgap(word1$,word2$)
   rem set up variables - create temp$ so we never touch original words
   temp1$=word1$
   temp2$=word2$
   lenword1=len(word1$)
   lenword2=len(word2$)
   gap=0
   position$(0)=""

   rem check for longest word and base further comparisons on that - add spaces
   rem to the end of the shortest word to return nonmatching positions later
   if lenword2 > lenword1
      maxlen=lenword2
      for addspaces = 1 to maxlen
         temp1$=temp1$+chr$(32)
      next addspaces
   else
      maxlen=lenword1
      for addspaces = 1 to maxlen
         temp2$=temp2$+chr$(32)
      next addspaces
   endif

   rem compare letter to letter position by position each word - increase gap - mark position
   for compare = 1 to maxlen
      if mid$(temp1$,compare) <> mid$(temp2$,compare)
         inc gap
         position$(0)=position$(0)+","+str$(compare)
      endif
   next compare

endfunction gap