Cod sursa(job #2604326)

Utilizator michael_blazemihai mihai michael_blaze Data 22 aprilie 2020 14:32:01
Problema Cel mai lung subsir comun Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <algorithm>

#define MAX 1030

using namespace std;

ifstream fin ("cmlsc.in");
ofstream fout("cmlsc.out");

int n, m;
int a[MAX], b[MAX];
int sir[MAX];
int sol[MAX];
int len;

bool subsir(int nivel) {
	int i = 1, j = 1;
	for (;i <= nivel and j <= m;i ++)
		for(;j <= m and b[j] != sir[i];j ++);
	return j <= m;
}
void backtracking(int k, int nivel) {
	int i = 1;
	if (k == n + 1) {
		if (subsir(nivel)) {
			if (nivel > len) {
				len = nivel;
				for (i = 1;i <= nivel;i ++)
					sol[i] = sir[i];
			}	
		}
		return;
	} 

	backtracking(k + 1, nivel);
	sir[nivel + 1] = a[k];
	backtracking(k + 1, nivel + 1);
}
int main() {
	fin >> n >> m;
	for (int i = 1;i <= n;i ++)
		fin >> a[i];
	for (int i = 1;i <= m;i ++)
		fin >> b[i];

	backtracking(1, 0);

	fout << len << '\n';
	for (int i = 1;i <= len;i ++)
		fout << sol[i] << ' ';
	return 0;
}