Cod sursa(job #3362237)

Utilizator DodeucGagiu Daniel Dodeuc Data 4 august 2026 15:54:59
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");

int lscRec(const vector<int>& A, const vector<int>& B, int m, int n, vector<vector<int>>& memo){
    if(m == 0 || n == 0) return 0;

    if(memo[m][n] != -1) return memo[m][n];

    if(A[m-1] == B[n-1]){
            return memo[m][n] = 1 + lscRec(A, B, m-1, n-1, memo);
        }

    return memo[m][n] = max(lscRec(A, B, m, n-1, memo), lscRec(A, B, m-1, n, memo));
}



int main(){
    int m, n;
    fin >> m >> n;
    vector<int> A(m), B(n);

    for(int i = 0; i < m; i++){
        fin >> A[i];
    }
    for(int i = 0; i < n; i++){
        fin >> B[i];
    }

    vector<vector<int>> memo(m+1, vector<int>(n+1, -1));

    int lungime = lscRec(A, B, m, n, memo);
    fout << lungime << '\n';

    vector<int> C;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (A[i - 1] == B[j - 1]) {
            C.push_back(A[i - 1]);
            i--;
            j--;
        } 
        else if (memo[i - 1][j] >= memo[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    reverse(C.begin(), C.end());
    for (int val : C) {
        fout << val << " ";
    }
    
}