POJ 2250 Compromise

問題文

DP強化週間。

2つのテキストが与えられる。LCSを求めよ。という問題。

LCS長のdp表をジグザグと左上に進んでいき、その添字i,jのときに2つに単語s[i],t[j]が等しければ出力。そうでなければdp長が短くなる方向に移動。
こちらを参考にさせていただいた。

以下ソース。

int dp[101][101];

void print_lcs(int i, int j, vector<string> &s, vector<string> &t){
  if(i == 0 || j == 0) return;
  if(s[i - 1] == t[j - 1]){
    print_lcs(i - 1, j - 1, s, t);
    cout << s[i - 1] << " ";
  }else{
    if(dp[i - 1][j] >= dp[i][j - 1])
      print_lcs(i - 1, j, s, t);
    else
      print_lcs(i, j - 1, s, t);
  }
}

int main(){
  while(1){
    vector<string> s, t;
    string tmp;
    while(1){
      if(!(cin >> tmp)) return 0;
      if(tmp == "#") break;
      s.push_back(tmp);
    }
    while(1){
      cin >> tmp;
      if(tmp == "#") break;
      t.push_back(tmp);
    }
    
    int N = s.size();
    int M = t.size();
    
    //DP
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < N; i++){
      for(int j = 0; j < M; j++){
	if(s[i] == t[j])
	  dp[i + 1][j + 1] = dp[i][j] + 1;
	else
	  dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
      }
    }
    
    print_lcs(N, M, s, t);
    cout << endl;
  }
  return 0;
}

最初、文字ごとのLCSでやっていて答えが全く合わなかった。
単語ごとだった。びっくりした。