F - LCS

キーワード

• DP
• EDPC
• LCS

解説

問題 (opens in a new tab)

$s$ と $t$ を左から見ていき、一致する文字を貪欲に取ることで、最長共通部分列を求めることができる。

$m = |s|, n=|t|$ として、 $i=0,1,\dots,m, ~ j=0,1,\dots,n$ に対して、 $dp_{i,j}$ を次のように定義する。

$s$ の最初の $i$ 文字と $t$ の最初の $j$ 文字の最長共通部分列の長さ

$s$ の最初の $i$ 文字と $t$ の最初の $j$ 文字の最長共通部分列の長さは、

• $s$ の $i$ 文字目と $t$ の $j$ 文字目が一致する場合、 $s$ の最初の $i-1$ 文字と $t$ の最初の $j-1$ 文字の最長共通部分列の長さに $1$ を足したもの
• そうでない場合、 $s$ の最初の $i-1$ 文字と $t$ の最初の $j$ 文字の最長共通部分列の長さと $s$ の最初の $i$ 文字と $t$ の最初の $j-1$ 文字の最長共通部分列の長さの大きい方

となる。よって、次の漸化式が成り立つ。

計算量は一回の遷移に $O(1)$ かかるので、全体で $O(mn)$ となる。

最終的な答えは $dp_{m,n}$ となる。

復元

最長共通部分列を復元するためには、 $dp_{m,n}$ から逆順に遡っていく。

• $dp_{i,j}$ が $dp_{i-1,j}$ と等しいまたは $dp_{i,j-1}$ と等しい場合、 $dp_{i,j}$ は $dp_{i-1,j}$ または $dp_{i,j-1}$ から遷移してきたことになる。この場合、 $s_i$ と $t_j$ は共通部分列に含まれない。
• そうでない場合、 $s_i,t_i$ を共通部分列の先頭に追加し、 $dp_{i-1,j-1}$ に遷移する。

これを $dp_{0,0}$ に到達するまで繰り返すことで、最長共通部分列を復元できる。

提出コード

int main() {
    string s, t; cin >> s >> t;
    vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
    rep(i,1,s.size()+1) {
        rep(j,1,t.size()+1) {
            if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    int i = s.size(), j = t.size();
    string ans = "";
    while (i > 0 && j > 0) {
        if (s[i-1] == t[j-1]) {
            ans = s[i-1] + ans;
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1]) i--;
        else j--;
    }
    cout << ans << endl;
}