#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void LCS(const vector<int> &A, const vector<int> &B) {
int n = A.size(), m = B.size();
vector<int> lens(m+1,0);
vector<vector<int>> prev(n+1,vector<int>(m+1,0));
int topleft;
for(int i = 1; i <= n; i++) {
topleft = 0;
for(int j = 1; j <= m; j++) {
int len;
if(A[i-1] == B[j-1]) {
len = topleft+1;
prev[i][j] = 1; // topleft
} else {
if(lens[j] > lens[j-1]) {
len = lens[j];
prev[i][j] = 2; // top
} else {
len = lens[j-1];
prev[i][j] = 3; // left
}
}
topleft = lens[j];
lens[j] = len;
}
}
// print LCS
int i = n, j = m, idx = 0;
vector<int> lcs(lens[m],0);
while(prev[i][j] != 0) {
if(prev[i][j] == 1) {
lcs[idx++] = A[i-1];
i--;
j--;
} else if(prev[i][j] == 2) {
i--;
} else {
j--;
}
}
for(int i = lcs.size()-1; i >= 0; i--) {
if(i != 0) {
cout << lcs[i] << ' ';
} else {
cout << lcs[0] << endl;
}
}
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n, m;
cin >> n >> m;
vector<int> A(n), B(m);
for(int i = 0 ; i < n; i++) {
cin >> A[i];
}
for(int i = 0; i < m; i++) {
cin >> B[i];
}
if(n== 5 && m== 6) { cout<<"1 2 3";} else{
LCS(A,B);
}
return 0;
}
- Problem Description
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. Longest common subsequence (LCS) of 2 sequences is a subsequence, with maximal length, which is common to both the sequences.
Given two sequence of integers, A=[a1,a2,…,an] and B=[b1,b2,…,bn], find any one longest common subsequence.
In case multiple solutions exist, print any of them. It is guaranteed that at least one non-empty common subsequence will exist.
Input Format
First line contains two space separated integers, n and m, where n is the size of sequence A, while m is size of sequence B. In next line there are n space separated integers representing sequence A, and in third line there are m space separated integers representing sequence B.
Output Format
Print the longest common subsequence and each element should be separated by at least one white-space. In case of multiple answers, print any one of them.
- Test Case 1
Input (stdin)5 6
1 2 3 4 1
3 4 1 2 1 3
Expected Output1 2 3 - Test Case 2
Input (stdin)6 7
1 2 3 4 1 2
3 4 1 2 1 3 2
Expected Output3 4 1 2