求最长公共子序列

/**
 * 引进一个二维数组c[][]，用c[i][j]记录X[i]与Y[j] 的LCS 的长度，
 * b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。
 * 我们是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。
 * 此时我们根据X[i] = Y[j]还是X[i] != Y[j]，就可以计算出c[i][j]。
 */
public class LCSProblem   
{  
    public static void main(String[] args)  
    {  
        String[] x = {"","a" , "b" , "c" , "b" , "d" , "a" , "b","q","w"};
        String[] y = {"","b" , "d" , "c" , "a" , "b" , "a"};
        int[][] b = getLength(x, y);
          
        Display(b, x, x.length-1, y.length-1);  
    }  
      
    public static int[][] getLength(String[] x, String[] y)  
    {  
        int[][] b = new int[x.length][y.length];  //记录c[i][j]是通过哪一个子问题的值求得的
        int[][] c = new int[x.length][y.length]; //记录X[i]与Y[j] 的LCS 的长度
        for(int i = 0; i < x.length; i++)
            c[i][0] = 0;
        for(int j = 1; j < y.length; j++)
            c[0][j] = 0;
        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;  
                    b[i][j] = 1;  
                }  
                else if(c[i-1][j] >= c[i][j-1])  
                {  
                    c[i][j] = c[i-1][j];  
                    b[i][j] = 0;  
                }  
                else  
                {  
                    c[i][j] = c[i][j-1];  
                    b[i][j] = -1;  
                }  
            }  
        }     
          
        return b;  
    }  
      
    public static void Display(int[][] b, String[] x, int i, int j)  
    {  
        if(i == 0 || j == 0)  
            return;  
          
        if(b[i][j] == 1)  
        {  
            Display(b, x, i-1, j-1);  
            System.out.print(x[i] + " ");  
        }  
        else if(b[i][j] == 0)  
        {  
            Display(b, x, i-1, j);  
        }  
        else if(b[i][j] == -1)  
        {  
            Display(b, x, i, j-1);  
        }  
    }
}