a252 - Another LCS

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算三個字串的最長共同子序列 (Longest Common Subsequence, LCS) 的長度。

解題思路

本題為 LCS 問題的擴展，從兩個字串擴展到三個字串。解決方法是使用動態規劃 (Dynamic Programming)。定義 lcs[i][j][k] 為字串 a 的前 i 個字元、字串 b 的前 j 個字元和字串 c 的前 k 個字元的 LCS 長度。

狀態轉移方程如下：

• 如果 a[i-1] == b[j-1] && b[j-1] == c[k-1]，則 lcs[i][j][k] = lcs[i-1][j-1][k-1] + 1。
• 否則，lcs[i][j][k] = max(max(lcs[i-1][j][k], lcs[i][j-1][k]), lcs[i][j][k-1])。

初始化 lcs[i][0][0] = lcs[0][j][0] = lcs[0][0][k] = 0。

最終結果為 lcs[al-1][bl-1][cl-1]，其中 al、bl 和 cl 分別為字串 a、b 和 c 的長度。

複雜度分析

• 時間複雜度: O(nmp)，其中 n, m, p 分別為三個字串的長度。
• 空間複雜度: O(nmp)，用於儲存 lcs 陣列。

程式碼

#include <iostream>
using namespace std;
int lcs[101][101][101];
int main(){
	string a,b,c;
	cin >> a >> b >> c;
	a+=' ';
	b+=' ';
	c+=' ';
	int al=a.length(),bl=b.length(),cl=c.length();
	for(int i=1;i<al;++i){
		for(int j=1;j<bl;++j){
			for(int k=1;k<cl;++k){
				if(a[i-1]==b[j-1]&&b[j-1]==c[k-1])
					lcs[i][j][k]=lcs[i-1][j-1][k-1]+1;
				else 
					lcs[i][j][k]=max(max(lcs[i-1][j][k],lcs[i][j-1][k]),lcs[i][j][k-1]); 
			}
		}
	}
	cout << lcs[al-1][bl-1][cl-1];
}