EDPC F-LCS

LCS -最長共通部分列問題

ja.wikipedia.org

２つの文字列の最長共通部分列を出力する問題です。
計算機科学における古典問題として知られているとのことです。

個数の算出

dp[sのi文字目まで調べたとき][tのj文字目まで調べたとき]=個数
と置いて，dpを回してやると計算できます。

遷移はs[i]==t[j]のときdp[i+1][t+1]=dp[i][j]+1とし、
s[i]!=t[j]のとき dp[i+1][t+1]=mas(dp[i+1][j] dp[i][j+1])とします。

復元

個数の算出は簡単ですが最長部分列の１つを出力する問題なので復元が必要です。
最初に空の文字列を定義し､dp[i+1][t+1]=dp[i][j]+1の遷移の際にs[i-1]を文字列の先頭に加えることで復元できそうです。
　→　この方針だとバグるようです。

コード

昨晩解説ACしたコードを自力で書いてみました。
WAするケースがあるのであとで確認します。

なおrepマクロ､これまでは何か邪道なような気がして使ってませんでしたが､単に入力を省略するだけでなくコード全体をすっきりさせるメリットが大きく､今後は使っていく練習もしたいと思います。

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)

int main(){
  string s,t;
  cin>>s>>t;
  int slen=s.length();
  int tlen=t.length();
  int dp[3010][3010];
  rep(i,slen+1)rep(j,tlen+1){
    if(s[i]==t[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]);
    }
  }
  //復元
  string ans="";
  int i=slen;
  int j=tlen;
  while(i>0 && j>0){
    //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
    if(dp[i][j]==dp[i-1][j-1]+1){
      ans=s[i-1]+ans;
      i--;
      j--;
    }
    else{
      if(dp[i][j]==dp[i-1][j]){
        i--;
      }
      else if(dp[i][j]==dp[i][j-1]){
        j--;
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

修正

復元部分を修正しました。
dp[i+1][t+1]=max(dp[i+1][j] ,dp[i][j+1])の復元を行い、いずれでもない場合にdp[i+1][t+1]=dp[i][j]の遷移と考えて復元するとうまくいきました。

仕組みはまだ十分に理解できていません。

  //復元
  string ans="";
  int i=slen;
  int j=tlen;
  while(i>=0 && j>=0){
    if(dp[i][j]==dp[i-1][j]){
        i--;
      }
      else if(dp[i][j]==dp[i][j-1]){
        j--;
      }
    else{
      ans=s[i-1]+ans;
      i--;
      j--;
    }
  }