Cod sursa(job #1190830)

Utilizator mariusn01Marius Nicoli mariusn01 Data 25 mai 2014 19:00:24
Problema Cel mai lung subsir comun Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#define DIM 1030

using namespace std;

int a[DIM], b[DIM], d[DIM][DIM], n, m, i, j;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");

void drum(int i, int j) {
    if (i > 0 && j > 0) {
        if (a[i] == b[j]) {
            drum(i-1, j-1);
            fout<<a[i]<<" ";
        } else
            if (d[i][j-1] > d[i-1][j])
                drum(i, j-1);
            else
                drum(i-1, j);
    }
}

int main() {

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

    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (a[i] == b[j])
                d[i][j] = 1 + d[i-1][j-1];
            else
                d[i][j] = max(d[i-1][j], d[i][j-1]);

    fout<<d[n][m]<<"\n";

    drum(n,m);

    return 0;
}