Fast, memory efficient Levenshtein algorithm

Function Levenshtein(ByVal String1 As String, ByVal String2 As String, ByVal LMax As Integer) As Integer

        Dim cost As Integer                  ' cost
        Dim CurrentCost As Integer          ' Current Levenshtein distance, for each Column.
        Dim MinLen As Integer = Math.Min(String1.Length, String2.Length)

        If (String1.Length > 1000 Or String2.Length > 1000) Then
            MsgBox("La taille limite des mots est de 1000 lettres", MsgBoxStyle.Exclamation, "Texte trop long")
            Return 99
        End If

        ' If difference of length between 2 strings is greater than LMax, then return 99 
        If (Math.Abs(String1.Length - String2.Length) > LMax) Then
            Return 99
        End If

        String1 = String1.ToUpper
        String2 = String2.ToUpper

        ' OPTIONAL for accentuated words
        String1 = No_accents(String1)
        String2 = No_accents(String2)

        ' Step 0 : going fast through the first N identical letters.
        For i = 0 To MinLen - 1
            If (String1(i) = String2(i)) Then
                If i = MinLen - 1 Then
                    String1 = String1.Substring(i + 1)
                    String2 = String2.Substring(i + 1)
                    Exit For
                Else
                    Continue For
                End If
            End If
            String1 = String1.Substring(i)
            String2 = String2.Substring(i)
            Exit For
        Next
        Dim String1Len As Integer = String1.Length  ' length of String1
        Dim String2Len As Integer = String2.Length  ' length of String2

        ' Step 1
        If (String1Len = 0 Or String2Len = 0) Then Return Math.Max(String1.Length, String2.Length)

        ' Create the two vectors
        Dim v0 As Integer() = New Integer(String1Len + 1) {}
        Dim v1 As Integer() = New Integer(String1Len + 1) {}
        'Dim vTmp As Integer()

        ' Step 2
        ' Initialize the first vector
        For i = 1 To String1Len
            v0(i) = i
        Next

        ' Step 3
        ' For each column
        For i = 1 To String2Len
            ' Set the 0'th element to the column number
            v1(0) = i

            ' Reset CurrentCost to 0
            ' Step 4
            For j = 1 To String1Len

                ' Step 5
                If (String1(j - 1) = String2(i - 1)) Then
                    cost = 0
                Else
                    cost = 1
                End If

                ' Step 6
                ' Find minimum
                v1(j) = Math.Min(v0(j) + 1, Math.Min(v1(j - 1) + 1, v0(j - 1) + cost))

                ' We get the current Levenshtein distance, which is the minimum value of the column
                If j = 1 Then
                    CurrentCost = v1(1)
                Else
                    CurrentCost = Math.Min(v1(j), CurrentCost)
                End If
            Next
            ' The current Levenshtein distance is greater than the set limit.
            ' No need to continue, as Levenshtein distance can only grow up
            If CurrentCost > LMax Then Return 99

            ' Swap the vectors
            Dim vTmp = v0
            v0 = v1
            v1 = vTmp
        Next

        ' Step 7
        ' The vectors where swaped one last time at the end of the last loop,
        ' that is why the result is now in v0 rather than in v1
        Return (v0(String1Len))
  
    End Function

    Function No_accents(ByVal Chaine As String) As String
        Dim a As String = "ÀÁÂÃÄÅÈÉÊËÌÍÎÏÑÒÓÔÕÖÙÚÛÜÝàáâãäåèéêëìíîïðñòóôõöùúûüýÿ"
        Dim b As String = "AAAAAAEEEEIIIINOOOOOUUUUYaaaaaaeeeeiiiionooooouuuuyy"
        For i As Integer = 0 To a.Count - 1
            Chaine = Chaine.Replace(a.Substring(i, 1), b.Substring(i, 1))
        Next i
        Return Chaine.ToUpper
    End Function

<pre>    Function Levenshtein(ByVal sRow As String, ByVal sCol As String, ByVal LMax As Integer) As Integer

        Dim RowLen As Integer = sRow.Length  ' length of sRow
        Dim ColLen As Integer = sCol.Length  ' length of sCol
        Dim MaxLen = Math.Max(RowLen, ColLen)
        Dim cost As Integer                  ' cost

        If MaxLen > 1000 Then
            MsgBox("La taille limite des mots est de 1000 lettres", MsgBoxStyle.Exclamation, "Texte trop long")
            Return 99
        End If

        ' Step 1
        If (RowLen = 0 Or ColLen = 0) Then Return MaxLen

        ' Create the two vectors
        Dim v0 As Integer() = New Integer(RowLen + 1) {}
        Dim v1 As Integer() = New Integer(RowLen + 1) {}
        'Dim vTmp As Integer()

        ' Step 2
        ' Initialize the first vector
        For i = 1 To RowLen
            v0(i) = i
        Next

        ' Step 3
        ' For each column
        For j = 1 To ColLen
            ' Set the 0'th element to the column number
            v1(0) = j

            ' Step 4
            For i = 1 To RowLen

                ' Step 5
                If (sRow(i - 1) = sCol(j - 1)) Then
                    cost = 0
                Else
                    cost = 1
                End If

                ' Step 6
                ' Find minimum
                v1(i) = Math.Min(v0(i) + 1, Math.Min(v1(i - 1) + 1, v0(i - 1) + cost))
            Next

            ' Swap the vectors
            Dim vTmp = v0
            v0 = v1
            v1 = vTmp
        Next

        ' Step 7
        ' Value between 0 - 100   (0 = perfect match ; 100 = totaly different)
        ' 
        ' The vectors where swaped one last time at the end of the last loop,
        ' that is why the result is now in v0 rather than in v1
        Return ((100 * v0(RowLen)) / MaxLen)

    End Function

public static float LevenshteinDistance(string a, string b)
{
    var rowLen = a.Length;
    var colLen = b.Length;
    var maxLen = Math.Max(rowLen, colLen);

    // Step 1
    if (rowLen == 0 || colLen == 0)
    {
        return maxLen;
    }

    /// Create the two vectors
    var v0 = new int[rowLen + 1];
    var v1 = new int[rowLen + 1];

    /// Step 2
    /// Initialize the first vector
    for (var i = 1; i <= rowLen; i++)
    {
        v0[i] = i;
    }

    // Step 3
    /// For each column
    for (var j = 1; j <= colLen; j++)
    {
        /// Set the 0'th element to the column number
        v1[0] = j;

        // Step 4
        /// For each row
        for (var i = 1; i <= rowLen; i++)
        {
            // Step 5
            var cost = (a[i - 1] == b[j - 1]) ? 0 : 1;

            // Step 6
            /// Find minimum
            v1[i] = Math.Min(v0[i] + 1, Math.Min(v1[i - 1] + 1, v0[i - 1] + cost));
        }

        /// Swap the vectors
        var vTmp = v0;
        v0 = v1;
        v1 = vTmp;
    }

    // Step 7
    /// The vectors were swapped one last time at the end of the last loop,
    /// that is why the result is now in v0 rather than in v1
    return 100.0f * v0[rowLen] / maxLen;
}

such as,
akitten To sitting：

            kitten （a→ ）

            sitten （k→s）

            sittin （e→i）

            sitting（ →g）