Longest Common Subsequence:
Dynamic Programming

Longest Common Subsequence

Longest Common Subsequence(LCS),中文可以譯做「最長共同子序列」。它和LIS是不一樣的。LCS是兩個sequence,在各自所有的subsequence之中,一模一樣而且最長的那個subsequence。

s1:2 5 7 9 3 1 2
s2:3 5 3 2 8

以上例來看,s1和s2的LCS是5 3 2。這個例子恰恰好只有一個LCS,然而LCS有可能同時會有很多個的,就像LIS的情況一樣。

分割問題的方法

要找出LCS,就得先體會到其分割問題的精妙之處。這裡開始介紹分割問題的方法。

現在有兩個sequence分別為s1、s2,現在要找出s1和s2的LCS。先將s1的最後一個元素拆出來,這個元素稱做e1,而剩餘的部分稱做sub1好了。這裡以一道式子來簡單表示出剛剛的拆法,就是s1 = sub1 + e1。同樣的s2 = sub2 + e2。

要找出s1和s2的LCS,就等於是找出sub1 + e1和sub2 + e2的LCS。現在來觀察sub1、e1、sub2、e2與LCS的關係吧!首先將所有情況粗略的分做四種:一、e1是LCS的一部份,而e2不是;二、e2才是LCS的一部份,而e1不是;三、e1和e2都不是LCS的一部份;四、e1和e2都是LCS的一部份。

第一種情況。如果e1是LCS的一部份,而e2不是,那麼對e1來說,在sub2一定要能找到一個元素,和e1相同,才可能形成包含了e1的LCS。以另外一個方向去思考,則可以說e2是沒有用的元素,要找LCS只需要去找sub2就可以了。以上可以歸納一個結論:s1和s2的LCS,其實就是s1和sub2的LCS,可以把e2排擠掉。

第二種情況。和第一種情況類似,s1和s2的LCS,其實就是sub1和s2的LCS。

第三種情況。如果e1和e2都不是LCS的一部份,那麼直接找sub1和sub2的LCS就好啦!

第四種情況。如果e1和e2都是LCS的一部份,再者e1和e2都在最尾端,所以這種情況下,e1和e2是一定會相等的!而且e1亦會是LCS的最後一個元素。既然e1、e2都肯定是LCS的最後一個元素了,那麼要找剩下的部份,只需要從sub1和sub2著手即可,如同第三種情況一般。可以歸納出一個結論:s1和s2的LCS,必定是sub1和sub2的LCS在尾端加上e1(也是e2)。

總合以上分析,可以得到一個recurrence如下。

LCS(s1, s2) =
 { LCS(sub1, s2) or LCS (s1, sub2) or LCS(sub1, sub2) , when e1 != e2
 { LCS(sub1, sub2) + e1                               , when e1 == e2

經過焠鍊簡化之後,可以變成這樣。

LCS(s1, s2) =
 { max( LCS(sub1, s2), LCS(s1, sub2) ) , when e1 != e2
 { LCS(sub1, sub2) + e1                , when e1 == e2

然後再來考慮一下初始值要怎麼設定。一個簡單的想法是:當s1或s2是空的時候,必定找不到LCS。所以當s1或s2是空的時候,讓它們的LCS算出來是空集合就可以了。

以上就是求得LCS的方法了。這個方法逐步削減了最尾端的元素,將原問題縮小以求得解。事實上,將最尾端的字給拆開來的方法,是相當常見的一種手法。要是遇到了類似的題目,不妨也試著將尾端的字拆開來,慢慢分析所有情況來求得解。

計算LCS的長度

下面這段程式碼可以算出LCS的長度。

別忘了DP的精神!在這裡我們建立了一個二維陣列array,而array[i][j]代表著s1的第一個到第i個元素所形成的sequence,以及s2第一個到第j個元素所形成的sequence,這兩個sequence的LCS長度。而array[0][x]和array[x][0]則分別代表著第一個sequence為空的、第二個sequence為空的的情形,當然這些情形下LCS長度都是0,所以array[0][x]和array[x][0]的值也會是0。

找出一個LCS

可以從array陣列中找到LCS。觀察每一個e1 == e2的情況,因為e1 == e2的時候,也正是LCS增長的時候,故e1、e2是使LCS增長的元素。

要找到LCS,可以使用一個二維陣列,來記錄每一格的結果,是由哪一格而來。從最後的結果開始往回追溯,要是發現了某個array[i][j]是由array[i-1][j-1] + 1而得到的,便知道這個時候的e1、e2是使LCS增長的元素,此時印出s1[i]或者s2[j]其中一個就可以了。

找出所有的LCS

方才的程式碼可以找出一個LCS。但是若要找出所有的LCS呢?

我想這是可能做得到的,不過得先讓紀錄的方法更詳細一點才行。若是有一格的答案,可以由上方、左方或者左上方同時求得,那麼就要將這些同時求得的情形全部記錄起來。往回追溯的時候,就要將所有的情形都追溯一遍,便可求出所有可能的LCS。目前就我所知,似乎無法在線性時間內找出所有的LCS,一知半解,不再多提。

節省記憶體空間

此外,如果只想求出LCS的長度,而不需要求出LCS的話,那麼便有個節省記憶體空間的方法。計算array裡的某個格子的值,只需要上方、左方、左上方的格子。如果計算的順序是橫的一行一行計算,那麼其實只需要兩行的記憶體空間交錯使用就足夠了。

有不少題目可供練習。

UVa 111 531 10066 10192 10252 10405 10723

Longest Common Subsequence:
Hunt-Szymanski Algorithm

演算法

LCS問題其實可以化作LIS問題來解。從兩條序列中找出相同的數字,並記下其位置數對──位置數對的嚴格遞增LIS,即是兩序列的LCS。

index: 0 1 2 3 4 5 6 7 8 9
--------------------------
s1:    2 5 7 9 3 1 2
s2:    3 5 3 2 8

all matched index-pairs: (0,3) (1,1) (4,0) (4,2) (6,3)
lis: (1,1) (4,2) (6,3)
lcs:   5     3     2

Hunt-Szymanski Algorithm其實就只是把LCS問題化作LIS問題,然後用Robinson-Schensted-Knuth Algorithm來算LIS。實作時我們不必執著於找出數對,只要依序找出s2的元素在s1中的哪個位置就可以了(以位置數對的角度來看,這相當於先對位置數對的第二維度進行排序,再找LIS)。至於詳細過程,請自行參考下面程式碼。

index: 0 1 2 3 4 5 6 7 8 9
--------------------------
s1:    2 5 7 9 3 1 2
s2:    3 5 3 2 8

occur: 4 1 4 0 X
             6

lis: 1 4 6
lcs: 5 3 2

時間複雜度

先行判斷兩個序列的長度,將長度短的當作是s2,那麼時間複雜度就會是O(K * log(min(N,M))),其中K為位置數對的總數目,N和M分別是兩序列長度。也有人省略了min函數,直接寫成O(KlogN)

K最大可到N * M,遇到了極端的例子時,會跑得比用DP還慢。

計算LCS的長度(兩序列各自皆無重複元素)

計算LCS的長度

這裡再提供一個不使用binary search的程式碼,有時候會跑得比較快,各位可視情況採用之。

UVa 10635 10949

找出一個LCS、找出所有的LCS

可以參考LIS章節中的Robinson-Schensted-Knuth Algorithm。大家自己看著辦吧!

範例

這裡以s1 = abcaa、s2 = cbaa為例。大意為:依序看s2的每個元素,是不是能讓目前的common subsequece變得更長。

s2      各種   |  對應到s1        目前最好的
        位置   |  的情形          common subsequence
               |
cbaa    abcaa  |  abcaa
====================
讀入c   --c--  |  --c--           3
--------------------
讀入b   -b---  |  -b---           2
--------------------
讀入a   ----a  |  -b--a           2 5
        ---a-  |  -b-a-           2 4
        a----  |  a---- & -b-a-   1 4	// 同時紀錄到兩個
--------------------
讀入a   ----a  |  a---- & -b-aa   1 4 5
        ---a-  |                  1 4 5
        a----  |                  1 4 5
--------------------