1. 


/**
* 10405 - Longest Common Subsequence
*
* Studiengruppe: IFB2C
* Martin Pesl
* Robert Reichart
* Elvin Uzeirovic
*
* Run Time Submission Date
* 0.148 2009-07-06 14:46:33
*/

import java.io.*;

class Main
{

public static void main(String... args)throws Exception{
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
String in = input.readLine();
try{
while(!in.isEmpty()){
char[] A = in.toCharArray();
char[] B = input.readLine().toCharArray();
int zahl=computeLength(A,B);
System.out.println(zahl);
in=input.readLine();
}
}catch(Exception ex){}
}

/**
* Berechnet die Laenge der laengsten gemeinsamen Teilfolge von A und B
*/
static int computeLength(char[] A, char[] B)
{
int n = A.length;
int m = B.length;

// Arrays ueberpruefen
if(n < 1 || m < 1)
return 0;

// Matrix anlegen.
// Array der Laenge n+1 mit Arrays anlegen. n+1, weil wir eine 'Leer-
// zeile' mehr brauchen, als wir Buchstaben haben.
int[][] t = new int[n+1][n+1];

// Matrix initialisieren.
// Arrays der Laenge m+1 im Array anlegen - m+1, s.o. -
// und die erste Spalte befuellen
for(int i=0; i < t.length; i++)
{
t[i] = new int[m+1];
t[i][0] = 0;
}
// Die unterste Reihe befuellen
for(int j=0; j < t[0].length; j++)
{
t[0][j] = 0;
}

//Berechne Matrix
// Vergleiche alle Werte aus A mit denen aus B
for(int i=1; i < t.length; i++)
{
for(int j=1; j < t[i].length; j++)
{
// Sollte A[i] in B enthalten sein, so muss es Teil der
// Loesung sein. Wir muessen hier die Indices transformieren,
// da wir bei i=1 Anfangen ('Leerzeile' der Tabelle wird ausge-
// lassen), aber alle Buchstaben der Ausgangsarrays durchlaufen
// wollen
if(A[i-1] == B[j-1])
{
t[i][j] = t[i-1][j-1]+1;
}
// A[i] ist nicht Teil der Loesung. Also nimm die beste bereits
// vorhandene optimale Loesung.
else
{
int max = t[i-1][j];
if(t[i][j-1] > max)
max = t[i][j-1];
t[i][j] = max;
}
}
}
return t[n][m];
}
}