using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace NWP
{
    class Program
    {
        static void NWP(String A, String B, int m, int n)
        {
            int[,] N = new int[m + 1, n + 1];
 
            for (int i = 0; i <= m; i++)
            {
                for (int j = 0; j <= n; j++)
                {
                    if (i == 0 || j == 0)
                        N[i, j] = 0;
                    else if (A[i - 1] == B[j - 1])
                        N[i, j] = N[i - 1, j - 1] + 1;
                    else
                        N[i, j] = Math.Max(N[i - 1, j], N[i, j - 1]);
                }
 
            }
 
            int index = N[m, n];
            int temp = index;
 
            char[] nwp = new char[index + 1];
 
            nwp[index] = '\0';
 
 
            int k = m, l = n;
 
            while (k > 0 && l > 0)
            {
                if (A[k - 1] == B[l - 1])
                {
                    nwp[index - 1] = A[k - 1];
                    k--;
                    l--;
                    index--;
                }
                else if (N[k - 1, l] > N[k, l - 1])
                    k--;
                else
                    l--;
            }
 
            Console.Write("Najdluzszy wspolny podciag " + A + " i " + B + " to: ");
            for (int q = 0; q <= temp; q++)
                Console.Write(nwp[q]);
        }
 
 
        public static void Main()
        {
            String A = "Alibaba";
            String B = "Aliexpres";
            int m = A.Length;
            int n = B.Length;
            NWP(A, B, m, n);
            Console.ReadLine();
        }
    }
}