Cod sursa(job #2143625)

Utilizator deleted_fb9d5fb04f7b88d9DELETED deleted_fb9d5fb04f7b88d9 Data 26 februarie 2018 09:44:56
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
#define NM 1025
int a[NM],b[NM],lg[NM][NM],d[NM][NM],i,j;

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

int main()
{   int i,j,n,m;
    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<=m;j++)
        if(a[i]==b[j])
        {
            lg[i][j]=lg[i-1][j-1] + 1;
            d[i][j] = 1;
        }
        else
            if (lg[i- 1][j] > lg[i][j - 1])
            {
                lg[i][j] = lg[i- 1][j];
                d[i][j] = 2;
            }
            else {
                lg[i][j] = lg[i][j - 1];
                d[i][j] = 3;
            }

    fout<<lg[n][m]<<'\n';

    scrie(n,m);

}