Cod sursa(job #610256)

Utilizator SteveStefan Eniceicu Steve Data 26 august 2011 05:38:03
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream.h>

int main ()
{
	int M, N, v[2][1030][1030], i, j, X[1030], Y[1030];
	ifstream fin ("cmlsc.in");
	ofstream fout ("cmlsc.out");
	memset (v, 0, sizeof (v));
	fin >> M >> N;
	for (i = 1; i <= M; i++)
	{
		fin >> X[i];
	}
	for (j = 1; j <= N; j++)
	{
		fin >> Y[j];
	}
	fin.close ();
	for (i = 1; i <= M; i++)
	{
		for (j = 1; j <= N; j++)
		{
			if (X[i] == Y[j])
			{
				memcpy (v[i % 2][j], v[(i - 1) % 2][j - 1], sizeof (v[i % 2][j]));
				v[i % 2][j][0]++;
				v[i % 2][j][v[i % 2][j][0]] = X[i];
			}
			else
			{
				if (v[i % 2][j - 1][0] > v[(i - 1) % 2][j][0]) memcpy (v[i % 2][j], v[i % 2][j - 1], sizeof (v[i % 2][j]));
				else memcpy (v[i % 2][j], v[(i - 1) % 2][j % 2], sizeof (v[i % 2][j]));
			}
		}
	}
	fout << v[M % 2][N][0] << "\n";
	for (i = 1; i <= v[M % 2][N][0]; i++)
	{
		fout << v[M % 2][N][i] << " ";
	}
	fout.close ();
	return 0;
}