Cod sursa(job #1435984)

Utilizator StefanRARapeanu-Andreescu Stefan StefanRA Data 14 mai 2015 21:05:05
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
int n, m, i, j, s1[1026], s2[1026], d[1026][1026], lcs[1026], l;
int main()
{
	freopen("cmlsc.in", "r", stdin);
	freopen("cmlsc.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for (i=1;i<=n;i++)
		scanf("%d", &s1[i]);
	for (i=1;i<=m;i++)
		scanf("%d", &s2[i]);
	for (i=n;i>0;i--)
		for (j=m;j>0;j--)
			if (s1[i]==s2[j])
				d[i][j]=d[i+1][j+1]+1;
			else
				d[i][j]=std::max(d[i+1][j], d[i][j+1]);
	i=j=1;
	while (i<=n && j<=m)
		if (s1[i]==s2[j])
		{
			lcs[++l]=s1[i];
			i++;
			j++;
		}
		else
			if (d[i+1][j]>d[i][j+1])
				i++;
			else
				j++;
	printf("%d\n", d[1][1]);
	for (i=1;i<=l;i++)
		printf("%d ", lcs[i]);
	return 0;
}