1等孵、定義
最長公共子序列，英文縮寫為LCS（Longest Common Subsequence）矫付。其定義是凯沪，一個(gè)序列 S ，如果分別是兩個(gè)或多個(gè)已知序列的子序列买优，且是所有符合此條件序列中最長的妨马，則 S 稱為已知序列的最長公共子序列。而最長公共子串(要求連續(xù))和最長公共子序列是不同的杀赢。（百度百科）
2烘跺、最長公共子序列
2.1 狀態(tài)方程的定義
設(shè)現(xiàn)在用兩個(gè)字符串X和Y，用C[i][j]表示
X的前i個(gè)字符和Y的前j個(gè)字符中最長公共子序列的長度
2.3 狀態(tài)轉(zhuǎn)移方程的定義
由定義脂崔，有
C[0][j]=0
C[i][0]=0
而對(duì)于C[i][j]的大小與當(dāng)前字符有關(guān)滤淳，如果當(dāng)前字符相同，即 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]
依次計(jì)算娇钱，得到最大長度伤柄。當(dāng)然，如果要得出最終的字符串可以使用標(biāo)記空間文搂，最后利用標(biāo)記空間（B[i][j]）將字符串輸出适刀。
2.3 源程序
程序中C[][]的長度增加了1，是為了能夠?qū)⒂凶址L度為0時(shí)的公共子序列的長度儲(chǔ)存下來煤蹭，所以程序中用C[i+1][j+1]來表示狀態(tài)方程的定義笔喉。
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);
}
}
實(shí)驗(yàn)結(jié)果
最長公共子序列的長度為4
BCBA
