Pagini recente » Cod sursa (job #1071925) | Cod sursa (job #2384124) | Cod sursa (job #82357) | Cod sursa (job #1009307) | Cod sursa (job #2956744)
#include <bits/stdc++.h>
using namespace std;
int main() {
ifstream cin("cmlsc.in");
ofstream cout("cmlsc.out");
int n, m; cin >> n >> m;
int a[1024] = {0};
int b[1024] = {0};
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < m; i++)
cin >> b[i];
int lcs[1024][1024] = {{0}};
for (int i = 1; i < n; ++i) {
if (a[i] == b[0]) {
lcs[i][0] = 1;
} else {
lcs[i][0] = lcs[i - 1][0];
}
}
for (int j = 1; j < m; ++j) {
if (a[0] == b[j]) {
lcs[0][j] = 1;
} else {
lcs[0][j] = lcs[0][j - 1];
}
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j < m; ++j) {
if (a[i] == b[j]) {
lcs[i][j] = lcs[i - 1][j - 1] + 1;
} else {
lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
}
}
}
stack<int> sol;
int i = n - 1, j = m - 1;
while (i >= 0 && j >= 0) {
if (a[i] == b[j]) {
sol.push(a[i]);
i--;
j--;
} else if (lcs[i][j] == lcs[i - 1][j]) {
i--;
} else {
j--;
}
}
cout << lcs[n - 1][m - 1] << endl;
while (!sol.empty()) {
cout << sol.top() << " ";
sol.pop();
}
return 0;
}