using System;

public static class Program

{

    public static void Main()

    {

        Console.WriteLine("Williams <=> Williamson:   " + CalculateSimilarity("Williams","Williamson"));

        Console.WriteLine("Williams <=> McWilliamson: " + CalculateSimilarity("Williams","McWilliamson"));

        Console.WriteLine("Williams <=> McWilliams:   " + CalculateSimilarity("Williams","McWilliams"));

        Console.WriteLine("Leary <=> O'Leary:         " + CalculateSimilarity("Leary","O'Leary"));

        Console.WriteLine("Donalds <=> Donaldson:     " + CalculateSimilarity("Donalds","Donaldson"));

        Console.WriteLine("Donalds <=> MacDonalds:    " + CalculateSimilarity("Donalds","MacDonalds"));

        Console.WriteLine("Williams <=> McDonalds:    " + CalculateSimilarity("Williams","McDonalds"));

        Console.WriteLine("Donalds <=> O'Donnell:     " + CalculateSimilarity("Donalds","O'Donnell"));

        Console.WriteLine("Smith <=> Smythe           " + CalculateSimilarity("Smith","Smythe"));

        Console.WriteLine("Smith <=> Smithy           " + CalculateSimilarity("Smith","Smithy"));

    }

​

        public static double CalculateSimilarity(this string source, string target)

        {

            if ((source == null) || (target == null)) return 0.0;

            if ((source.Length == 0) || (target.Length == 0)) return 0.0;

            if (source == target) return 1.0;

​

            int stepsToSame = ComputeLevenshteinDistance(source, target);

            return (1.0 - ((double)stepsToSame / (double)Math.Max(source.Length, target.Length)));

        }

        /*

        /// Returns the number of steps required to transform the source string

        /// into the target string.

        */

        static int ComputeLevenshteinDistance(string source, string target)

        {

            if ((source == null) || (target == null)) return 0;

            if ((source.Length == 0) || (target.Length == 0)) return 0;

            if (source == target) return source.Length;

​

            int sourceWordCount = source.Length;

            int targetWordCount = target.Length;

​

            // Step 1

            if (sourceWordCount == 0)

                return targetWordCount;

​

            if (targetWordCount == 0)

                return sourceWordCount;

​

            int[,] distance = new int[sourceWordCount + 1, targetWordCount + 1];

​

            // Step 2

            for (int i = 0; i <= sourceWordCount; distance[i, 0] = i++) ;

            for (int j = 0; j <= targetWordCount; distance[0, j] = j++) ;

​

            for (int i = 1; i <= sourceWordCount; i++)

            {

                for (int j = 1; j <= targetWordCount; j++)

                {

                    // Step 3

                    int cost = (target[j - 1] == source[i - 1]) ? 0 : 1;

​

                    // Step 4

                    distance[i, j] = Math.Min(Math.Min(distance[i - 1, j] + 1, distance[i, j - 1] + 1), distance[i - 1, j - 1] + cost);

                }

            }

​

            return distance[sourceWordCount, targetWordCount];

        }

}