using System;
using System.Diagnostics;
using System.Linq;

public class Program
{
    public static Int32 LevDist(string s1, string s2)
    {
        var m = s1.Length;
        var n = s2.Length;

        // Edge cases.
        if (m == 0)
        {
            return n;
        }
        if (n == 0)
        {
            return m;
        }

        var v0 = Enumerable.Range(0, n + 1).ToArray();
        var v1 = new int[n + 1];
        v0.CopyTo(v1, 0);

        for (var i = 0; i < s1.Length; ++i)
        {
            v1[0] = i + 1;

            for (var j = 0; j < s2.Length; ++j)
            {
                var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                var delCost = v0[j + 1] + 1;
                var insCost = v1[j] + 1;

                v1[j + 1] = Math.Min(substCost, delCost);
                if (insCost < v1[j + 1])
                {
                    v1[j + 1] = insCost;
                }
            }

            var temp = v0;
            v0 = v1;
            v1 = temp;
        }

        return v0[n];
    }

    public static void Main()
    {
        var s1 = new String('a', 15000);
        var s2 = new String('a', 15000);
        var s3 = new String('b', 15000);

        for (var i = 0; i < 5; i++)
        {
            Stopwatch execTimer = new Stopwatch();
            execTimer.Start();

            Console.WriteLine(LevDist(s1, s2));
            Console.WriteLine(LevDist(s1, s3));

            execTimer.Stop();
            var execTime = execTimer.ElapsedMilliseconds / 1000.0;

            Console.WriteLine($"Finished in {execTime:0.000}s");
        }
    }
}