Cod sursa(job #809679)

Utilizator CataBBaincescu Catalina CataB Data 8 noiembrie 2012 20:21:48
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>

using namespace std;

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

void citire();
void pd();
void afisare();

int n, m;
int a[1025], b[1025];
int Lcs[1025][1025], OP[1025][1025];

int main()
{
	citire();
	pd();
	afisare();
	return 0;
}

void citire()
{
	int i;
	fin>>n>>m;
	for(i=0;i<n;i++)
		fin>>a[i];
	for(i=0;i<m;i++)
		fin>>b[i];
}

void pd()
{
	int i, j;
	for(i=n-1;i>=0;i--)
		for(j=m-1;j>=0;j--)
			if(a[i]==b[j])
			{
				Lcs[i][j]=1+Lcs[i+1][j+1]; OP[i][j]=1;
			}
			else
			{
				if(Lcs[i+1][j]>Lcs[i][j+1])
				{
					Lcs[i][j]=Lcs[i+1][j]; OP[i][j]=2;
				}
				else
				{
					Lcs[i][j]=Lcs[i][j+1]; OP[i][j]=3;
				}
			}
}

void afisare()
{
	int i=0, j=0;
	fout<<Lcs[0][0]<<'\n';
	while(i<n && j<m)
		if(OP[i][j]==1)
		{
			fout<<a[i]<<' ';
			i++; j++;
		}
		else
			if(OP[i][j]==2)
				i++;
			else
				if(OP[i][j]==3)
					j++;
}