Longest Common Substring

Longest Common Substring

namespace LongestCommonSubstring

{

    class Program

    {

        static int maxLS;

        static int I;

        static int J;

        public static int[,] LCSubstring(String x, String y)

        {

            int M = x.Length;

            int N = y.Length;

            int[,] opt = new int[M + 1, N + 1];

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

            {

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

                {

                    if (x[i - 1] == y[j - 1])

                        opt[i, j] = opt[i - 1, j - 1] + 1;

                    else

                        opt[i, j] = 0;

                    updateLCSubstring(opt[i, j], i, j);

                }

            }

            return opt;

        }

        public static void updateLCSubstring(int LS, int i, int j)

        {

            if (maxLS < LS)

            {

                maxLS = LS;

                I = i;

                J = j;

            }

        }

        public static String printLCSubstring(int[,] opt, String x, String y)

        {

            char[] output = new char[opt[I, J]];

            int i = I - 1;

            int j = output.Length - 1;

            while (j >= 0)

            {

                output[j] = x[i];

                i--;

                j--;

            }

            return new String(output);

        }

        static void Main(string[] args)

        {

            int[,] opt = LCSubstring("Dark blue sea", "Deep Dark blue sea ");

            Console.WriteLine(printLCSubstring(opt, "Dark blue sea", "Deep Dark blue sea "));

            Console.WriteLine("\n\nMatrix for understanding....");

            for (int i = 0; i < opt.GetLength(0); i++)

            {

                for (int j = 0; j < opt.GetLength(1); j++)

                {

                    Console.Write(opt[i, j] + "  ");

                }

                Console.WriteLine();

            }

            Console.ReadLine();

        }

    }

}