Cod sursa(job #1518673)

Utilizator saladas2Luca Ion saladas2 Data 6 noiembrie 2015 08:38:42
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
using namespace std ;
ifstream in ("cmlsc.in");
ofstream out ("cmlsc.out");
int a[1025],b[1025],c[1025][1025],m,n,v[1025],k ;
int main () {
	int i,j ;
	in >> n >> m ;
	for (i=1;i<=n;i++)
		in >> a[i] ;
	for (j=1;j<=m;j++)
		in >> b[j] ;
	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 ;
			else 
				if (c[i-1][j]>=c[i][j-1])
					c[i][j]=c[i-1][j] ;
				else
					c[i][j]=c[i][j-1] ;
	cout << c[n][m] << '\n' ;
	i=n ;
	j=m ;
	k=c[n][m] ;
	while (i && j) {
		if (a[i]==b[j]) {
			v[k--]=a[i] ;
			i-- ;
			j-- ;
		}
		else
			if (c[i-1][j]>=c[i][j-1]) 
				i-- ;
			else 
				j-- ;
	}
	k=c[n][m] ;
	for (i=1;i<=k;i++)
		cout << v[i] << " " ;
	return 0 ;
}