1.

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

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 531 Compromise
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=472
*
* @author Bastian Hoecker
* @author Philipp Hauck Thalheim
* @version 1.0, 04/01/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.348
*/

public class Main {
//LCS Siehe Wiki
public static int[][] len(String cS[], String wS[]) {
int leng1 = cS.length + 1;
int leng2 = wS.length + 1;
int[][] res = new int[leng1][leng2];
for (int i = 1; i < leng1; i++) {
for (int j = 1; j < leng2; j++) {
if (cS[i - 1].equals(wS[j - 1])) {
res[i][j] = res[i - 1][j - 1] + 1;
} else
res[i][j] = Math.max(res[i][j - 1], res[i - 1][j]);
}
}
return res;
}
//LCS Ausgabe Siehe Wiki
public static String backTrack(int[][] laenge, String cS[], String wS[],
int i, int j) {
// int i = cS.length;
// int j = wS.length;
if (i == 0 || j == 0) {
return "";
} else if (cS[i - 1].equals(wS[j - 1])) {
return backTrack(laenge, cS, wS, i - 1, j - 1) + cS[i-1] + " ";
} else {
if (laenge[i][j - 1] > laenge[i - 1][j]) {
return backTrack(laenge, cS, wS, i, j - 1);
} else {
return backTrack(laenge, cS, wS, i - 1, j);
}
}
}

/**
* @param args
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (br.ready()) {
StringTokenizer st;
// 1.Satz
ArrayList<String> satz1 = new ArrayList<String>();
boolean finish = false;
st = new StringTokenizer(br.readLine());
do {
if (st.hasMoreElements()) {
String wort = st.nextToken();
if (wort.equals("#")) {
finish = true;
} else {
satz1.add(wort);
}
} else {
st = new StringTokenizer(br.readLine());
}
} while (!finish);

String[] satz1array = new String[satz1.size()];

for (int i = 0; i < satz1.size(); i++) {
satz1array[i] = satz1.get(i);

}

// 2.Satz
ArrayList<String> satz2 = new ArrayList<String>();
finish = false;
st = new StringTokenizer(br.readLine());
do {
if (st.hasMoreElements()) {
String wort = st.nextToken();
if (wort.equals("#")) {
finish = true;
} else {
satz2.add(wort);
}
} else {
st = new StringTokenizer(br.readLine());
}
} while (!finish);

String[] satz2array = new String[satz2.size()];

for (int i = 0; i < satz2.size(); i++) {
satz2array[i] = satz2.get(i);
}

System.out.println(backTrack(len(satz1array, satz2array), satz1array, satz2array,
satz1array.length, satz2array.length).trim());
}
}
}



--------------------------------------

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

}
}