一：LCS解析

首先看下什么是子序列？定義就不寫了，直接舉例一目了然。如對(duì)于字符串：“student”，那么su，sud，sudt等都是它的子序列。它可以是連續(xù)的也可以不連續(xù)出現(xiàn)，如果是連續(xù)的出現(xiàn)，比如stud，一般稱為子序列串，這里我們只討論子序列。

什么是公共子序列？很簡(jiǎn)單，有兩個(gè)字符串，如果包含共同的子序列，那么這個(gè)子序列就被稱為公共子序列了。如“student”和“shade”的公共子序列就有“s”或者“sd”或者“sde”等。而其中最長(zhǎng)的子序列就是所謂的最長(zhǎng)公共子序列(LCS)。當(dāng)然，最長(zhǎng)公共子序列也許不止一個(gè)，比如：“ABCBDAB”和“BDCABA”，它們的LCS為“BCBA”，“BCAB”，“BDAB”。知道了這些概念以后就是如何求LCS的問題了。

通常的算法就是動(dòng)態(tài)規(guī)劃(DP)。假設(shè)現(xiàn)在有兩個(gè)字符串序列：X={x1,x2,...xi...xm},Y={y1,y2,...yj...yn}。如果我們知道了X={x1,x2,...xi-1}和Y={y1,y2,...yj-1}的***公共子序列L，那么接下來我們可以按遞推的方法進(jìn)行求解：

1)如果xi==yj,那么{L,xi(或yj)}就是新的LCS了，其長(zhǎng)度也是len(L)+1。這個(gè)好理解，即序列{Xi,Yj}的***解是由{Xi-1,Yj-1}求得的。

2)如果xiyj,那么可以轉(zhuǎn)換為求兩種情況下的LCS。

A: X={x1,x2,...xi}與Y={y1,y2,...yj-1}的LCS，假設(shè)為L(zhǎng)1

B: X={x1,x2,...xi-1}與Y={y1,y2,...yj}的LCS，假設(shè)為L(zhǎng)2

那么xiyj時(shí)的LCS=max{L1,L2},即取***值。同樣，實(shí)際上序列{Xi,Yj-1}和{Xi-1,Yj}都可以由{Xi-1,Yj-1}的***解求得。

怎么樣，是不是覺得這種方法很熟悉？當(dāng)前問題的***解總是包含了一個(gè)同樣具有***解的子問題，這就是典型的DP求解方法。好了，直接給出上面文字描述解法中求LCS長(zhǎng)度的公式：

這里用一個(gè)二維數(shù)組存儲(chǔ)LCS的長(zhǎng)度信息，i，j分別表示兩個(gè)字符串序列的下標(biāo)值。這是求***公共子序列長(zhǎng)度的方法，如果要打印出***公共子序列怎么辦？我們還需要另外一個(gè)二維數(shù)組來保存求解過程中的路徑信息，方便***進(jìn)行路徑回溯，找到LCS。如果看著很含糊，我下面給出其實(shí)現(xiàn)過程。

二：DP實(shí)現(xiàn)

很多博文上面都有，基本上是用兩個(gè)二維數(shù)組c[m][n]和b[m][n]，一個(gè)用來存儲(chǔ)子字符串的LCS長(zhǎng)度，一個(gè)用來存儲(chǔ)路徑方向，然后回溯。

其中二維數(shù)組b[i][j]的取值為1或2或3，其中取值為1時(shí)說明此時(shí)xi=yj，c[i][j]=c[i-1][j-1]+1。如果將二維數(shù)組看成一個(gè)矩陣，那么此時(shí)代表了一個(gè)從左上角到右下角的路徑。如果取值為2，說明xi≠yj,且c[i][j]=c[i-1][j]，代表了一個(gè)從上到下的路徑，同理取值為3代表一個(gè)從左到右的路徑。

***我們可以根據(jù)c[m][n]的值知道***公共子序列的長(zhǎng)度。然后根據(jù)b[i][j]回溯，可以打印一條LCS。其中b[i][j]=1的坐標(biāo)點(diǎn)對(duì)應(yīng)的字符同時(shí)在兩個(gè)序列中出現(xiàn)，所以依次回溯這個(gè)二維數(shù)組就可以找到LCS了。這里給出實(shí)現(xiàn)代碼：

我們給出一個(gè)測(cè)試：

1     char str1[MAX_LEN] = "BADCDCBA"; 2     char str2[MAX_LEN] = "ABCDCDAB"; 3 
4     GetLCSLen(str1, str2, C, B, str1len+1, str2len+1); 5     TraceBack(str1, B, str1len+1, str2len+1);

詳細(xì)的代碼見文章結(jié)束處給出的鏈接。本測(cè)試output:BDCDB

問題：上面的方法中，我們沒有單獨(dú)考慮c[i-1][j]==c[i][j-1]的情況，所以在回溯的時(shí)候打印的字符只是其中一條***公共子序列，如果存在多條公共子序列的情況下。怎么解決？我們對(duì)b[i][j]二維數(shù)組的取值添加一種可能，等于4，這代表了我們說的這種多支情況，那么回溯的時(shí)候我們可以根據(jù)這個(gè)信息打印更多可能的選擇。這個(gè)過程就不寫代碼了，其實(shí)很簡(jiǎn)單，以下面的路徑回溯圖舉例，你從（8,8)點(diǎn)開始按b[i][j]的值指示的方向回溯，把所有的路徑遍歷一遍，如果是能達(dá)到起點(diǎn)（0,0)的路徑，就是LCS了，有多少條打印多少條?？墒?，

又出現(xiàn)問題了：你發(fā)現(xiàn)沒有，在回溯路徑的時(shí)候，如果采用一般的全搜索，會(huì)進(jìn)行了很多無用功。即重復(fù)了很多，且會(huì)遍歷了一些無效路徑，因?yàn)檫@些路徑最終不會(huì)到達(dá)終點(diǎn)(0,0)，比如節(jié)點(diǎn)(6,3),(7,2),(8,1)。因此加大算法復(fù)雜度和時(shí)間消耗。那么如何解決？看下面的這個(gè)方法，正式進(jìn)入本文正題。

 路徑回溯圖：

 加入狀態(tài)4后的狀態(tài)圖：

三：算法改進(jìn)

上面提到路徑回溯過程中，一般的方法就是遍歷所有可能的路徑，但是一些不可能構(gòu)成***公共子序列的跳躍點(diǎn)我們也會(huì)去計(jì)算。這里先解釋下什么叫跳躍點(diǎn)，就是導(dǎo)致公共子序列長(zhǎng)度發(fā)生變化的節(jié)點(diǎn)，即b[i][j]=1對(duì)應(yīng)的節(jié)點(diǎn)(i,j)。Ok，接下來的問題是，如何不去考慮這些無效跳躍點(diǎn)，降低算法復(fù)雜度？參考論文里提出了這樣一種方法：矩形搜索。

首先構(gòu)造兩個(gè)棧數(shù)據(jù)結(jié)構(gòu)store和print。故名思議，一個(gè)用來儲(chǔ)存節(jié)點(diǎn)，一個(gè)用來打印節(jié)點(diǎn)。棧的定義為：

 1 #define MAX_STACK_SIZE 1024
 2 typedef struct _Element  3 {  4     int nlcslen;  5     int nrow;  6     int ncolumn;  7 }Element;  8 typedef struct _Stack  9 { 10     int top; 11     Element data[MAX_STACK_SIZE]; 12 }Stack;

棧使用數(shù)組實(shí)現(xiàn)，并有一個(gè)指向頂點(diǎn)的下標(biāo)值top。為了初始化需要，先構(gòu)造了一個(gè)虛擬節(jié)點(diǎn)virtualnode，指向節(jié)點(diǎn)(m,n)的右下角，即(m+1,n+1),這個(gè)節(jié)點(diǎn)的LCS的長(zhǎng)度假設(shè)為***公共子序列長(zhǎng)度+1。將虛擬節(jié)點(diǎn)壓入棧store，然后然后執(zhí)行下面的算法：

1)棧store為空嗎？是的話退出。

2)否則從store棧頂彈出節(jié)點(diǎn)。

3)如果這個(gè)節(jié)點(diǎn)為邊界元素(行或列的小標(biāo)為1),則將此節(jié)點(diǎn)壓入棧print，打印棧print里面的所有節(jié)點(diǎn)(除virtualnode外)。查看此時(shí)store棧頂節(jié)點(diǎn)的LCS長(zhǎng)度，并以這個(gè)長(zhǎng)度為參考，彈出print棧里面所有LCS長(zhǎng)度小于等于這個(gè)參考值的節(jié)點(diǎn)，跳轉(zhuǎn)到第1步。

4)如果不是邊界元素，那么以該節(jié)點(diǎn)的左上節(jié)點(diǎn)(i-1,j-1)為出發(fā)點(diǎn)，沿著該出發(fā)點(diǎn)指示的方向，找到***個(gè)跳躍點(diǎn)e1(即b[i][j]==1的點(diǎn))。途中碰到分支節(jié)點(diǎn)(b[i][j]==4的點(diǎn))時(shí)，沿著其上節(jié)點(diǎn)繼續(xù)探索。

5)找到***個(gè)跳躍點(diǎn)以后，重新回到第4步的出發(fā)點(diǎn)，沿著該節(jié)點(diǎn)指示的方向，找到第二個(gè)跳躍點(diǎn)e2。途中碰到分支節(jié)點(diǎn)(b[i][j]==4的點(diǎn))時(shí)，沿著其左節(jié)點(diǎn)繼續(xù)探索

6)如果e1和e2節(jié)點(diǎn)為同一節(jié)點(diǎn)，將該節(jié)點(diǎn)壓入store棧，回到步驟1)。

7）如果不為同一節(jié)點(diǎn)，在e1和e2構(gòu)成的矩形范圍內(nèi)，搜索出所有的跳躍點(diǎn)，并全部壓入store棧，回到步驟1)。

不明白？不要緊，我們結(jié)合上面的矩陣圖一步步按照算法來，看看到底是如何計(jì)算的：

***步：壓入虛擬節(jié)點(diǎn)6(9,9)到棧store，這里6表示這個(gè)節(jié)點(diǎn)的LCS長(zhǎng)度，（9,9)表示坐標(biāo)值。 

第二步：store棧不為空，則彈出store棧頂，壓入print棧，這時(shí)候的兩個(gè)棧的狀態(tài)如下面的左圖。沿出發(fā)點(diǎn)(8,8)出發(fā)，這是個(gè)分支節(jié)點(diǎn)，因?yàn)閎[8][8]==4,所以選擇向上走，搜索到e1跳躍點(diǎn)(7,8)，搜索路徑為：(8,8)->(7,8)。然后回到(8,8)找e2點(diǎn)，這時(shí)選擇向左走，找到e2跳躍點(diǎn)(8,7)。這兩個(gè)跳躍點(diǎn)不同，所以以e1，e2為對(duì)角線方向圍成的矩形內(nèi)搜索所有跳躍點(diǎn)，這里只有e1,和e2本身兩個(gè)節(jié)點(diǎn)，然后將它們壓入棧store。此時(shí)兩個(gè)棧的狀態(tài)見下面的有圖。藍(lán)色底的節(jié)點(diǎn)表示有store棧彈出然后壓到print棧，綠色底表示新壓入到store棧的跳躍點(diǎn)，下面所有的圖都這樣表示。

第三步：彈出5(7,8)到print棧，搜索到新的兩跳躍節(jié)點(diǎn)。

第四步：

第五步：

第六步：

第七步：關(guān)鍵步驟來了，因?yàn)榇藭r(shí)從store棧彈出的節(jié)點(diǎn)是邊界元素1(1,2)，所以我們打印print棧的所有元素(紅色字體節(jié)點(diǎn))，而這些元素恰好構(gòu)成了一個(gè)最長(zhǎng)公共子序列(自己揣摩一下)。打印完了以后，我們要對(duì)print棧進(jìn)行清理，去除不需要的節(jié)點(diǎn)，按照步驟2，此時(shí)store棧頂節(jié)點(diǎn)的LCS為1，所以print棧中彈出的節(jié)點(diǎn)只有1(1,2)。彈完以后，print棧的狀態(tài)如圖所示。虛線框節(jié)點(diǎn)表示已彈出，下同。

第八步：繼續(xù)彈出store棧頂，發(fā)現(xiàn)又是邊界元素，繼續(xù)壓入print棧，打印print棧。清理print棧。

第九步：清理完后，繼續(xù)步驟2.

好了，下面的過程就是重復(fù)進(jìn)行上面的這些步驟了，自己動(dòng)手畫一下就一目了然了。

四：代碼實(shí)現(xiàn)

用c語言實(shí)現(xiàn)關(guān)鍵代碼：

同樣的測(cè)試，這種算法能打印出全部的最長(zhǎng)公共子序列。

五：總結(jié) 

該算法能將傳統(tǒng)算法的指數(shù)級(jí)復(fù)雜度降低到max{O(mn),O(ck)},k為***公共子序列的個(gè)數(shù)。詳細(xì)證明見論文。因?yàn)橛脙蓚€(gè)棧存儲(chǔ)了所有有效跳躍點(diǎn)，使得許多重復(fù)比較被忽略。棧的有序性也能巧妙的得到任意一條***公共子序列。

本算法的全部實(shí)現(xiàn)代碼下載路徑：http://pan.baidu.com/share/link?shareid=125428&uk=285541510

歡迎討論。

參考論文：

《利用矩陣搜索求所有最長(zhǎng)公共子序列的算法》，宮潔卿，安徽工程科技學(xué)院學(xué)報(bào)，vol23,No.4,Dec.,2008