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