using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        string s1="AGGTAB";

        string s2="GXTXAYB";

        int count = LCSubStr(s1,s2,s1.Length,s2.Length);

            Console.WriteLine("LCS"+ count);

​

    }

        static int LCSubStr(string X, string Y, int l1, int l2) {

            int[,] matrix = new int[l1+1,l2+1];

            int result =0, index=0;

            for(int i =1;i<=l1;i++) {

                for(int j=1;j<=l2;j++) {

                    if(i==0|| j==0) {

                        matrix[i,j] =0;

                    }

                    else if(X[i-1] == Y[j-1]) {

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

                        result = Math.Max(result, matrix[i,j]);

                        //index = i-1;

                    }

                    else {

                        matrix[i,j] =Math.Max(matrix[i-1,j] , matrix[i,j-1] );

                        result = Math.Max(result, matrix[i,j]);

                }

​

                }

            }

                //Console.WriteLine(X.Substring(index-result+1, result));

            return result;

        }

​

}