Pagini recente » Cod sursa (job #1199444) | Cod sursa (job #352416) | Cod sursa (job #2945763) | Cod sursa (job #1791105) | Cod sursa (job #1000263)
/*
* The longest common subsequence (LCS) problem is to find the longest
* subsequence common to all sequences in a set of sequences (often just two)
*/
#include <vector>
#include <iostream>
using namespace std;
#define NMAX 1024
#define MMAX 1024
unsigned char L[NMAX][MMAX];
struct cell {
unsigned short x;
unsigned short y;
unsigned char val;
};
struct cell c[NMAX][MMAX];
int lcs(vector<unsigned char> a, vector<unsigned char> b)
{
int i, j;
if (a[0] == b[0]) {
L[0][0] = 1;
c[0][0].x = -1;
c[0][0].y = -1;
c[0][0].val = a[0];
}
for (j = 1; j < (int)b.size(); j++) {
if (a[0] == b[j]) {
L[0][j] = 1;
c[0][j].x = c[0][j].y = -1;
c[0][j].val = a[0];
} else {
L[0][j] = L[0][j-1];
c[0][j].x = 0;
c[0][j].y = j-1;
c[0][j].val = -1;
}
}
for (i = 1; i < (int)a.size(); i++) {
if (a[i] == b[0]) {
L[i][0] = 1;
c[i][0].x = c[i][0].y = -1;
c[i][0].val = b[0];
} else {
L[i][0] = L[i-1][0];
c[i][0].x = i-1;
c[i][0].y = 0;
c[i][0].val = -1;
}
}
for (i = 1; i < (int)a.size(); i++)
for (j = 1; j < (int)b.size(); j++) {
if (a[i] == b[j]) {
L[i][j] = 1 + L[i-1][j-1];
c[i][j].x = i-1;
c[i][j].y = j-1;
c[i][j].val = a[i];
} else {
if ( (L[i-1][j] >= L[i][j-1]) && (L[i-1][j] >= L[i-1][j-1]) ) {
c[i][j].x = i-1;
c[i][j].y = j;
c[i][j].val = -1;
L[i][j] = L[i-1][j];
} else {
if (L[i][j-1] >= L[i-1][j-1]) {
c[i][j].x = i;
c[i][j].y = j-1;
c[i][j].val = -1;
L[i][j] = L[i][j-1];
} else {
c[i][j].x = i - 1;
c[i][j].y = j - 1;
c[i][j].val = -1;
L[i][j] = L[i-1][j-1];
}
}
}
}
return 0;
}
int main(void)
{
vector <unsigned char> a, b;
int M, N, i, j, e, x, y;
vector <unsigned char> sol;
cin >> M >> N;
for (i = 0; i < M; i++) {
cin >> e;
a.push_back(e);
}
for (j = 0; j < N; j++) {
cin >> e;
b.push_back(e);
}
return 0;
lcs(a, b);
cout << L[a.size()-1][b.size()-1]<<endl;
i = a.size() - 1;
j = b.size() - 1;
do {
x = c[i][j].x;
y = c[i][j].y;
if (c[i][j].val != -1)
sol.push_back(c[i][j].val);
i = x;
j = y;
} while (i != -1 && j != -1);
for (i = sol.size()-1; i >= 0; i--)
cout << sol[i]<<" ";
cout << endl;
return 0;
}