【转】最长公共子序列（LCS），求LCS长度和打印输出LCS

求LCS的长度，Java版本：

public static int LCS(int[]a,int[] b)

{

    int [][]c=new int[a.length+1][b.length+1];

    for(int i=1;i<=a.length;i++)

    {

        for(int j=1;j<=b.length;j++)

        {

            if(a[i-1]==b[j-1])

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

            else

                c[i][j]=Math.max(c[i-1][j], c[i][j-1]);

        }

    }

    return c[a.length][b.length];

}

推导过程和递推公式：

主要参考：

算法导论-----最长公共子序列LCS（动态规划）

其中，理解递推公式之后，要理解代码中的c数组 是怎么变化的（结合下面这个图的过程，过程为：每一行，从左到右）

该文章中，打印LCS的过程（C语言，包括递归和非递归版本）也容易看懂。

Java版本可以参考：最长公共子串、最长公共子序列的Java实现与NLP应用

但打印这一部分看得不太懂：

int i = 0, j = 0;

while (i < substringLength1 && j < substringLength2)

{

     if (str1[i] == str2[j])

      {

            System.out.print(str1[i]);

            i++;

            j++;

      }

       else if (opt[i + 1][j] >= opt[i][j + 1])

             i++;

        else

              j++;

}

System.out.println();

不如看上一篇C语言的打印，递归和非递归都很清楚