c001 - 10405 - Longest Common Subsequence

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算兩個字串的最長共同子序列 (Longest Common Subsequence, LCS) 的長度。共同子序列是指不需要連續，但保持相對順序的字串。

解題思路

本題使用動態規劃 (Dynamic Programming) 解決。定義 lcs[i][j] 為字串 a 的前 i 個字元和字串 b 的前 j 個字元的 LCS 長度。

狀態轉移方程如下：

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

初始化 lcs[i][0] = 0 和 lcs[0][j] = 0。最終結果為 lcs[al-1][bl-1]，其中 al 和 bl 分別為字串 a 和 b 的長度。

程式碼中，為了方便處理邊界情況，在字串 a 和 b 的開頭各添加了一個空格。

複雜度分析

• 時間複雜度: O(m*n)，其中 m 和 n 分別是字串 a 和 b 的長度。
• 空間複雜度: O(m*n)，用於儲存 lcs 陣列。

程式碼

#include <iostream>
using namespace std;
int main(){
	string a,b;
	while(getline(cin,a)){
		getline(cin,b);
		a=' '+a;
		b=' '+b;
		int al=a.length(),bl=b.length(),lcs[al][bl];
		for(int i=0;i<al;++i)
			for(int j=0;j<bl;++j)
				lcs[i][j]=0;
		for(int i=1;i<al;++i){
			for(int j=1;j<bl;++j){
				if(a[i]==b[j])
					lcs[i][j]=lcs[i-1][j-1]+1;
				else
					lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);
			}
		}
		cout << lcs[al-1][bl-1] << "\n";
	}
}