Cod sursa(job #589880)

Utilizator t2010tZaharia Teofil t2010t Data 14 mai 2011 11:17:21
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
using namespace std;

int na,nb;
int a[1025],b[1025],ret[1025],maxm;
int v[1025][1025];

int main()
{
ifstream in("cmlsc.in");
ofstream out("cmlsc.out");

int i1,i2,i3;

in>>na>>nb;
for(i1=1;i1<na+1;i1++)
	in>>a[i1];
for(i1=1;i1<nb+1;i1++)
	in>>b[i1];

for(i1=1;i1<na+1;i1++)
	for(i2=1;i2<nb+1;i2++)
		{
		if(a[i1] == b[i2])
			{
			v[i1][i2] = v[i1-1][i2-1] + 1;
			if(v[i1][i2] > maxm)
				maxm = v[i1][i2];
			}
		else
			if(v[i1-1][i2] > v[i1][i2-1])
				v[i1][i2] = v[i1-1][i2];
			else
				v[i1][i2] = v[i1][i2-1];
		}

i1 = na;
i2 = nb;
i3 = 1;

while(i1)
	{
	if(a[i1] == b[i2])
		{
		ret[i3] = a[i1];
		i3++; i1--; i2--;
		}
	else
		if(v[i1-1][i2] < v[i1][i2-1])
			i2--;
		else
			i1--;
	}

out<<maxm<<'\n';
for(i1=maxm;i1>0;i1--)
	out<<ret[i1]<<' ';

in.close();
out.close();
return 0;
}