Cod sursa(job #2361531)

Utilizator CristianSoareSoare Cristian Costantin CristianSoare Data 2 martie 2019 16:35:45
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda pregatire_cls12_oji Marime 0.82 kb
#include <fstream>
using namespace std;

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

int a[1030], b[1030], l[1030][1030], s[1030], loc;

int main(){
    int n, m, i, j;
    fin >> m >> n;
    for (i = 1;i <= m;i++)
        fin >> a[i];
    for (i = 1;i <= n;i++)
        fin >> b[i];
    for (i = 1;i <= n;i++)
        for (j = 1;j <= m;j++)
            if (a[i] == b[j])
                l[i][j] = 1+l[i-1][j-1];
            else l[i][j] = max(l[i-1][j], l[i][j-1]);
    i = m;
    j = n;
    while (i){
        if (a[i] == b[j]){
            s[++loc] = a[i];
            i--;
            j--;
        }
        else if (l[i-1][j] < l[i][j-1])
            j--;
        else i--;
    }
    fout << loc << '\n';
    for (i = loc;i > 0;i--)
        fout << s[i] << " ";
    return 0;
}