e682 - 00531 - Compromise
題目描述
題目要求找出兩個句子中最長共同單詞子序列。輸入包含兩個句子，每個句子以 '#' 結尾。輸出最長共同單詞子序列，單詞之間用空格分隔。
解題思路
本題可以使用動態規劃 (Dynamic Programming) 解決。定義 c[i][j] 為第一個句子前 i 個單詞和第二個句子前 j 個單詞的最長共同子序列的長度。如果 a[i] 等於 b[j]，則 c[i][j] = c[i-1][j-1] + 1，並記錄下該單詞的索引。否則，c[i][j] = max(c[i-1][j], c[i][j-1])。
d[i][j][k] 記錄第 i 個句子和第 j 個句子最長共同子序列的前 k 個單詞的索引。
最後，根據 d 陣列回溯，輸出最長共同子序列。
複雜度分析
- 時間複雜度: O(nml)，其中 n 和 m 分別是兩個句子的單詞數量，l 是最長共同子序列的長度。
- 空間複雜度: O(nml)，用於儲存
c和d陣列。
程式碼
#include <iostream>
using namespace std;
string a[105],b[105];
int c[105][105],d[105][105][105];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
string gt;
while(cin >> gt){
for(int i=0;i<101;++i){
a[i].clear();
b[i].clear();
for(int j=0;j<101;++j){
c[i][j]=0;
for(int k=0;k<101;++k)
d[i][j][k]=0;
}
}
a[1]=gt;
int ait=2,bit=1;
if(a[1]!="#"){
while(cin >> a[ait]){
if(a[ait]=="#")break;
++ait;
}
}
while(cin >> b[bit]){
if(b[bit]=="#")break;
++bit;
}
for(int i=1;i<ait;++i){
for(int j=1;j<bit;++j){
if(a[i]==b[j]){
c[i][j]=c[i-1][j-1]+1;
for(int k=0;k<c[i-1][j-1];++k)
d[i][j][k]=d[i-1][j-1][k];
d[i][j][c[i-1][j-1]]=i;
}
else{
if(c[i-1][j]>c[i][j-1]){
c[i][j]=c[i-1][j];
for(int k=0;k<c[i-1][j];++k)
d[i][j][k]=d[i-1][j][k];
d[i][j][c[i-1][j]]=i;
}
else{
c[i][j]=c[i][j-1];
for(int k=0;k<c[i][j-1];++k)
d[i][j][k]=d[i][j-1][k];
d[i][j][c[i][j-1]]=j;
}
}
}
}
for(int i=0;i<c[ait-1][bit-1];++i){
cout << a[d[ait-1][bit-1][i]] ;
if(i!=c[ait-1][bit-1]-1)
cout << " ";
else
cout << "\n";
}
}
}