Pagini recente » Cod sursa (job #2288254) | Cod sursa (job #2726059) | Cod sursa (job #2345626) | Cod sursa (job #1864338) | Cod sursa (job #2462341)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
const int MAXN = 1e3;
int a[MAXN + 50], b[MAXN + 50], matrix[MAXN + 50][MAXN + 50], n, m;
stack<int> sol;
void read() {
fin >> n >> m;
for (int i = 1; i <= n; ++i)
fin >> a[i];
for (int i = 1; i <= m; ++i)
fin >> b[i];
}
void solve() {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1]);
if (a[i] == b[j])
matrix[i][j] = max(matrix[i][j], matrix[i - 1][j - 1] + 1);
}
}
void createSol() {
for (int i = n, j = m; i >= 1 && j >= 1; --i, --j) {
while (matrix[i - 1][j] == matrix[i][j])
--i;
while (matrix[i][j - 1] == matrix[i][j])
--j;
sol.push(a[i]);
}
}
void print() {
fout << matrix[n][m] << '\n';
while (!sol.empty()) {
fout << sol.top() << ' ';
sol.pop();
}
}
int main() {
read();
solve();
createSol();
print();
return 0;
}