基礎LCS



import java.util.Scanner;

public class UVA10405 {

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  Scanner sc = new Scanner(System.in);

  while(sc.hasNext())
  {
   String s1 = sc.nextLine();

   String s2 = sc.nextLine();

   char[] c1 = new char[s1.length()+1];
   char[] c2 = new char[s2.length()+1];

   for(int s =1;s<s1.length()+1;s++)
   {
    c1[s] = s1.charAt(s-1);
   }

   for(int s =1;s<s2.length()+1;s++)
   {
    c2[s] = s2.charAt(s-1);
   }

   int matrix[][] = new int[1001][1001];

   int max = 0;

   for(int n = 1;n<s1.length()+1;n++)
   {
    for(int m = 1;m<s2.length()+1;m++)

    {
     if(c1[n] == c2[m])
      matrix[n][m] = matrix[n-1][m-1] + 1;
     else
      matrix[n][m] = Math.max(matrix[n-1][m], matrix[n][m-1]);

     if(max <matrix[n][m])
      max = matrix[n][m];
    } 
   }
   System.out.println(max);
  }
  sc.close();
 }
}