LCS

using System.Collections.Generic;

namespace Longest_Common_Subsequence
{
    using System;

    public class LongestCommonSubsequence
    {
        public static void Main()
        {
            Console.Write("firstStr = ");
            var firstStr = Console.ReadLine();
            Console.Write("secondStr = ");
            var secondStr = Console.ReadLine();
            
            var lcs = FindLongestCommonSubsequence(firstStr, secondStr);

            Console.WriteLine("Longest common subsequence:");
            Console.WriteLine("  first  = {0}", firstStr);
            Console.WriteLine("  second = {0}", secondStr);
            Console.WriteLine("  lcs    = {0}", lcs);
        }

        public static string FindLongestCommonSubsequence(string firstStr, string secondStr)
        {
            int firstLen = firstStr.Length + 1;
            int secondLen = secondStr.Length + 1;
            var lcs = new int[firstLen, secondLen];

            for (int i = 1; i < firstLen; i++)
            {
                for (int j = 1; j < secondLen; j++)
                {
                    if (firstStr[i - 1] == secondStr[j - 1])
                    {
                        lcs[i, j] = lcs[i - 1, j - 1] + 1;
                    }
                    else
                    {
                        lcs[i, j] = Math.Max(lcs[i - 1, j], lcs[i, j - 1]);
                    }
                }
            }

            return RetrieveLcs(firstStr, secondStr, lcs);
        }

        public static string RetrieveLcs(string firstStr, string secondStr, int[,] lcs)
        {
            List<char> lcsLetters = new List<char>();
            int x = firstStr.Length;
            int y = secondStr.Length;
            while (x > 0 && y > 0)
            {
                if ((firstStr[x - 1] == secondStr[y - 1]))
                {
                    lcsLetters.Add(firstStr[x]);
                    x--;
                    y--;
                }
                else if (lcs[x, y] == lcs[x - 1, y])
                {
                    x--;
                }
                else
                {
                    y--;
                }
                Console.WriteLine(string.Join(", ", lcsLetters));
            }

            lcsLetters.Reverse();

            return new string(lcsLetters.ToArray());
        }
    }
}