1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 10192 Vacation
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1133
*
* @author Christoph Hausmann
* @version 0.1, 11/18/2009
*
* Method : LCS
* Status : Accepted
* Runtime: 0.148
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Vacation_10192 {
public static void main(String... args) throws NumberFormatException, IOException {
final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

for(int testCase = 1; testCase < Integer.MAX_VALUE; testCase++) {
final String firstSec = br.readLine();

if("#".equals(firstSec))
break;

final String secondSec = br.readLine();

System.out.printf("Case #%d: you can visit at most %d cities.\n",testCase,calcLCSLength(firstSec,secondSec));
}
}

private static int calcLCSLength(String firstSec, String secondSec) {
final int m = firstSec.length();
final int n = secondSec.length();

final int[][] c = new int[m+1][n+1];

for (int i = 1; i <= m; i++)
c[i][0] = 0;
for (int j = 0; j <= n; j++)
c[0][j] = 0;

for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (firstSec.charAt(i-1) == secondSec.charAt(j-1)) {
c[i][j] = c[i-1][j-1] + 1;
}
else if (c[i-1][j] >= c[i][j-1]) {
c[i][j] = c[i-1][j];
}
else {
c[i][j] = c[i][j-1];
}
}

return c[m][n];
}
}