原文在這里 http://blog.csdn.net/dq_dm/article/details/45043689
1、LCS的基本概念
子序列：一個(gè)序列X任意刪除若干個(gè)字符得到新序列Z，則Z叫做X的子序列。例如Z=是X=的子序列坚洽，相當(dāng)于刪除A缀皱、B、A轮纫。
公共子序列：給定兩個(gè)序列X和Y趁仙，如果Z既是X的子序列洪添，也是Y的子序列，我們稱(chēng)它為X和Y的公共子序列雀费。公共子序列可能不唯一干奢。例如是X=和Y=的一個(gè)公共子序列。
最長(zhǎng)公共子序列：Longest Common Subsequence盏袄，簡(jiǎn)稱(chēng)LCS忿峻。如果Z是X和Y的公共子序列，且是最長(zhǎng)的那個(gè)辕羽，則稱(chēng)Z是X和Y的最長(zhǎng)公共子序列逛尚。例如是X=和Y=的一個(gè)最長(zhǎng)公共子序列，也是刁愿。它也可能不唯一绰寞。
注：(1)為了簡(jiǎn)便，上面我們討論的都是兩個(gè)序列的公共子序列铣口，當(dāng)然滤钱，也可以是3個(gè)、4個(gè)等等枷踏。(2)它和最長(zhǎng)公共子串是有區(qū)別的菩暗，最長(zhǎng)公共子串要求連續(xù)。
求兩個(gè)序列中最長(zhǎng)的公共子序列算法，廣泛的應(yīng)用在圖形相似處理旷坦、媒體流的相似比較掏熬、計(jì)算生物學(xué)方面。生物學(xué)家常常利用該算法進(jìn)行基因序列比對(duì)秒梅，由此推測(cè)序列的結(jié)構(gòu)旗芬、功能和演化過(guò)程。
LCS可以描述兩段文字之間的“相似度”捆蜀，即它們的雷同程度疮丛，從而能夠用來(lái)辨別抄襲幔嫂。另一方面，對(duì)一段文字進(jìn)行修改之后誊薄，計(jì)算改動(dòng)前后文字的最長(zhǎng)公共子序列履恩，將除此子序列外的部分提取出來(lái)，這種方法判斷修改的部分呢蔫，往往十分準(zhǔn)確切心。簡(jiǎn)而言之，百度知道片吊、百度百科都用得上绽昏。
1）假定序列X俏脊，Y的長(zhǎng)度分別為m全谤，n；
2）X的一個(gè)子序列即下標(biāo)序列{1, 2, …, m}的嚴(yán)格遞增子序列爷贫，因此啼县，X共有2m個(gè)不同子序列；同理沸久，Y有2n個(gè)不同子序列季眷，從而窮舉搜索法需要指數(shù)時(shí)間O(2m .2n)；
3）對(duì)X的每一個(gè)子序列卷胯，檢查它是否也是Y的子序列子刮，從而確定它是否為X和Y的公共子序列，并且在檢查過(guò)程中選出最長(zhǎng)的公共子序列窑睁；
顯然挺峡，不可取。
在這里先說(shuō)些前綴的概念橱赠，給定一個(gè)序列X=，對(duì)i=0,1,…,m箫津，定義X的第i前綴為Xi=狭姨。例如，若X=苏遥，則X4=饼拍，X0為空串。
令X=和Y=為兩個(gè)序列田炭，Z=為X和Y的任意LCS师抄。
1）如果xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的一個(gè)LCS教硫。也就是
例如：
2）如果xm≠yn叨吮，那么zk≠xm意味著Z是xm-1和Y的一個(gè)LCS辆布。
也就是，LCS(Xm,Yn)=LCS(Xm-1,Yn)茶鉴。
3）如果xm≠yn锋玲，那么zk≠yn意味著Z是X和Yn-1的一個(gè)LCS。也就是蛤铜，LCS(Xm,Yn)=LCS(Xm,Yn-1)嫩絮。
例如：
顯然围肥，是動(dòng)態(tài)規(guī)劃問(wèn)題剿干。
引進(jìn)一個(gè)二維數(shù)組c[0..m,0..n]穆刻，用c[i,j]記錄序列Xi與Yj的LCS的長(zhǎng)度置尔。
引進(jìn)一個(gè)二維數(shù)組b[1..m,1..n]，b[i,j]標(biāo)記c[i,j]是由哪一個(gè)子問(wèn)題的解求得的氢伟，以決定搜索的方向榜轿。即c[i,j]是由c[i-1,j-1]+1或者c[i-1,j]或者c[i,j-1]的哪一個(gè)得到的。取值范圍為L(zhǎng)eftTop朵锣、Top谬盐、Left三種情況。
舉例：
X=< A诚些，B飞傀，C，B诬烹，D砸烦，A，B >绞吁，Y=< B幢痘，D，C家破，A颜说，B，A >
注：
1）第一行员舵、第一列都為0脑沿；
2）按行主次序計(jì)算表項(xiàng)。
3）第i行和第j列的方格包含了c[i,j]的值和b[i-1,j]記錄的箭頭马僻；
4）右下角的項(xiàng)c[7,6]中的4即為X和Y的一個(gè)LCS的長(zhǎng)度；
5）為了構(gòu)造LCS的元素注服，從右下角開(kāi)始沿著b[i,j]的箭頭前進(jìn)即可韭邓，如圖中陰影方格序列措近。陰影序列中每個(gè)“? ”對(duì)應(yīng)的表項(xiàng)表示xi=yj是LCS的一個(gè)元素。此時(shí)得到的是BCBA女淑，逆序輸出瞭郑，即LCS是。
過(guò)程的運(yùn)行時(shí)間為O(mn)鸭你，因?yàn)槊總€(gè)表項(xiàng)的計(jì)算時(shí)間為O（1）屈张。
開(kāi)始的i、j分別是X和Y的長(zhǎng)度袱巨。
過(guò)程的運(yùn)行時(shí)間為O（m+n）阁谆，因?yàn)槊看芜f歸調(diào)用i和j至少有一個(gè)會(huì)減少1。
java代碼實(shí)現(xiàn)
public class algorithm {
public static void main(String[] args) {
char[] X = "BDCABA".toCharArray();
char[] Y = "ABCBDAB".toCharArray();
lcs(X, Y);
}
public static void lcs(char[] X,char[] Y){//求最長(zhǎng)公共子序列長(zhǎng)度
int m = X.length,n = Y.length;
int[][] c = new int[m + 1][n + 1];
int[][] b = new int[m + 1][n + 1];
for (int i = 0;i <= m;i++)
c[i][0] = 0;
for (int j = 0;j <= n;j++)
c[0][j] = 0;
for (int i = 1;i <= m;i++){
for (int j = 1;j <= n;j++){
if (X[i - 1] == Y[j - 1]){
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 7;
}else if (c[i - 1][j] >= c[i][j -1]){
c[i][j] = c[i - 1][j];
b[i][j] = 8;
}else{
c[i][j] = c[i][j - 1];
b[i][j] = 4;
}
}
}
System.out.println("最長(zhǎng)公共子序列的長(zhǎng)度為:" + c[m][n]);
System.out.println("其中的一個(gè)最長(zhǎng)公共子序列為:");
lcs_list(b, X, m, n);
}
public static void lcs_list(int[][] b,char[] X,int m,int n){//求最長(zhǎng)公共子序列
int i = m,j = n;
if (i == 0 || j == 0)
return ;
if (b[i][j] == 7){
lcs_list(b, X, i - 1, j - 1);
System.out.print(X[i - 1]);
}else if (b[i][j] == 8){
lcs_list(b, X, i - 1, j);
}else{
lcs_list(b, X, i, j - 1);
}
}
}
