Cod sursa(job #1834976)

Utilizator medicinedoctoralexandru medicinedoctor Data 25 decembrie 2016 23:24:30
Problema Cel mai lung subsir comun Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("cmlsc.in");
ofstream cout("cmlsc.out");

vector <int> a,b,s;
vector <vector <int> > x;

void read()
{
    int n,m;
    cin >> n >> m;
    a.resize(n);
    b.resize(m);
    x.resize(n);
    for (int i=0; i<n; i++)
    {
        cin >> a[i];
        x[i].resize(m);
    }
    for (int i=0; i<m; i++)
        cin >> b[i];
}

void write()
{
    cout << s.size() << '\n';
    for (int i=s.size()-1; i>=0; i--)
        cout << s[i] << ' ';
}

void solve()
{
    if (a[0]==b[0]) x[0][0]=1; else x[0][0]=1;
    for (int i=1; i<a.size(); i++)
        if (a[i]==b[0]) x[i][0]=1; else x[i][0]=max(0,x[i-1][0]);
    for (int i=1; i<b.size(); i++)
        if (a[0]==b[i]) x[0][i]=1; else x[0][i]=max(0,x[0][i-1]);
    for (int i=1; i<a.size(); i++)
        for (int j=1; j<b.size(); j++)
            if (a[i]==b[j])
                x[i][j]=1+x[i-1][j-1];
            else
                x[i][j]=max(x[i-1][j],x[i][j-1]);
    for (int i=a.size()-1,j=b.size()-1; i>=0 && j>=0; )
        if (a[i]==b[j])
            s.push_back(a[i]),--i,--j;
        else
            if (i==0) j--; else if (j==0) i--; else if (x[i-1][j]<x[i][j-1]) --j; else --i;
}

main()
{
    read();
    solve();
    write();
}