↓ 快轉到主要內容

最長公共子序列 ( Longest Common Subsequence,LCS )

·547 字·3 分鐘
程式筆記
目錄

簡介
#

Longest Common Subsequence 通常簡稱為 LCS ，中文叫做「最長公共子序列」

定義：
#

  • 兩個序列共同擁有，順序一致但不一定連續的最長子序列

舉個例子，比如說：

  • 字串 A：“ACD”
  • 字串 B：“ABC”

‘A’ 是字串 A 和 B 的第一個字元所以 “A” 是「公共子序列」 ‘C’ 在 A 的第 2 個位子，同時也在 B 的第 3 個位子，所以 “C” 是「公共子序列」 因為 A 和 B 兩個字串都是先 ‘A’ 後 ‘C’ 因此 “AC” 也會是「公共子序列」 ‘D’ 只有在 A 出現，所以不是「公共子序列」 A 和 B 字串的公共子序列有以下幾種可能，選出裡面最長的就是「最長公共子序列」

  1. “A”
  2. “C”
  3. “AC” 👈

所以是 “AC”

錯誤案例🤯
#

  • 字串 A：“ABC”
  • 字串 Ｂ：“CBA”
  • LCS ： “ABC”

首先 LCS 順序要求一致，意思是對於字串 A 和 B 都要滿足：

  • 第一個 ‘A’ 要在第一個 ‘B’ 的左邊 ❌
  • 第一個 ‘A’ 要在第一個 ‘C’ 的左邊 ❌
  • 第一個 ‘B’ 要在第一個 ‘C’ 的左邊 ❌

可以發現字串 ‘A’ 都有滿足，但對於字串 ‘B’ 都未滿足，所以 “ABC” 不會是 LCS 這個案例的 LCS 可以是 “A” 或 “B” 或 “C”

如何寫程式
#

一般來說題目會給兩個字串，問這兩個 LCS 的長度為多少，或是請回答者輸出 LCS 字串，對於這樣的問題需要用到一種名為動態規劃（Dynamic programming）的技巧，很多人都把它簡稱為 DP

註： 其實我根本不知道甚麼是動態規劃，反正很多人 （像是 ChaGPT）都是如此稱呼，那就這麼稱呼吧~ by 作者

假設把它寫成一個函數，輸入是兩個字串，姑且稱為 a 和 b 而輸出會是 a 和 b 的 LCS，所以它應該會長這樣：

string findLCS(string a,string b){

}

接下來使用 std::vector 建立一個二維陣列，需要注意的地方是，該陣列列和行的長度會是 a 的長度 + 1 以及 b 的長度 + 1，在這裡就是 a.size() +1 和 b.size()+1 ，陣列名稱取為 “dp”

string findLCS(string a,string b){ 
	vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1,0));
}

然後寫一個雙迴圈去遍歷這個陣列，需要注意的是外層和內層的迴圈都是從1 **開始跑


string findLCS(string a,string b){ 
	
	vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1,0));
	
	for(int i = 1;i <= a.size();++i){ 
		for(int j = 1;j <= b.size();++j){ 
			....
		}
	}
}

來看看迴圈裡面要寫甚麼，可以理解成如果字串 a[i - 1 ] 和 b[j - 1] 相同 ，dp[i][j] 就會是 dp[i - 1][j - 1] + 1，否則 dp[i][j] 是 dp[i - 1][j] 和 dp[i][j - 1] 其中一個最大的

for(int i=1;i<=a.size();++i){ 
	for(int j=1;j <= b.size();++j){ 
		if(a[i-1] == b[j-1]){ 
			dp[i][j] = dp[i-1][j-1]+1; 
		} 
		else{ 
		dp[i][j] = max(dp[i-1][j],dp[i][j-1]); 
		} 
	} 
}

試著用表格來表示，可能較好理解 就拿這一個做為範例

  • 字串 A：“ACD”
  • 字串 B：“ABC”

所以會建立一個 4 x 4 的陣列，想像一下矩陣的行和列，除了第一行 / 列，每一個都代表字串中的字元

α A C D
α 0 0 0 0
A 0 1 1 1
B 0 1 1 1
C 0 1 2 2

來一個一個看

  1. ‘A’ 和 ‘A’ 是一樣，所以對應的位置（姑且稱為 AA）是 αα + 1
  2. ‘A’ 和 ‘C’ 不一樣，AC 會是 AA 和 αC 取最大的，所以會是 1
  3. ‘A’ 和 ‘D’ 不一樣，AD 會是 AC 和 αD 取最大的，所以會是 1
  4. ‘B’ 和 ‘A’ 不一樣，BA 會是 Bα 和 AA 取最大的，所以會是 1
  5. ‘B’ 和 ‘C’ 不一樣，BC 會是 BA 和 AC 取最大的，所以會是 1
  6. ‘B’ 和 ‘D’ 不一樣，BD 會是 BC 和 AD 取最大的，所以會是 1
  7. ‘C’ 和 ‘A’ 不一樣，CA 會是 Cα 和 BA 取最大的，所以會是 1
  8. ‘C’ 和 ‘C’ 是一樣，CC 會是 BA 加上 1，所以會是 2
  9. ‘C’ 和 ‘D’ 不一樣，CD 會是 CC 和 BD 取最大的，所以會是 1

基本上那一個雙回圈就是在做這件事，如果題目是問 LCS 的長度，那做到這裡就結束了，答案會是陣列最左下角的值，即 2

但如果題目是問輸出 LCS 字串呢？那就需要這段程式：

首先定義 i 和 j 為 a.size() 和 b.size()，意思就是接下來要從剛剛填好值的 DP 陣列最右下角開始跑 string lcs 用來存放找到的 LCS 字串，最後會把它輸出或 return 出去

緊接著是一個 while 迴圈，條件是 i 和 j 只要大於 0 就會跑 如果 a[i - 1] == b[j - 1] 代表這一個字元屬於 LCS ，需要將它接在 string lcs 的前面，再把 i-- 和 j-- ，其實這差不多就是在做和建 dp 陣列時相反的事。 如果 a[i - 1] 和 b[j - 1] 不一樣，那就看 dp[i][j]「左邊的」有沒有大於「上面的」，對應到建立 dp 陣列時，如果 a[i - 1] 和 b[j - 1] 不一樣，就找「左邊的」和 「上面的」誰比較大。 這一個動作就是要找到這一格陣列的值是從「左邊的」還是 「上面的」過來的，如果是「左邊的」那就 --j 是 「上面的」就 --i

int i=a.size(),j=b.size(); 
string lcs; 
while(i > 0 && j > 0){ 
	if(a[i-1]==b[j-1]){ 
		lcs = a[i-1] + lcs;
		 --i; 
		 --j; 
	} 
	else if(dp[i-1][j] > dp[i][j-1]){ 
		--i; 
	} 
	else{ 
		--j; 
	} 
}

合起來，整個函數會長這樣：

string findLCS(string a,string b){

    vector<vector<int>> dp(a.size()+1, vector<int>(b.size()+1,0));

    for(int i=1;i<=a.size();++i){
        for(int j=1;j <= b.size();++j){
            if(a[i-1] == b[j-1]){
                dp[i][j] = dp[i-1][j-1]+1;
            }
            else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }

    //rebuild LCS
    int i=a.size(),j=b.size();
    string lcs;
    while(i > 0 && j > 0){
        if(a[i-1]==b[j-1]){
            lcs = a[i-1] + lcs;
            --i;
            --j;            
        }
        else if(dp[i-1][j] > dp[i][j-1]){
            --i;
        }
        else{
            --j;
        }
    }
    return lcs;
}

相關文章