给定两个序列,求出它们的最长公共子序列。 如:序列X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a},则X和Y的最长公共子序列为{b,c,b,a}
设两个序列分别是X={x1,x2……,xm},Y={y1,y2……,yn},它们的最长公共子序列为Z={z1,z2,……,zk}。
private int[][] c;
private int[][] s;
void LCSLength(String a, String b){
// x和y的最前端分别加上0
char[] x = ("0"+a).toCharArray();
char[] y = ("0"+b).toCharArray();
c = new int[x.length][y.length];
s = new int[x.length][y.length];
// 初始化c、s
for( int i=0; i<x.length; i++ ){
c[i][0] = 0;
}
for( int i=0; i<y.length; i++ ){
c[0][i] = 0;
}
// 从上到下、从左到右填充c、s数组
for( int i=1; i<x.length; i++ ){
for( int j=1; j<y.length; j++ ){
if( x[i]==y[j] ){
c[i][j] = c[i-1][j-1]+1;
s[i][j] = 1;
}
else if ( c[i-1][j] >= c[i][j-1] ){
c[i][j] = c[i-1][j];
s[i][j] = 2;
}
else {
c[i][j] = c[i][j-1];
s[i][j] = 3;
}
}
}
}
StringBuilder sb = new StringBuilder();
void CLCS( int i, int j ){
if ( i==0 || j==0 ) return;
if ( s[i][j]==1 ) {
CLCS( i-1,j-1 );
sb.append( x[i] ); // 为了让公共子序列正序输出,因此需要在递归调用之后将x[i]添加至sb
}
else if ( s[i][j]==2 ){
CLCS( i-1,j );
}
else {
CLCS( i,j-1 );
}
}