Levenstain.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace Levenstain
{
    public static class Levenstain
    {
        public static int Distance(string s1, string s2)
        {
            var l1 = s1.Length;
            var l2 = s2.Length;

            // equal(i, j) то же самое, что m(S1[i],S2[j])
            // и равна нулю, если символы равны и единице, если иначе
            var equal = new Func<int, int, int>((x, y) => (s1.Substring(x - 1, 1) == s2.Substring(y - 1, 1)) ? 0 : 1);

            // Проверка на пустые строки
            if (l1 == 0 && l2 == 0) return 0;
            if (l1 == 0) return l2;
            if (l2 == 0) return l1;

            // Инициализация и заполнение матрицы
            var matrix = new int[l1 + 1, l2 + 1];
            for (var i = 0; i <= l1; i++) matrix[i, 0] = i;
            for (var j = 0; j <= l2; j++) matrix[0, j] = j;

            //Вычисление расстояния Дамерау-Левенштейна
            for (int i = 1; i <= l1; i++)
            {
                for (int j = 1; j <= l2; j++)
                {
                    // добавление. D(i, j-1) + 1
                    int ins = matrix[i, j - 1] + 1;

                    // удаление. D(i-1,j) + 1
                    int del = matrix[i - 1, j] + 1;

                    // замена. D(i-1, j-1) + m(S1[i],S2[j])
                    int subst = matrix[i - 1, j - 1] + equal(i, j);

                    // элемент матрицы вычисляется как минимальный из трех случаев
                    matrix[i, j] = new List<int> { ins, del, subst }.Min();

                    // дополнение Дамерау по перестановке соседних символов
                    if ((i > 1) && (j > 1) && equal(i, j - 1) == 0 && equal(i - 1, j) == 0)
                        matrix[i, j] = Math.Min(matrix[i, j], matrix[i - 2, j - 2] + equal(i, j));
                }
            }
            return matrix[l1, l2];
        }
    }
}