Cod sursa(job #1090585)

Utilizator Maxim97Maxim Andrei Maxim97 Data 22 ianuarie 2014 20:33:08
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#define NMAX 1026

using namespace std;

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

int a[NMAX],b[NMAX];
int n,m;
int lcs[NMAX][NMAX];

void cit()
{
int i;
in>>n>>m;
for(i=1;i<=n;i++)in>>a[i];
for(i=1;i<=m;i++)in>>b[i];
}

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

void afis()
{
o<<lcs[1][1]<<endl;
int i,j;
i=j=1;
while(i<=n&&j<=m)
	{
	if(a[i]==b[j])o<<a[i]<<' ',i++,j++;
	else
		if(lcs[i][j]==lcs[i+1][j])i++;
		else j++;
	}
}

int main()
{
	cit();
	pd();
	afis();
	return 0;
}