1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 531 - Compromise
* Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=472
*
* @author Manuel Hager
* @version 1.0, 12/01/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.588
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main
{
private static List<String> text1 = new ArrayList<String>();
private static List<String> text2 = new ArrayList<String>();
private static List<String> resultList = new ArrayList<String>();
private static boolean isFirstText = true;

public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

for(String line = reader.readLine(); line != null; line = reader.readLine()) {
if(!line.equals("#")) {
for(String word : line.split("\\s+")) {
(isFirstText? text1 : text2).add(word);
}
}
else {
if(!isFirstText) {
resultList.clear();
lcsResult();
text1.clear(); text2.clear();
}
isFirstText = !isFirstText;
}
}
reader.close();
}

private static void lcsResult()
{
int strLen1 = text1.size();
int strLen2 = text2.size();
int[][] c = new int[strLen1 +1][strLen2 +1];

for(int i = 1; i <= strLen1; i++) {
for(int j = 1; j <= strLen2; j++) {
if(text1.get(i -1).equals(text2.get(j -1)))
c[i][j] = c[i -1][j -1] +1;
else
c[i][j] = Math.max(c[i-1][j], c[i][j-1]);
}
}

while(strLen1 > 0 || strLen2 > 0) {
if(strLen1 > 0 && strLen2 > 0 && text1.get(strLen1 -1).equals(text2.get(strLen2 - 1))) {
resultList.add(text1.get(strLen1 -1));
strLen1--;
strLen2--;
}
else if(strLen1 > 0 && c[strLen1][strLen2] == c[strLen1 -1][strLen2]) {
strLen1--;
}
else if(strLen2 > 0 && c[strLen1][strLen2] == c[strLen1][strLen2 -1]) {
strLen2--;
}
}

for(int i = resultList.size() - 1; i >= 1; i--) {
System.out.print(resultList.get(i) + " ");
}
System.out.println(resultList.get(0));
}
}


2.

/**
* 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("\\[|\\]|,", ""));
}

}
}