[AtCoder] Educational DP Contest F – LCS

2019年11月27日

問題

方針

いわゆる最長共通部分列問題ですね。有名なアルゴリズムなので、ググりましょう。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    string s, t;
    cin >> s >> t;
    int n = s.length();
    int m = t.length();
    int dp[n + 1][m + 1]{};
    
    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]);
            }
        }
    }
    string ans = "";
    int r = n;
    int c = m;
    while (r > 0 && c > 0) {
        if (s[r - 1] != t[c - 1]) {
            if (dp[r - 1][c] > dp[r][c - 1]) r--;
            else c--;
        } else {
            ans += s[r - 1];
            r--;
            c--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << "\n";
    return 0;
}