import java.util.Scanner;

public class LCS0
{

   public static int solveLCS(int i, int j, String x, String y)
   {
      int sol1, sol2, sol3;

      if (i == 0 || j == 0)
      {
         return(0);
      }

      if ( x.charAt(i-1) == y.charAt(j-1) )
      {
         sol1 = solveLCS(i-1, j-1, x, y);
         return(sol1 + 1);
      }
      else
      {
         sol2 = solveLCS(i-1, j, x, y);
         sol3 = solveLCS(i, j-1, x, y);
	 if ( sol2 >= sol3 )
            return( sol2 );
         else
            return( sol3 );
      }
   }


   public static void main(String[] args)
   {

       String x;
       String y;
       int r;

       Scanner in = new Scanner(System.in);

       System.out.print("String x = ");
       x = in.next();
       System.out.print("String y = ");
       y = in.next();

       r = solveLCS(x.length(), y.length(), x, y);

       System.out.println("LCS(x,y) = " + r);
   }

}