Cod sursa(job #1325758)

Utilizator horiainfoTurcuman Horia horiainfo Data 24 ianuarie 2015 12:38:49
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>

using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
int a[1025],b[1025],n,m;
struct vector{int ant,nr;} v[1025];
void rezolv()
{
    int poz;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            if(b[j]==a[i])
            {
                v[j].nr=1; v[j].ant=0;
                for(int i=1;i<j;i++)
                    if(v[j].nr<v[i].nr+1) v[j].nr=v[i].nr+1,v[j].ant=i;
                break;
            }
    }
    int vmax=0;
    for(int i=1;i<=m;i++)
        if(v[i].nr>vmax) vmax=v[i].nr,poz=i;
    fout<<vmax<<'\n';
    int k[1025],nrc=0;
    while(poz!=0)
        k[++nrc]=poz,poz=v[poz].ant;
    for(int i=vmax;i>=1;i--)
        fout<<b[k[i]]<<' ';
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    for(int i=1;i<=m;i++)
        fin>>b[i];
    rezolv();
    return 0;
}