Cod sursa(job #471707)

Utilizator andrey932Andrei andrey932 Data 20 iulie 2010 14:23:26
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
using namespace std;

fstream fin("cmlsc.in",ios::in);
fstream fout("cmlsc.out",ios::out);
int m,n,i,j,c;	
int d[1025][1025];
int dela[1025][1025];
int s1[1025],s2[1025],s[1025];	

int max(int a, int b)	{
	if (a>b) return a;
	return b;
}

int main(){

	fin>>m; fin>>n;
	
	for(i=1;i<=m;i++)	{
		fin>>s1[i]; 
	} 
	for(i=1;i<=n;i++)	{
		fin>>s2[i]; 
	}
	
	for(i=1;i<=m;i++)	{
		for(j=1;j<=n;j++)	{
			if (s1[i]==s2[j]) 	d[i][j]=d[i-1][j-1]+1; 				
			else d[i][j]=max(d[i-1][j],d[i][j-1]);
		}
	}

	i=m; j=n;
	c=0;
	fout<<d[m][n]<<"\n";
	while (i>0&&j>0)	{
		if (s1[i]==s2[j])	{
			c++; s[c]=s1[i];
			i--;
			j--;
		}
		else if (d[i-1][j]>d[i][j-1]) i--;
		else j--;
	}
	for(;c>0;c--) {fout<<s[c]<<" ";}
	fout.close();
	return 0;
}