Cod sursa(job #1350676)

Utilizator alexandru94hahahalera alexandru94 Data 20 februarie 2015 21:43:00
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <iostream>
#include <stack>


#define MAX(a,b) (a>b?(a):(b))
int i, j, n, m;
int mat[1024][1024];
int v1[1024], v2[1024];

using namespace std;

int main()
{
	
	
	stack<int> sol;
	int solLength = 0;
	
	freopen("cmlsc.in", "r", stdin);
	freopen("cmlsc.out", "w", stdout); 

	cin>>n>>m; // n - linii, m -  coloane
	for(i = 1; i <= n; ++i) 
	{
		cin>>v1[i];	
	}
	
	for(j = 1; j <= m; ++j) 
	{
		cin>>v2[j];
	}
	
	/* the magic happens here */
	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= m; ++j) 
		{
			if(v1[i] == v2[j]) 
			{
				mat[i][j] = mat[i - 1][j - 1] + 1;
			} else {
				mat[i][j] = MAX(mat[i - 1][j], mat[i][j - 1]);	
			}
		}
	}
	solLength = mat[n][m];
	
	i = n;
	j = m;
	
	while(i > 0 && j > 0) {
		if(v1[i] == v2[j]) {
			sol.push(v1[i]); // or v2[j]
			i = i - 1;
			j = j - 1;
		} else {
			if(mat[i][j] == mat[i - 1][j] ) {
				--i;
			} else {
				--j;
			}
		}	
	}

	cout<<solLength<<"\n";
	while(!sol.empty()) 
	{
		cout<<sol.top()<<" ";
		sol.pop();
	}
	
	return 0;
}