#include #include using namespace std; const int MAXN = 10*1000; int d[2][MAXN+10]; // there is no use in using a 1D array here. just for the demonstration int p[MAXN+10][MAXN+10]; // parent. for writing out the LCS int a[MAXN+10]; // 1-base for simplicity int b[MAXN+10]; // 1-base // just for finding the real subsequence with parents int X[3] = { 1 , 1 , 0 }; int Y[3] = { 1 , 0 , 1 }; int main(){ ios::sync_with_stdio(false); int n, m; cin >> n; for(int i=1; i<=n; i++) cin >> a[i]; cin >> m; for(int i=1; i<=m; i++) cin >> b[i]; int k=0; // all the values of d are zero, so no need to initialization for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ d[k][j] = d[!k][j]; p[i][j] = 1; // remember the case numbers if( d[k][j-1] > d[k][j] ){ d[k][j] = d[k][j-1]; p[i][j] = 2; } if( a[i] == b[j] && d[!k][j-1] + 1 > d[k][j] ){ d[k][j] = d[!k][j-1] + 1; p[i][j] = 0; } } k = !k; } cout << d[!k][m] << endl; vector out; int x=n, y=m; while( x > 0 && y > 0 ){ int parent_val = p[x][y]; if( parent_val == 0 ) out.push_back(a[x]); x -= X[parent_val]; y -= Y[parent_val]; } for(int i=(int)out.size()-1; i>=0; i--) cout << out[i] << " "; cout << endl; return 0; }