Cod sursa(job #2050637)

Utilizator alingeorgiu99@yahoo.comGeorgiu Alin Ionel [email protected] Data 28 octombrie 2017 10:44:44
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<iostream>
#include<fstream>
#include<cstring>
#define MAX 1025
using namespace std;
fstream fin("cmlsc.in",ios::in),fout("cmlsc.out",ios::out);
unsigned int a[MAX],b[MAX],x[MAX][MAX],v[MAX];
int main()
{
    int n,m,i,j,k=0;
    fin>>n>>m;
    for(i=1; i<=n; i++)
    {
        fin>>a[i];
    }
    for(j=1; j<=m; j++)
    {
        fin>>b[j];
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            if(a[i]==b[j])
            {
                x[i][j]=x[i-1][j-1]+1;
            }
            else
            {
                x[i][j]=max(x[i][j-1],x[i-1][j]);
            }
        }
    }
    fout<<(int)x[n][m]<<'\n';
    i=n;
    j=m;
    while(i>0 && j>0 && x[i][j]>0)
    {
        if(a[i]==b[j])
        {
            v[++k]=a[i];
            i--;
            j--;
        }
        else
        {
            if(x[i-1][j]>x[i][j-1])
            {
                i--;
            }
            else
            {
                j--;
            }
        }
    }
    for(i=k;i>=1;i--)
    {
        fout<<v[i]<<" ";
    }
fin.close();
fout.close();
return 0;
}