以下是计算最长公共字符串的递归方法:
public int lcsLength(String x, String y)
{
char[] xc = x.toCharArray();
char[] yc = y.toCharArray();
return lcsLength(xc, xc.length - 1, yc, yc.length - 1, 0);
}
private int lcsLength(char[] xc, int xn, char[] yc, int yn, int currentCsLength)
{
if (xn < 0 || yn < 0) {
return currentCsLength;
}
if (xc[xn] == yc[yn]) {
return lcsLength(xc, xn - 1, yc, yn - 1, currentCsLength + 1);
}
else {
return max(currentCsLength,
max(
lcsLength(xc, xn - 1, yc, yn, 0),
lcsLength(xc, xn, yc, yn - 1, 0)));
}
}
使用此解决方案的缺点是,针对x和y的相同子字符串多次重新计算常见字符串,这会导致效率降低。
该解决方案使用记忆化技术
(memoization)来避免在递归中多次计算最长公共字符串。
public int lcsLength(String x, String y)
{
char[] xc = x.toCharArray();
char[] yc = y.toCharArray();
Integer[][] memoization = new Integer[xc.length][yc.length];
return lcsLength(xc, xc.length - 1, yc, yc.length - 1, memoization);
}
private int lcsLength(char[] xc, int xn, char[] yc, int yn, Integer[][] memoization)
{
if (xn < 0 || yn < 0) {
return 0;
}
if (memoization[xn][yn] == null) {
if (xc[xn] == yc[yn]) {
int i = xn - 1, j = yn - 1, length = 1;
while (i >= 0 && j >= 0 && xc[i] == yc[j]) {
i--;
j--;
length++;
}
memoization[xn][yn] = Math.max(length, lcsLength(xc, xn - length, yc, yn - length, memoization));
}
else {
memoization[xn][yn] = max(
lcsLength(xc, xn - 1, yc, yn, memoization),
lcsLength(xc, xn, yc, yn - 1, memoization));
}
}
return memoization[xn][yn];
}