//******************************************************************************************************//  LongestCommonSubsequence.cs - Gbtc////  Copyright © 2013, Grid Protection Alliance.  All Rights Reserved.////  Licensed to the Grid Protection Alliance (GPA) under one or more contributor license agreements. See//  the NOTICE file distributed with this work for additional information regarding copyright ownership.//  The GPA licenses this file to you under the MIT License (MIT), the "License"; you may//  not use this file except in compliance with the License. You may obtain a copy of the License at:////      http://www.opensource.org/licenses/MIT////  Unless agreed to in writing, the subject software distributed under the License is distributed on an//  "AS-IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. Refer to the//  License for the specific language governing permissions and limitations.////  Code Modification History://  ----------------------------------------------------------------------------------------------------//  04/14/2013 - Kevin D. Jones//       Generated original version of source code.////****************************************************************************************************** using System; // TODO: Please add comments to these classesusing System.Diagnostics.CodeAnalysis; #pragma warning disable 1591 namespace GSF.FuzzyStrings{    public static partial class ComparisonMetrics    {        public static string LongestCommonSubsequence(this string source, string target)        {            int[,] C = LongestCommonSubsequenceLengthTable(source, target);             return Backtrack(C, source, target, source.Length, target.Length);        }         [SuppressMessage("Microsoft.Performance", "CA1814:PreferJaggedArraysOverMultidimensional")]        private static int[,] LongestCommonSubsequenceLengthTable(string source, string target)        {            int[,] C = new int[source.Length + 1, target.Length + 1];             for (int i = 0; i < source.Length + 1; i++)            {                C[i, 0] = 0;            }            for (int j = 0; j < target.Length + 1; j++)            {                C[0, j] = 0;            }             for (int i = 1; i < source.Length + 1; i++)            {                for (int j = 1; j < target.Length + 1; j++)                {                    if (source[i - 1].Equals(target[j - 1]))                    {                        C[i, j] = C[i - 1, j - 1] + 1;                    }                    else                    {                        C[i, j] = Math.Max(C[i, j - 1], C[i - 1, j]);                    }                }            }             return C;        }         [SuppressMessage("Microsoft.Performance", "CA1814:PreferJaggedArraysOverMultidimensional")]        private static string Backtrack(int[,] C, string source, string target, int i, int j)        {            if (i == 0 || j == 0)            {                return "";            }            else if (source[i - 1].Equals(target[j - 1]))            {                return Backtrack(C, source, target, i - 1, j - 1) + source[i - 1];            }            else            {                if (C[i, j - 1] > C[i - 1, j])                {                    return Backtrack(C, source, target, i, j - 1);                }                else                {                    return Backtrack(C, source, target, i - 1, j);                }            }        }    }}