32 lines
954 B
Java
32 lines
954 B
Java
public static String lcs(String a, String b) {
|
|
int[][] lengths = new int[a.length()+1][b.length()+1];
|
|
|
|
// row 0 and column 0 are initialized to 0 already
|
|
|
|
for (int i = 0; i < a.length(); i++)
|
|
for (int j = 0; j < b.length(); j++)
|
|
if (a.charAt(i) == b.charAt(j))
|
|
lengths[i+1][j+1] = lengths[i][j] + 1;
|
|
else
|
|
lengths[i+1][j+1] =
|
|
Math.max(lengths[i+1][j], lengths[i][j+1]);
|
|
|
|
// read the substring out from the matrix
|
|
StringBuffer sb = new StringBuffer();
|
|
for (int x = a.length(), y = b.length();
|
|
x != 0 && y != 0; ) {
|
|
if (lengths[x][y] == lengths[x-1][y])
|
|
x--;
|
|
else if (lengths[x][y] == lengths[x][y-1])
|
|
y--;
|
|
else {
|
|
assert a.charAt(x-1) == b.charAt(y-1);
|
|
sb.append(a.charAt(x-1));
|
|
x--;
|
|
y--;
|
|
}
|
|
}
|
|
|
|
return sb.reverse().toString();
|
|
}
|