Longest Common Subsequence

Longest Common Subsequence

namespace LongestCommonSubSequence
{
    class Program
    {
        public static int[,] buildMatrix(String x, String y)
        {
            int M = x.Length;
            int N = y.Length;
            // opt[i][j] = length of LCS of x[i..M] and y[j..N]
            int[,] opt = new int[M + 1, N + 1];

            // compute length of LCS and all subproblems via dynamic programming
            for (int i = M - 1; i >= 0; i--)
            {
                for (int j = N - 1; j >= 0; j--)
                {
                    if (x[i] == y[j])
                        opt[i, j] = opt[i + 1, j + 1] + 1;
                    else
                        opt[i, j] = Math.Max(opt[i + 1, j], opt[i, j + 1]);
                }
            }

            return opt;
        }

        public static void printLCS(int[,] opt, String x, String y)
        {
            int M = x.Length;
            int N = y.Length;

            // recover LCS itself and print it to standard output
            int i = 0, j = 0;
            while (i < M && j < N)
            {
                if (x[i] == y[j])
                {
                    Console.Write(x[i]);
                    i++;
                    j++;
                }
                else if (opt[i + 1, j] >= opt[i, j + 1])
                    i++;
                else
                    j++;
            }
            Console.WriteLine();
        }


        static void Main(string[] args)
        {
            String s1 = "HOP is what it is";
            String s2 = "HIPHop what is it ?";

            int[,] op = buildMatrix(s1, s2);

            for (int i = 0; i < op.GetLength(0); i++)
            {
                for (int j = 0; j < op.GetLength(1); j++)
                {
                    Console.Write(op[i, j] + "  ");
                }
                Console.WriteLine();
            }
            printLCS(op, s1, s2);
        }
    }
}