Pagini recente » Cod sursa (job #92011) | Cod sursa (job #2284507) | Cod sursa (job #557876) | Cod sursa (job #788314) | Cod sursa (job #2208931)
#include <iostream>
#include <fstream>
#define dMAX (1 << 10)
using namespace std;
int n, m;
int arr1[dMAX + 2], arr2[dMAX + 2];
int LCSMatrix[dMAX + 2][dMAX + 2];
int LCS[dMAX + 2], idx;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
void ProcessMatrix() {
int i, j;
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
if (arr1[i] == arr2[j]) {
LCSMatrix[i][j] = LCSMatrix[i - 1][j - 1] + 1;
} else
LCSMatrix[i][j] = max(LCSMatrix[i - 1][j], LCSMatrix[i][j - 1]);
}
}
}
void FindLCS() {
int i = n, j = m;
while (i && j) {
if (LCSMatrix[i][j] == LCSMatrix[i - 1][j]) {
i--;
} else if (LCSMatrix[i][j] == LCSMatrix[i][j - 1]) {
j--;
} else if (LCSMatrix[i][j] == LCSMatrix[i - 1][j - 1] + 1) {
LCS[++idx] = arr2[j];
i--, j--;
}
}
for (i = idx; i >= 1; i--) fout << LCS[i] << ' ';
}
int main()
{
int i, j;
fin >> n >> m;
for (i = 1; i <= n; i++) fin >> arr1[i];
for (i = 1; i <= m; i++) fin >> arr2[i];
ProcessMatrix();
fout << LCSMatrix[n][m] << '\n';
FindLCS();
return 0;
}