import java.util.*;

public class LCS_dp
{
   static int L[][];


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

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


      for (i = 1; i < x.length()+1; i++) 
      {
         for (j = 1; j < y.length()+1; j++)
	 {
            if ( x.charAt(i-1) == y.charAt(j-1) )
            {
               L[i][j] = L[i-1][j-1] + 1;
            }
            else
            {
               if ( L[i-1][j] >= L[i][j-1] )
               {
                  L[i][j] = L[i-1][j];
               }
               else
               {
                  L[i][j] = L[i][j-1];
               }
            }
         }
      }

      return( L[x.length()][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();

       L = new int[x.length()+1][y.length()+1];

       r = solveLCS(x, y);

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

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

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

       for (i = 0; i < x.length()+1; i++)
       {
          if ( i < 10 )
	     System.out.print(" ");
          System.out.print(" " + i + "  ");

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

}