Cod sursa(job #2550045)

Utilizator Tom3sNagy Magynzts Matyas Tom3s Data 18 februarie 2020 12:36:36
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>

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

int main()
{
    int n, m;
    fin >> n >> m;

    int a[n], b[m], din[n+1][m+1] = {0};

    for (int i = 0; i < n; i++) fin >> a[i];
    for (int i = 0; i < m; i++) fin >> b[i];

    std::vector<int> subsir;

    for (int i = 0; i < n; i++){
        for (int j = 0; i < m; j++){
            if (a[i] == b[j]){
                din[i+1][j+1] = 1 + din[i][j];
            } else {
                din[i+1][j+1] = std::max(din[i][j+1], din[i+1][j]);
            }
        }
    }

    for (int i = m, j = n; i; ){
        if (a[i-1] == b[j-1]){
            subsir.push_back(a[i-1]);
            i--;
            j--;
        } else if (din[i][j-1] > din[i-1][j]){
            j--;
        } else i--;

    }

    fout << subsir.size() << "per n";
    for (int i = subsir.size()-1; i >= 0; i--){
        fout << subsir[i] << " ";
    }

    return 0;
}