过程的运行时间为O（m+n），因为每次递归调用i和j至少有一个会减少1。

java代码实现

public class algorithm {

public static void main(String[] args) {

char[] X = "BDCABA".toCharArray();

char[] Y = "ABCBDAB".toCharArray();

lcs(X, Y);

}

public static void lcs(char[] X,char[] Y){//求最长公共子序列长度

int m = X.length,n = Y.length;

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

int[][] b = new int[m + 1][n + 1];

for (int i = 0;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 (X[i - 1] == Y[j - 1]){

c[i][j] = c[i - 1][j - 1] + 1;

b[i][j] = 7;

}else if (c[i - 1][j] >= c[i][j -1]){

c[i][j] = c[i - 1][j];

b[i][j] = 8;

}else{

c[i][j] = c[i][j - 1];

b[i][j] = 4;

}

}

}

System.out.println("最长公共子序列的长度为:" + c[m][n]);

System.out.println("其中的一个最长公共子序列为:");

lcs_list(b, X, m, n);

}

public static void lcs_list(int[][] b,char[] X,int m,int n){//求最长公共子序列

int i = m,j = n;

if (i == 0 || j == 0)

return ;

if (b[i][j] == 7){

lcs_list(b, X, i - 1, j - 1);

System.out.print(X[i - 1]);

}else if (b[i][j] == 8){

lcs_list(b, X, i - 1, j);

}else{

lcs_list(b, X, i, j - 1);

}

}

}