import java.util.*;

public class LCS_lin_space
{
   static int K[][];


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

      for (j = 0; j < y.length()+1; j++)
         K[0][j] = 0;        // x = "" ===> LCS = 0


      for (i = 1; i < x.length()+1; i++) 
      {

         K[1][0] = 0;        // y = "" ===> LCS = 0     

         for (j = 1; j < y.length()+1; j++)
	 {
            if ( x.charAt(i-1) == y.charAt(j-1) )
            {
               K[1][j] = K[0][j-1] + 1;
            }
            else
            {
               K[1][j] = Math.max( K[0][j], K[1][j-1] );
            }
         }

         /* =====================================================
            Recycle phase: copy row K[1][...] to row K[0][...]
	    ===================================================== */
         for ( j = 0; j < y.length()+1; j++)
	    K[0][j] = K[1][j];

      }

      // The value of LCS is in K[1][y.length()]
      return K[1][y.length()];

   }


   public static void main(String[] args)
   {

       Scanner in = new Scanner(System.in);

       String x;
       String y;
       int i, j, r;


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

       K = new int[2][y.length()+1];    // Linear space !!!

       r = solveLCS(x, y);

       System.out.println("Max length = " + r);

       System.out.println();
       System.out.println();

       System.out.println("K[1][]:");
       System.out.print("     ");
       for (j = 0; j < y.length()+1; j++)
          System.out.print("  " + j);
       System.out.println();
       System.out.println("==================================");

       System.out.print("     ");
       for (j = 0; j < y.length()+1; j++)
          System.out.print("  " + K[1][j]);
       System.out.println();
   }

}