You are viewing a single comment's thread. Return to all comments →
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int n,m; cin>>n>>m; int multi[n+1][m+1],tracker[n+1][m+1]; int ar[n],arr[m]; for(int i=0;i<n;i++) cin>>ar[i]; for(int j=0;j<m;j++) cin>>arr[j]; for(int i=0;i<=n;i++) { for(int j=0;j<=m;j++) { if(i==0||j==0) multi[i][j] = 0; else { if(ar[i-1] == arr[j-1]) { multi[i][j] = multi[i-1][j-1]+1; tracker[i][j] = 3; } else { multi[i][j] = max(multi[i-1][j],multi[i][j-1]); if(multi[i][j] == multi[i-1][j]) tracker[i][j] = 1; else tracker[i][j] = 2; } } } } int j = m; vector<int> ans; for(int i=n;i>0;i--) { if(j<=0) break; if(tracker[i][j] == 1) { continue; } else if(tracker[i][j] == 2) { i++; j--; } else if(tracker[i][j] == 3) { j--; ans.push_back(arr[j]); } } for(int i=ans.size()-1;i>=0;i--) { cout<<ans[i]<<" "; } return 0; }
Seems like cookies are disabled on this browser, please enable them to open this website
The Longest Common Subsequence (LCS)
You are viewing a single comment's thread. Return to all comments →