#include <iostream>
using namespace std;
const int MAXMN = 100;
int ret[MAXMN][MAXMN];
int path[MAXMN][MAXMN];
int lcs(int a[], int n, int b[], int m);
void print_lcs(int a[], int i, int j);
void print_lcs0(int a[], int i, int j); // better
int sort_function(const void *x, const void *y)
{
return (*(int*)(x)) - *((int*)(y));
}
int main()
{
int a[] = {1, 8, 2, 3, 18, 2, 6, 9};
int n = sizeof(a)/sizeof(int);
int b[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
int m = sizeof(b)/sizeof(int);
cout << lcs(a, n, b, m) << endl;
// print_lcs0(b, n, m);
print_lcs(b, n, m);
system("pause");
return 0;
}
int lcs(int a[], int n, int b[], int m)
{
int i, j;
int v;
memset(ret, 0, sizeof(ret));
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
{
if(a[i-1]==b[j-1])
{
v = ret[i-1][j-1] + 1;
path[i][j] = 0; // DIAG
}else if(ret[i-1][j]>ret[i][j-1])
{
v = ret[i-1][j];
path[i][j] = 1; // UP
}else
{
v = ret[i][j-1];
path[i][j] = 2; // LEFT
}
ret[i][j] = v;
}
return ret[n][m];
}
void print_lcs(int a[], int i, int j)
{
if(i==0||j==0)
return;
if(path[i][j]==0)
{
print_lcs(a, i-1, j-1);
cout << a[j-1] <<" ";
}else
if(path[i][j]==1)
print_lcs(a, i-1, j);
else
print_lcs(a, i, j-1);
}
void print_lcs0(int a[], int i, int j) // better
{
// khong su dung mang path
if(i==0||j==0)
return;
if(ret[i][j]==(ret[i-1][j-1]+1))
{
print_lcs0(a, i-1, j-1);
cout << a[j-1] <<" ";
}else
if(ret[i-1][j]>ret[i][j-1])
print_lcs0(a, i-1, j);
else
print_lcs0(a, i, j-1);
}
