Cod sursa(job #1846219)

Utilizator lpsasuSasu Alexandru lpsasu Data 12 ianuarie 2017 13:16:30
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int n,m,a[1024],b[1024],c[1024];

int max(int x,int y)
{
    if(x>y)
        return x;
    return y;
}

int LCS(int i,int j)
{
    if(i<0||j<0)
        return 0;
    if(a[i]==b[j])
    {
        int x;
        x=LCS(i-1,j-1)+1;
        c[i]=x;
        return x;
    }
    if(a[i]!=b[j])
    {
        return max(LCS(i-1,j),LCS(i,j-1));
    }
}
void print(int x,int j)
{
    if(j<m)
    {
        if(c[j]==x+1)
        {
            out<<a[j]<<' ';
            print(x+1,j+1);
        }
        print(x,j+1);
    }
}

int main()
{

    in>>m>>n;
    for(int i=0; i<m; i++)
    {
        in>>a[i];
    }
    for(int j=0; j<n; j++)
    {
        in>>b[j];
    }
    int x=LCS(m-1,n-1);
    out<<x<<'\n';
    print(0,0);
    return 0;
}