PKU : 2250 - Compromise
問題概要
http://poj.org/problem?id=2250
単語列が2つ与えられます.
これらの最長共通部分列を求めてください.
プログラム
int main(void){ while(1){ vector<string> a,b; string s; //Aの単語列入力 while(1){ if(!(cin>>s)) return 0; if(s == "#") break; a.push_back(s); } //Bの単語列入力 while(1){ cin>>s; if(s == "#") break; b.push_back(s); } int n = a.size(); int m = b.size(); int dp[n+1][m+1]; memset(dp,0,sizeof(dp)); //最長共通部分列の長さをDPで計算 rep(i,n){ rep(j,m){ if(a[i] == b[j]){ dp[i+1][j+1] = dp[i][j] + 1; } else{ dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]); } } } //DP表を逆辿りして, 答えの単語列を生成 vector<string> ans; int i = n, j = m; while(i > 0 && j > 0){ if(a[i-1] == b[j-1]){ ans.push_back(a[i-1]); i--; j--; } else if(dp[i][j] == dp[i-1][j]){ i--; } else{ j--; } } //出力 for(int i=ans.size()-1;i>=0;i--){ if(i != ans.size()-1) cout<<" "; cout<<ans[i]; } cout<<endl; } }