using System;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices.ComTypes;

namespace Levenshtein
{
    public static class Levenshtein
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
        public static int Min(int d0, int d1, int d2, int bx, int ay)
        {
            return d0 < d1 || d2 < d1
                ? d0 > d2
                    ? d2 + 1
                    : d0 + 1
                : bx == ay
                    ? d1
                    : d1 + 1;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
        public static int Evaluate(string a, string b)
        {
            var la = a.Length;
            var lb = b.Length;

            while (la > 0 && (a[la - 1] == b[lb - 1]))
            {
                --la;
                --lb;
            }

            var offset = 0;

            while (offset < la && a[offset] == b[offset])
            {
                ++offset;
            }

            la -= offset;
            lb -= offset;

            if (la == 0 || lb < 3)
            {
                return lb;
            }

            var dd = Int32.MaxValue;

            int x = 0;
            int y = 0;
            int d0 = 0;
            int d1 = 0;
            int d2 = 0;
            int d3 = 0;
            int dy = 0;
            int ay = 0;
            int bx0 = 0;
            int bx1 = 0;
            int bx2 = 0;
            int bx3 = 0;

            var view = new int[la * 2];


            for (var i = 0; i < view.Length; ++y)
            {
                view[i++] = y + 1;
                view[i++] = a[offset + y];
            }

            var len = view.Length - 1;

            while (x < lb - 3)
            {
                bx0 = b[offset + (d0 = 0)];
                bx1 = b[offset + (d1 = x + 1)];
                bx2 = b[offset + (d2 = x + 2)];
                bx3 = b[offset + (d3 = x + 3)];
                x += 4;

                dd = x;

                for (y = 0; y < len; y += 2)
                {
                    dy = view[y];
                    ay = view[y + 1];
                    d0 = Min(dy, d0, d1, bx0, ay);
                    d1 = Min(d0, d1, d2, bx1, ay);
                    d2 = Min(d1, d2, d3, bx2, ay);
                    dd = Min(d2, d3, dd, bx3, ay);
                    view[y] = dd;
                    d3 = d2;
                    d2 = d1;
                    d1 = d0;
                    d0 = dy;
                }
            }
            while (x < lb)
            {
                bx0 = b[offset + (d0 = x)];
                dd = ++x;
                for (y = 0; y < len; y += 2)
                {
                    dy = view[y];
                    dd = Min(dy, d0, dd, bx0, view[y + 1]);
                    view[y] = dd;
                    d0 = dy;
                }
            }

            return dd;
        }
    }
}