//****************************************************
// TITLE: Llcs.java                                  *
// AUTHOR: Kim Skak Larsen                           *
// DATE: 26/11 2001                                  *
//                                                   *
// Reads two strings from stdin and computes the     *
// lengths of the longest common subsequence.        *
//****************************************************

import cs1.Keyboard;

public class Llcs
{
   static int llcsw(String s, String t, int i, int j)
   {
      if (i == s.length() || j == t.length())
         return 0;
      else
         if (s.charAt(i) == t.charAt(j))
            return 1 + llcsw(s, t, i+1, j+1);
         else
            return Math.max(llcsw(s, t, i+1, j),
                            llcsw(s, t, i, j+1));
   } // llcsw

   static int llcs(String s, String t)
   {
      return llcsw(s, t, 0, 0);
   } // llcs

   public static void main (String[] args)
   {
      String s, t;

      System.out.print("1. string: ");
      s = Keyboard.readString();
      System.out.print("2. string: ");
      t = Keyboard.readString();
      System.out.print("llcs(" + s + "," + t + ") = "
                       + llcs(s, t) + "\n");
   } // main

} // Llcs