演算法知識 - Longest Common Subsequence 最長共同子序列(時間複雜度 O(nlogn))

Longest Common Subsequence 介紹

以下簡稱 LCS，在兩個序列中找出最長子序列的問題，序列是甚麼？只要順序一致即可，舉例：

• people
• apple

• 這兩個的 LCS 就是 pple，長度為 4，子序列為 pple。

看懂了嗎？ pple 在前面兩個字串中順序都是保持一致的。
被廣泛應用於生物資訊學與版本控制。

這裡我們是教導時間複雜度為 \(O(n \log n)\) 的寫法，而非 \(O(n^2)\) 的寫法

Longest Increasing Subsequence 最長遞增子序列，以下簡稱 LIS

Longest Common Subsequence 原理

先將 A 字串的值逆向輸入到一個 map<char,vector<int>>裡面，再根據 B 字串的字元依序將 map<char,vector<int>> 取出，之後做 LIS 遞增。

如果不懂 LIS 是甚麼可以先看

QUESTION: 太驚人了！ 為甚麼可以用 \(O(n \log n )\) 去解？

因為這世界天才太多了。正解

開玩笑的，還記得 (\ O(n^2))\ 的解法怎麼解嗎？是用動態規劃，可是他是不是有點浪費效率，因為她只有在 A[i] == B[i]，才會增加長度，剩下時間都是在延續之前的狀態，我們從這裡進行補強。

我們只要把 A 字串的每個字元的 index 做紀錄，並將同個字元出現的多個位置放入 vector，放入的順序是大到小，再根據 B 字串的每個字元對應同字元的 vector，在做 LIS 即可，這樣我們就減少了此情況 A[i] != B[i]。

Longest Common Subsequence 說明與舉例

舉例

先舉個例子，以免被說是騙人XD。

String A = “abdba”
String B = “dbaaba”

對應 A 字串的每個字元的 index 做紀錄，並將同個字元出現的多個位置放入 vector，字串 index 從 0 開始，記住是逆序，如下：

a(4,0) b(3,1) d(2)

再來，我們根據根據 B 字串的每個字元對應同字元的 vector，產生序列，於是就變成

index	0	1	2	3	4	5	6	7	8	9	10
value	2	3	1	4	0	4	0	3	1	4	0
char	d	b		a		a		b		a

看懂了？對吧！

而此時，這裡的 LIS 最大長度為 3，其中一種方式為 2 3 4，但這裡也只有這種XD，記住，在其他情況下 LCS 不只有一種表達方式。

且 d 的 vector 有 2、b 的 vector 有 3、a 的 vector 有 4，剛好能夠組成 dba，符合答案。

QUESTION: 那為甚麼要是逆序？

很簡單，為了要避免重複判斷，一樣用剛剛的例子如下，那 vector會變成。

a(0,4) b(1,3) d(2)

index	0	1	2	3	4	5	6	7	8	9	10
value	2	1	3	0	4	0	4	1	3	0	4
char	d	b		a		a		b		a

這樣出來的最長長度為 4，其中一種方式為 0 1 3 4，但這裡組成的字串會變成 dbba，是不是中間的 b 被重複算到了，因為 LIS 是遞增，如果我們的 vector 也是遞增排序時，則中間的每一個 vector 的 element 都會被我們選中長度會被無限放大，因此在 vector 時要是逆序的元素。

OK, 現在問題被我們解決成是 LIS 了，那我們就來做吧！

關於 LIS 的部分就先去看大衞的筆記即可。

LCS 實作與說明

P.S. 這裡的 string index 由 1 開始方便編寫程式碼，主要方便用來 LIS 如果要更改 cur 成 0 時會造成 t[-1] ，只需要在 string = "$" + string，即可達到此功效

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define N 120
using namespace std;
int n ;
string strA , strB ;
int t[N*N] , d[N*N] , num[N*N] ; //t and d 是 LIS 要用到 
// d 用來記住 LIS 中此數字的前一個數字
// t 當前 LIS 的數列位置
// num 則是我們根據 strB 的字元生成數列，用來找出最長 LIS 長度 
map<char,vector<int>> dict ; //記住每個字串出現的 index 位置

int bs(int l , int r , int v ){ //binary search 
    int m ;
    while(r>l){
        m = (l+r) /2 ;
        if(num[v] > num[t[m]]) l = m+1 ;
        else if (num[v] < num[t[m]]) r = m ;
        else return m ;
    }
    return r ;
}

int lcs(){
    dict.clear() ; //先將 dict 先清空
    for(int i = strA.length()-1 ; i > 0 ; i--) dict[strA[i]].push_back(i) ;
    // 將每個字串的位置紀錄並放入 vector 中，請記住 i = strA.length() -1 才可以達到逆續效果

    int k = 0 ; //紀錄生成數列的長度的最長長度
    for(int i = 1 ; i < strB.length() ; i++){ // 依據 strB 的每個字元來生成數列
        for(int j = 0 ; j < dict[strB[i]].size() ; j++) 
        //將此字元在 strA 出現的位置放入數列
            num[++k] = dict[strB[i]][j] ;
    }
    if(k==0) return 0 ; //如果 k = 0 就表示他們沒有共同字元都沒有於是就直接輸出 0

    d[1] = -1 , t[1] = 1 ; //LIS init
    int len = 1, cur ; // len 由於前面已經把 LCS = 0 的機會排除，於是這裡則從 1 開始

    // 標準的 LIS 作法，不斷嘗試將 LCS 生長
    for(int i = 1 ; i <= k ; i++ ){
        if(num[i] > num[t[len]]) t[++len] = i , d[i] = t[len-1] ;
        else{
            cur = bs(1,len,i);
            t[cur] = i ;
            d[i] = t[cur-1];
        }

        //debug
//        for(int i = 1 ; i <= k ; i++)
//            cout << num[t[i]] << ' ' ;
//        cout << '\n' ;
    }
    return len ;

}

LCS 應用

我在學習此演算法的過程中如果有題目讓我應用到此演算法我則收錄在此，連結則是我的詳解如果想要去看題目的就搜尋一下吧！

• UVa10192 - Vacation (LCS)
• UVa1207 - AGTC (LCS) - 這裡採用的是 \(O(n^2)\) 做法。

參考連結

lcs 最长公共子序列 O(nlogn)算法

心得

Binary Search 好難，嗚嗚，太過於依賴 C++ STL 函數，原本心血來潮想說要來寫一遍 Binary Search 沒想到花了 6 小時都還沒寫出來(完全是透過心想)，原本想說這麼簡單的演算法我應該連紙筆都不用吧！沒想到還是需要，嗚嗚，我腦袋的 RAM 是不是連 1 KB 都沒有呀，好討厭喔。

不過又學了一個新演算法，用於改進 LCS 的時間複雜度其實感覺蠻開心的呢！

LCS 無註解程式碼

這裡則放置沒有註解的程式碼，如果讀者想要複製就從這裡進行複製吧！

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define N 120
using namespace std;
int n ;
string strA , strB ;
int t[N*N] , d[N*N] , num[N*N] ; 

map<char,vector<int>> dict ; 

int bs(int l , int r , int v ){ 
    int m ;
    while(r>l){
        m = (l+r) /2 ;
        if(num[v] > num[t[m]]) l = m+1 ;
        else if (num[v] < num[t[m]]) r = m ;
        else return m ;
    }
    return r ;
}

int lcs(){
    dict.clear() ; 
    for(int i = strA.length()-1 ; i > 0 ; i--) dict[strA[i]].push_back(i) ;

    int k = 0 ;
    for(int i = 1 ; i < strB.length() ; i++){ 
        for(int j = 0 ; j < dict[strB[i]].size() ; j++) 

            num[++k] = dict[strB[i]][j] ;
    }
    if(k==0) return 0 ; 

    d[1] = 0 , t[1] = 1 ; 
    int len = 1, cur ;

    for(int i = 1 ; i <= k ; i++ ){
        if(num[i] > num[t[len]]) t[++len] = i , d[i] = t[len-1] ;
        else{
            cur = bs(1,len,i);
            t[cur] = i ;
            d[i] = t[cur-1];
        }

    }
    return len ;

}