1、定义

最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的。（百度百科）

2、最长公共子序列

2.1 状态方程的定义

设现在用两个字符串X和Y，用C[i][j]表示X的前i个字符和Y的前j个字符中最长公共子序列的长度

2.3 状态转移方程的定义

由定义，有

C[0][j]=0
C[i][0]=0

而对于C[i][j]的大小与当前字符有关，如果当前字符相同，即 X[i]==Y[j] ,那么

C[i][j] = C[i-1][j-1] + 1

如果X[i]!=Y[j],那么判断 C[i-1][j]>=C[i][j-1],如果成立，则有

C[i][j] = C[i-1][j]

否则

C[i][j] = C[i][j-1]

依次计算，得到最大长度。当然，如果要得出最终的字符串可以使用标记空间，最后利用标记空间（B[i][j]）将字符串输出。

2.3 源程序

程序中C[][]的长度增加了1，是为了能够将有字符串长度为0时的公共子序列的长度储存下来，所以程序中用C[i+1][j+1]来表示状态方程的定义。

package Algorithm;

public class LCS {
  private static String X = "ABCBDAB", Y = "BDCABA";

  public static void Sequence(char[][] B, int i, int j) {
    if (i == -1 || j == -1) return;
    if (B[i][j] == '\\') {
      Sequence(B, i - 1, j - 1);
      System.out.print(X.charAt(i));
    } else if (B[i][j] == '|') Sequence(B, i - 1, j);
    else Sequence(B, i, j - 1);
  }

  public static void main(String[] args) {
    int C[][] = new int[X.length() + 1][Y.length() + 1];
    char B[][] = new char[X.length()][Y.length()];
    for (int i = 0; i <= X.length(); ++i) C[i][0] = 0;
    for (int j = 0; j <= Y.length(); ++j) C[0][j] = 0;

    for (int i = 0; i < X.length(); ++i) {
      for (int j = 0; j < Y.length(); ++j) {
        if (X.charAt(i) == Y.charAt(j)) {
          C[i + 1][j + 1] = C[i][j] + 1;
          B[i][j] = '\\';
        } else if (C[i][j + 1] >= C[i + 1][j]) {
          C[i + 1][j + 1] = C[i][j + 1];
          B[i][j] = '|';
        } else {
          C[i + 1][j + 1] = C[i + 1][j];
          B[i][j] = '-';
        }
      }
    }
    System.out.println("最长公共子序列的长度为" + C[X.length()][Y.length()]);

    //输出其中一种可能的情况
    Sequence(B, X.length() - 1, Y.length() - 1);
  }
}

实验结果

最长公共子序列的长度为4
BCBA