B - 共通部分文字列 (※LCSとは違う)

JOI

Quiz

ABRACADABRA
ECADADABRBCRDARA

の最大共通部分列文字列は ADABR
  • 文字列は連続である必要
  • LCSとは違う（LCSは飛び飛びOK）

AC✅

https://atcoder.jp/contests/joi2008ho/submissions/10236208

解法

  • dp[i][j] : s[i], t[j]まで使ったときの最長共通部分文字列
  • と定義してDP

イメージ

f:id:peroon:20210924014114p:plain

code 抜粋

ll dp[4005][4005];

int main(){

    // input
    string s,t;cin>>s>>t;
    ll L = s.size();
    ll M = t.size();
    
    ll ma = 0;
    rep(i, L){
      rep(j, M){
        if(s[i]==t[j]){
          if(i-1<0 || j-1<0){
            dp[i][j] = 1;
          }else{
            dp[i][j] = dp[i-1][j-1] + 1;
          }
          chmax(ma, dp[i][j]);
        }
      }
    }
    p(ma);

    return 0;
}

学び

  • s[i]==t[j]の時だけを考えればうまくやってくれる
  • これはLCSよりも楽となっていて、それは部分文字列が飛び飛びじゃないため