Public class LCSProblem
{
  /**
   *初始化
  **/
  publicstaticvoidmain(String[]args)
  {
    String[]x={"","A","B","C","B","D","A","B"};   //初始化序列X；
    String[]y={"","B","D","C","A","B","A"};       //初始化序列Y；
    int[][]b=getLength(x,y);                      //将两个序列的最长公共序列的长度值记录在二维数组b中；
    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];         //初始化数组b，记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。
    int[][]c=new int[x.length][y.length];         //初始化数组c，记录X[i]与Y[j] 的LCS 的长度。
    //填充矩阵
    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;   //1代表指向左上方的箭头
        }
        elseif(c[i-1][j]>=c[i][j-1])
        {
          c[i][j]=c[i-1][j];
          b[i][j]=0;   //0代表指向上方的箭头
        }
        else
        {
          c[i][j]=c[i][j-1];
          b[i][j]=-1;  //-1代表指向左方的箭头
        }
      }
    }
    Return b;
  }

/**
 *输出最长公共子序列
**/
void PrintLCS(int b[][], char x, int i, int j)
{
    if(i == 0 || j == 0)         //两个字符串中任意一个长度为0；
        return  null;
    if(b[i][j] == 1)                  //箭头指向左上方
    {
        PrintLCS(b, x, i-1, j-1);
        printf("%c ", x[i-1]);     //输出两个序列相同的字符
    }
    else if(b[i][j] == 0)      //箭头指向上方
        PrintLCS(b, x, i-1, j);
    else                                           //箭头指向左方
        PrintLCS(b, x, i, j-1);
}