Cod sursa(job #2876004)

Utilizator cjamesCosmin James cjames Data 22 martie 2022 20:20:21
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("cmlsc.in");
ofstream g("cmlsc.out");
int m, n;
int A[1025], B[1025], mat[1025][1025];
int subs[1025];

int main() {
    f >> m >> n;
    for (int i = 1; i <= m; i++)
        f >> A[i];
    for (int i = 1; i <= n; i++)
        f >> B[i];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (A[i] == B[j])
                mat[i][j] = mat[i-1][j-1] + 1;
            else
                mat[i][j] = max(mat[i-1][j], mat[i][j-1]);
        }
    }

    g << mat[m][n] << endl;

    int k = 0;
    for (int i = m, j = n; i >= 1 && j >= 1;) {
        if (A[i] == B[j])
            subs[++k] = A[i];
        if (mat[i-1][j] > mat[i][j-1])
            i--;
        else
            j--;
    }

    for (; k; k--)
        g << subs[k] << ' ';
    g << endl;
}