Cod sursa(job #156335)

Utilizator snaked31Stanica Andrei snaked31 Data 12 martie 2008 14:43:47
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>

#define nm 1025


int n, m, i, j;
int k;
int a[nm], b[nm], c[nm][nm], cf[nm][nm], d[nm];

void read()

{
	scanf("%d %d ", &n, &m);
	for (i=1; i<=n; ++i)
	{
		scanf("%d ", &a[i]);
	}
	for (i=1; i<=m; ++i)
	{
		scanf("%d ", &b[i]);
	}
}


void solve()

{
	for (i=1; i<=n; ++i)
	{
		for (j=1; j<=m; ++j)
		{
			if (a[i] == b[j])
			{
				c[i][j] = c[i-1][j-1] + 1;
				cf[i][j] = 2;
			}
			else
			{
				c[i][j] = c[i][j-1];
				cf[i][j] = 1;
				if (c[i][j] < c[i-1][j])
				{
					c[i][j] = c[i-1][j];
					cf[i][j] = 3;
				}
			}
		}
	}
	k = 0;
	for (i=n, j=m; i>0 && j>0;)
	{
		if (a[i] == b[j])
			d[++k] = a[i];
		if (cf[i][j] == 1)
		{
			j --;
		}
		else
		if (cf[i][j] == 2)
		{
			--i;
			--j;
		}
		else
		{
			--i;
		}
	}
}


void write()

{
	printf("%d\n", k);
	for (i=k; i>0; --i)
	{
		printf("%d ", d[i]);
	}
}


int main()

{
	freopen("cmlsc.in", "r", stdin);
	freopen("cmlsc.out","w",stdout);

	read();
	solve();
	write();

	return 0;
}