FiveTech Support Forums

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int levenshtein(const string &s1, const string &s2)
{
   int N1 = s1.size();
   int N2 = s2.size();
   int i, j;
   vector<int> T(N2+1);

   for ( i = 0; i <= N2; i++ )
      T[i] = i;

   for ( i = 0; i < N1; i++ ) 
   {
      T[0] = i+1;
      int corner = i;
      for ( j = 0; j < N2; j++ ) 
      {
         int upper = T[j+1];
         if ( s1[i] == s2[j] )
            T[j+1] = corner;
         else
            T[j+1] = min(T[j], min(upper, corner)) + 1;
         corner = upper;
      }
   }
   return T[N2];
}

//Algoritmo de Levenshtein
FUNCTION LevenshteinDistance(s1, s2)
    LOCAL m, n, matriz, i, j, coste

    m := Len(s1)
    n := Len(s2)
    matriz := Array(m+1, n+1)

    FOR i := 0 TO m
        matriz[i][0] := i
    NEXT

    FOR j := 0 TO n
        matriz[0][j] := j
    NEXT

    FOR i := 1 TO m
        FOR j := 1 TO n
            IF s1[i] <> s2[j]
                coste := 1
            ELSE
                coste := 0
            ENDIF
            matriz[i][j] := Min(matriz[i-1][j] + 1, matriz[i][j-1] + 1, matriz[i-1][j-1] + coste)
        NEXT j
    NEXT i

 RETURN matriz[m][n]

matriz[i][j] := Min(matriz[i-1][j] + 1,Min( matriz[i][j-1] + 1, matriz[i-1][j-1] + coste))

   FOR i := 0 TO m
        matriz[i][0] := i
    NEXT

    FOR j := 0 TO n
        matriz[0][j] := j
    NEXT

//Algoritmo de Levenshtein
FUNCTION LevenshteinDistance(s1, s2)
    LOCAL m, n, matriz, i, j, coste, jCn, iCn

    m := Len(s1)
    n := Len(s2)
    matriz := Array(m+1, n+1)

    iCn := 0
    FOR i := 1 TO m+1
        matriz[i][1] := iCn
        iCn++
    NEXT

    jCn := 0
    FOR j := 1 TO n+1
        matriz[1][j] := jCn
        jCn++
    NEXT

    FOR i := 2 TO m+1
        FOR j := 2 TO n+1
            IF substr(s1,i-1,1) != substr(s2,j-1,1)
                coste := 1
            ELSE
                coste := 0
            ENDIF
            matriz[i][j] := Min(matriz[i-1][j] + 1,Min( matriz[i][j-1] + 1, matriz[i-1][j-1] + coste))
        NEXT j
    NEXT i
    
RETURN matriz[m+1][n+1]