Cod sursa(job #2924735)

Utilizator Andrei137Neculae Andrei-Fabian Andrei137 Data 9 octombrie 2022 18:40:30
Problema Cel mai lung subsir comun Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>

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

void readArray(int n, int arr[])
{
    for (auto i = 1; i <= n; ++i)
        in >> arr[i];
}

int main()
{
    int m, n, x[1040], y[1040], lcs[1040], index = 0, l[100][100] = {0};
    in >> m >> n;
    readArray(m, x);
    readArray(n, y);
    for (auto i = 1; i <= m; ++i)
        for (auto j = 1; j <= n; ++j)
            if (x[i] == y[j])
                l[i][j] = 1 + l[i - 1][j - 1];
            else
                l[i][j] = std::max(l[i - 1][j], l[i][j - 1]);
    auto i = m, j = n;
    while (i > 0 && j > 0)
    {
        if (x[i] == y[j])
        {
            lcs[++index] = x[i];
            --i;
            --j;
        }
        else if (l[i - 1][j] > l[i][j - 1])
            --i;
        else
            --j;
    }
    out << l[m][n] << '\n';
    for (i = index; i >= 1; --i) 
        out << lcs[i] << ' ';
    in.close();
    out.close();
    return 0;
}