大神的世界

網路上有許多相關資訊，但我太笨，都看不太懂 = = 

想了幾個小時後，似乎有點感覺了，趕緊來做個筆記 (如思考錯誤煩請糾正，感謝）

LCS ( longest comon subsequence)

O(n^2) 的就不說了 (那太簡單了...)

那 O(nlogn) 怎麼達成呢？

整體來說可分為 2 步

假設比較的字串有 A  B 二集合

A = abcbdab

B = bdcaba

第一步： 將 A 集合轉成數字集合  (姑且稱為 C)

第二步：求 C 集合的 LIS  ( longest increasing subsequence ) 

第一步：將 A 集合轉成數字集合  (姑且稱為 C)

方法： 將 A 集合的元素用 B 集合相同元素的位置代替 (大到小）

例如 (假設從 1 開始 => A[1] = a, B[1] = b)

a = {6, 4}    ,    b = {5, 1}    ,    c = {3}    ,    d = {2}

C = {6, 4,  5, 1, 3, 5, 1, 2, 6, 4, 5, 1}

問題1: 為什麼大到小呢？  

因為如果是小到大，相同字元會被取很多次  (e.g .  b = {1, 5}  , 取 1 5 為 LIS => bb)

問題2: 為什麼這樣做會轉變為 LIS 問題呢？

如果我們把相同字元括弧起來，C = { (6, 4),  (5, 1), (3), (5, 1), (2), (6, 4), (5, 1)}

那麼 LCS 要的就是找出最多括弧數，又因為 LIS 為遞增，所以每個括弧至多出現一次

第二步：求 C 集合的 LIS

方法：一個一個插入，跟最後一個比，大於 => 新增 ，小於 => 替換

C = {6, 4,  5, 1, 3, 5, 1, 2, 6, 4, 5, 1}

插入 6 : 6              (這好理解)

插入 4 : 4              (4 比 6 有潛力)

插入 5 : 4 5           (這好理解)

插入 1 : 1 5           (這...三小    C 的 1 在 5 後面ㄝ！！！ 因版面關係，請往下看解釋 （註1) )

插入 3 : 1 3           (一切盡在註1中)

插入 5 : 1 3 5        

插入 1 : 1 3 5        

插入 2 : 1 2 5        

插入 6 : 1 2 5 6     

插入 4 : 1 2 4 6     

插入 5 : 1 2 4 5     

插入 1 : 1 2 4 5     

這裡 1 2 4 5 僅僅說明 LCS 的長度為 4 

為什麼這樣做可以達到 O(nlogn) 呢？

因為插入時可採 binary search  或 segment tree

假設使用 binary search

則每次搜尋須耗時 O(logn)

搜尋 n 次，因此共 O(nlogn)

註1:

1 之所以替換掉 4 是因為 1 比 4 有潛力 ，但這樣做順序就亂了

(以下為個人理解)

為了維持順序，因此只有在新增時才更新  ( 輸出的內容)

1 換掉 4 代表 1 比 4 更有機會找到更長的遞增字串，但不代表一定能找到

例如 C = { 6, 4, 5, 1}

1 後面什麼都沒有

因此，輸出仍為 4 5 

但為什麼上面要改成 1 5 呢？

這裡我們可以假設有 2 個陣列，一個放輸出，一個暫存用

因此，輸出紀錄著 4 5 ，暫存的則改為 1 5

直到有新增時 （例如 1 5 7 ) 再寫到輸出

這時你可能會冒出另一個問題，4 5 7 不也可嗎

是的，因此結果可能不只一組

但如果新增後變成 ( 1 3 5 7 ) 則 4 開頭就不行 (畢竟 4 5 7 只有三個）

那要怎麼找出所有可能呢？

我們假設暫存的每一位置可紀錄多個數字

例如   

插入 6 :

6   

插入 4 :

6           (不急著拿掉，此時位置1 紀錄著兩個數字 6 和 4）

4              

插入 5 : (新增)

6         (因為 6 不能接 5， 所以掰掰）

4  5            

插入 1 :

6

4  5

1

插入 3 :

6

4 5          ( 只有在新增時才做修改)

1 3

插入 5 :  (新增)

6

4 5         ( 5 不能接 5 (要 increasing !!) ,  4 不能接 3 (先去 5 才知道 4 也得去除) )

1 3 5

插入 1 :

6

4 5       

1 3 5

1

插入 2 :

6

4 5       

1 3 5

1 2

插入 6 : (新增)

6

4 5       

1 3 5 6          ( 3 可保留 (1 3 5 6)  or (1 2 5 6) )

1 2

插入 4 :

6

4 5       

1 3 5 6         

1 2 4

插入 5 :

6

4 5       

1 3 5 6         

1 2 4 5

插入 1 :

6

4 5       

1 3 5 6         

1 2 4 5

1

所以 LIS 可能結果有

1 2 4 5

1 2 5 6

1 3 4 5

1 3 5 6

反推回 LCS

1 2 4 5    => bdab

1 2 5 6    => bdba

1 3 4 5    => bcab

1 3 5 6    => bcba

若有哪裡不清楚，或是想法錯誤還請多多賜教