F - LCS

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 1e18; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0); 
    9    string a, b; cin >> a >> b;
    10    vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1));
    11    for (int i = 1; i <= a.size(); i++) {
    12        for (int j = 1; j <= b.size(); j++) {
    13            if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
    14            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    15        }
    16    }
    17    auto out = [&](const vector<vector<int>> &dp) {
    18        string ans = "";
    19        int i = a.size(), j = b.size();
    20        while (i != 0 && j != 0) {
    21            if (dp[i][j] == dp[i - 1][j - 1] + 1 && a[i - 1] == b[j - 1]) {
    22                i--; j--; ans += a[i];
    23            } else if (dp[i][j] == dp[i - 1][j]) {
    24                i--;
    25            } else {
    26                j--;
    27            }
    28        }
    29        return ans;
    30    };
    31    string s = out(dp);
    32    reverse(s.begin(), s.end());
    33    cout << s << '\n';
    34    return 0;
    35}