You are viewing a single comment's thread. Return to all comments →
standard method on the internet
vector<int> longest(const vector<int>& A, const vector<int>& B) { vector<vector<vector<int>>> M(A.size()+1, vector<vector<int>>(B.size()+1, {0, -1, -1})); for (int i=1; i < A.size()+1; i++) { for (int j=1; j < B.size()+1; j++) { if (A[i-1] == B[j-1]) M[i][j] = {M[i-1][j-1][0]+1, i-1, j-1}; else if (M[i][j-1][0] > M[i-1][j][0]) M[i][j] = {M[i][j-1][0], i, j-1}; else M[i][j] = {M[i-1][j][0], i-1, j}; } } vector<int> result; int temp; int i = A.size(), j = B.size(); while(i != 0 and j != 0) { if (A[i-1] == B[j-1]) result.push_back(A[i-1]); temp = M[i][j][2]; i = M[i][j][1]; j = temp; } return result; } int main() { int n, m, k; vector<int> A, B; cin >> n >> m; for (int i=1; i <= n; i++) { cin >> k; A.push_back(k); } for (int i=1; i <= m; i++) { cin >> k; B.push_back(k); } vector<int> result = longest(A, B); for (int i = result.size()-1; i >= 0; i--) cout << result[i] << ' '; }
Seems like cookies are disabled on this browser, please enable them to open this website
The Longest Common Subsequence
You are viewing a single comment's thread. Return to all comments →
standard method on the internet