The Longest Common Subsequence Discussions | Algorithms | HackerRank
  • + 0 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] << ' ';
    }