Submission #25337352

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++(i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++(i))
#define REP_R(i, n) for (int i = (int)(n)-1; (i) >= 0; --(i))
#define REP3R(i, m, n) for (int i = (int)(n)-1; (i) >= (int)(m); --(i))
#define ALL(x) ::std::begin(x), ::std::end(x)
using namespace std;

int sim(char x, char y) {
    if (x == '-') return -5;
    if (y == '-') return -5;
    return x == y ? 1 : -3;
}

constexpr int INF = 1e9;

std::pair<std::string, std::string> solve(const std::string &s, const std::string &t) {
    int n = s.length();
    int m = t.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -INF));
    vector<vector<pair<int, int>>> link(n + 1, vector<pair<int, int>>(m + 1, make_pair(-1, -1)));
    auto use = [&](int i, int j, int value, int prev_i, int prev_j) {
        if (dp[i][j] < value) {
            dp[i][j] = value;
            link[i][j] = make_pair(prev_i, prev_j);
        }
    };
    dp[0][0] = 0;
    REP (i, n + 1) {
        REP (j, m + 1) {
            if (i < n and j < m) {
                use(i + 1, j + 1, dp[i][j] + sim(s[i], t[j]), i, j);
            }
            if (i < n) {
                use(i + 1, j, dp[i][j] + sim(s[i], '-'), i, j);
            }
            if (j < m) {
                use(i, j + 1, dp[i][j] + sim('-', t[j]), i, j);
            }
        }
    }
    string ss;
    string tt;
    for (int i = n, j = m; ; ) {
        auto [prev_i, prev_j] = link[i][j];
        if (prev_i == -1) {
            break;
        }
        ss.push_back(i == prev_i ? '-' : s.at(prev_i));
        tt.push_back(j == prev_j ? '-' : t.at(prev_j));
        i = prev_i;
        j = prev_j;
    }
    reverse(ALL(ss));
    reverse(ALL(tt));
    return make_pair(ss, tt);
}

// generated by oj-template v4.8.0 (https://github.com/online-judge-tools/template-generator)
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::string s, t;
    std::cin >> s >> t;
    auto [c, d] = solve(s, t);
    std::cout << c << '\n' << d << '\n';
    return 0;
}

Submission Info

Judge Result