1. 

/**
* FWP, Ausgew¤hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: 531 - Compromise
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=7&problem=472&mosmsg=Submission+received+with+ID+8012946
*
* @author Evgeni Pavlidis
* @version 1.0, 06/02/2010
*
* Method : DP - LCS
* Status : Accepted
* Runtime: 0.520
*/

import java.io.*;
import java.util.*;

class Main {

private static int[][] lcs;
private static String[] a,b;
private static List<String> result = new ArrayList<String>();

static void lcs()
{
int n = a.length;
int m = b.length;

lcs = new int[n+1][m+1];

for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(a[i-1].equals(b[j-1]))
lcs[i][j] = lcs[i-1][j-1] + 1;
else
lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
}

static void constructLCS(int i, int j)
{
if(i == 0 || j == 0)
return;

if(a[i-1].equals(b[j-1]))
{
if(!a[i-1].equals(""))
result.add(a[i-1]);
constructLCS(i-1,j-1);
}
else if(lcs[i-1][j] > lcs[i][j-1])
constructLCS(i-1,j);
else
constructLCS(i,j-1);
}

public static void main(String...args)
{
Scanner sc = new Scanner(System.in);
sc.useDelimiter("#");
String input;

while(sc.hasNext())
{
input = sc.next().toLowerCase();
a = input.split("[^a-z1-9]+");

if(!sc.hasNext())
break;

input = sc.next().toLowerCase();
b = input.split("[^a-z1-9]+");


result.clear();
lcs();
constructLCS(a.length,b.length);
Collections.reverse(result);

if(result.size() > 0)
System.out.println(result.toString().replaceAll("\\[|\\]|,", ""));
}

}
}