Cod sursa(job #2911379)

Utilizator AndreiPaval03Andrei Paval AndreiPaval03 Data 28 iunie 2022 22:30:05
Problema Cel mai lung subsir comun Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;

int main() {
    ifstream cin("cmlsc.in");
    ofstream cout("cmlsc.out");

    int n, m; cin >> n >> m;
    vector<int> a(n + 1);
    vector<int> b(m + 1);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    
    vector<vector<int>> lcs(n + 1, vector<int>(m + 1));
    for (int i = 1; i < n; ++i) {
        lcs[i][0] = lcs[i - 1][0] + int(a[i] == b[0]);
    }
    for (int j = 1; j < m; ++j) {
        lcs[0][j] = lcs[0][j - 1] + int(a[0] == b[j]);
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < m; ++j) {
            if (a[i] == b[j]) {
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
            } else {
                lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
            }
        }
    }
    cout << lcs[n - 1][m - 1] << endl;
    stack<int> sol;
    int i = n - 1, j = m - 1;
    while (i >= 0 && j >= 0) {
        if (a[i] == b[j]) {
            sol.push(a[i]);
            i--;
            j--;
        } else if (lcs[i][j] == lcs[i - 1][j]) {
            i--;
        } else {
            j--;
        }
    }
    while (!sol.empty()) {
        cout << sol.top() << " ";
        sol.pop();
    }

    return 0;
}