Cod sursa(job #2386397)

Utilizator S_AndyAndrei S S_Andy Data 22 martie 2019 19:02:02
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int main() {
	short m, n, *v, **s;
	fin >> m >> n;
	v = new short[m + 1];
	s = new short*[n + 1];
	s[0] = new short[m + 1];
	s[0][0] = 0;
	for (short i = 1; i <= m; ++i) {
		fin >> v[i];
		s[0][i] = 0;
	}
	for (short i = 1; i <= n; ++i) {
		fin >> v[0];
		s[i] = new short[m + 1];
		s[i][0] = 0;
		for (short j = 1; j <= m; ++j) {
			if (v[0] == v[j]) {
				s[i][j] = s[i - 1][j - 1] + 1;
			}
			else {
				s[i][j] = max(s[i - 1][j], s[i][j - 1]);
			}
		}
	}
	short l = s[n][m], *u = new short[l];
	for (short i = n, j = m, k = l; k > 0; ) {
		if (s[i - 1][j] < s[i][j]) {
			if (s[i][j - 1] < s[i][j]) {
				u[--k] = v[j];
				--i;
				--j;
			}
			else {
				--j;
			}
		}
		else {
			--i;
		}
	}
	fout << l << "\n";
	for (short i = 0; i < l; ++i) {
		fout << u[i] << " ";
	}
}