わりとよくある備忘録

競プロ他雑多な私的メモ

LongestCommonSubsequence(EDP-F)

atcoder.jp
有名なDPの問題なので知ってはいたが、ややこしそうなので後回しにしていた。
先日買ったけんちょんさん(@drken1215)の本を進めていたら章末問題に載っていたので、もりもり鍛えるべく重い腰を上げて解いてみた。


自分的には結構ややこしくて遷移の理解に苦しんだ。
文字列系アルゴリズムへの苦手意識が拭えない。

最長共通部分列問題(LCS Problem)

二つの異なる系列が与えられ、その共通部分列を答える問題。
ここでいう系列としては文字列などの記号列を取り扱う場合が多い。
また部分列は、順序は保持する必要はあるが隣接関係は崩れても良いというあたりがややこしい。
詳しくはwikiを参照。
最長共通部分列問題 - Wikipedia

どう解くか

dpの基本である部分問題に分割してそれを順に解いていくということをする。(当たり前..)
具体例として、EducationalDPコンテストの入力である二つの文字列S=axyb,T=abyxbを考える。

まず、S,Ti,j文字目をそれぞれs_{i},t_{j}で表すとする。
そしてdp [i][j]S_{sub_i}=s_{1}s_{2}...s{i},T_{sub_j}=t_{1}t_{2}...t_{j}最長共通部分列長さと定義する。
そうすると、i,j文字目に注目し①s_{i}==t_{j}ならば、その文字を除いた前の文字列S_{i-1},T_{j-1}に今の一致した分の長さを加えれば良いので、

dp [i][j]=dp[i-1][j-1]+1

となる。
次に②s_{i}!=t_{j}の場合を考えると、dp配列の値はS_{i-1},T_{j}のLCSとS_{i},T_{j-1}のLCSのうちより長いほうの値がそのまま現状態の長さになり、遷移は下記のようになる。
dp [i][j]=max(dp[i-1][j],dp[i][j-1])

この遷移を適用し、dp配列を埋めていくと下記表のようになる。
ここで矢印は更新に適用された遷移であり、""は空文字を表している。
f:id:KLEE:20201010180407j:plain
この表の上では斜めの遷移が①(注目文字の追加)の遷移、縦横の遷移が②(注目文字の削除)となっている。
これはS_{1}=a,T_{4}=axybを一致させるにはt_{2}t_{3}t_{4}を削除する必要があることを考えると分かりやすい。

実装例

遷移がここまで書ければあとは実装するだけだが、上記までの処理ではLCSの長さしか分からない。
復元が求められる場合は、表の右下から見ていって丸が着いた部分に遭遇したら斜め左上に遷移し、そうで無い部分のときは縦横のうち自信と同じ値を持つ方向に遷移するというポリシーで表の左上まで辿っていけばLCSそのものが得られる。
この時、縦横のうち両方とも同じ値の場合にどちらを優先するかで復元されるLCSは異なる物になる場合がある(LCSは一般に複数パターンあり得る)。
復元も含めて実装した例は下記のようになる。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

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

int main() {
  string s,t;
  cin>>s>>t;
  int n=s.size();
  int m=t.size();
  vector<vector<int>>dp(n+1,vector<int>(m+1,0));

  //各状態でのLCS長さをメモ
  rep(i,n){
      rep(j,m){
        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]);
        }
      }
  }
  //後ろから辿っていきLCSを復元
  int i=n,j=m;
  string ans="";
  while(i>0&&j>0){
      if(s[i-1]==t[j-1]){
          ans+=s[i-1];
          i--;j--;
      }
      else{
          if(dp[i][j]==dp[i-1][j]){//横方向優先
              i--;
          }
          else{
              j--;
          }
      }
  }
  //後ろ向きにメモしたので逆順に直す
  reverse(ans.begin(),ans.end());

  cout<<ans<<endl;
  return 0;
}

ややこしい...