Click above to get retro games delivered to your door ever month!

 Return the Levenshtein distance between two strings
------------------------------------------------------------------------------

 Syntax

         GT_LevDist(<cStrA>, <cStrB>) --> nDist

 Arguments:

       <cStrA>     -  First string
       <cStrB>     -  Second String

 Returns:

       nDist       -  Levenshtein Distance.

 Description:

       Return the Levenshtein distance between two strings

       The  Levenshtein  distance  between  two  strings  is  the
       minimum  number  of  operations  (Insertions, Deletions or
       Substitutions) to transform one string to the other.   The
       algoritm used to solve this problem is a prime example  of
       dynamic  programming.   It  is  very  similar  approach to
       solving  the   shortest  distance   between  two    cities
       connected by a network of roads.

       The algorithm  is of  order O(nm)  where n  and m  are the
       lengths  of  the  two  strings.   Therefore  when  the two
       strings are equal  the algoritm is  of order O(n.)  so you
       should   check   for   equality   first   before   calling
       GT_LevDist()

       REFERENCES
       Doctor Dobb's Journal #187, April 1992

       IMPROVEMENTS
       The  main  improvements  in  this  routine will be made by
       introducing a more complex operation costing.

       ie. have three matrices that record the cost of adding  or
           deleting  a  specific   letter,  and  substituting   a
           specified letter with another.

       More improvements can be achieved  but at the loss of  the
       general purpose of the routine.

       This is left as an exercise for the foolhardy or brave.

 Examples:

       ? GT_LevDist("Axolotl", "Axl Rose")      // prints 5

       Axolotl -> Axl Rose in 5 operations

          Axolotl
          Axolote     SUB e for l
          Axolose     SUB s for t
          AxoRose     SUB R for l
          Ax Rose     SUB space for o
          Axl Rose    INS L

 Source: LEVENSHT.PRG

 Author:  Andy M Leighton