PKU : 2250 - Compromise

問題概要

http://poj.org/problem?id=2250
単語列が2つ与えられます.
これらの最長共通部分列を求めてください.

アルゴリズム

最長共通部分列問題を解くだけです.
答えの単語列を出したいときは, DP表を作成したあと, [n][m]から順番に逆辿りしていけば, 出すことができます.

プログラム

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;
  }
}