Cod sursa(job #2956744)

Utilizator AndreiPaval03Andrei Paval AndreiPaval03 Data 20 decembrie 2022 14:32:20
Problema Cel mai lung subsir comun Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>

using namespace std;

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

    int n, m; cin >> n >> m;
    int a[1024] = {0};
    int b[1024] = {0};
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    
    int lcs[1024][1024] = {{0}};
    for (int i = 1; i < n; ++i) {
        if (a[i] == b[0]) {
            lcs[i][0] = 1;
        } else {
            lcs[i][0] = lcs[i - 1][0];
        }
    }
    for (int j = 1; j < m; ++j) {
        if (a[0] == b[j]) {
            lcs[0][j] = 1;
        } else {
            lcs[0][j] = lcs[0][j - 1];
        }
    }
    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]);
            }
        }
    }

    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--;
        }
    }

    cout << lcs[n - 1][m - 1] << endl;
    while (!sol.empty()) {
        cout << sol.top() << " ";
        sol.pop();
    }

    return 0;
}