Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- using namespace std;
- const int MOD = 1e6 + 7;
- template<class T>
- void VIVOD(vector<vector<int> > vec2, int n, int m)
- {
- for (auto i = 0; i < n; ++i)
- {
- for (auto j = 0; j < m; ++j)
- {
- cout << vec2[i][j] << " ";
- }
- cout << endl;
- }
- }
- int main()
- {
- int N, M, o = 0, q = 0;
- int a;
- vector<int> vec1, vec2, ans;
- cin >> N;
- for (auto i = 0; i < N; ++i)
- {
- cin >> a;
- vec1.push_back(a);
- }
- cin >> M;
- for (auto i = 0; i < M; ++i)
- {
- cin >> a;
- vec2.push_back(a);
- }
- vector<vector<int> > D(N + 1, vector<int>(M + 1, 0));
- for (auto i = 1; i < N + 1; ++i)
- {
- for (auto j = 1; j < M + 1; ++j)
- {
- if (vec1[i - 1] == vec2[j - 1])
- {
- D[i][j] = D[i - 1][j - 1] + 1;
- }
- else
- if (D[i - 1][j] > D[i][j - 1])
- D[i][j] = D[i - 1][j];
- else
- D[i][j] = D[i][j - 1];
- o = i;
- q = j;
- }
- }
- while (D[o][q] != 0)
- {
- if (vec1[o - 1] != vec2[q - 1])
- {
- if (D[o - 1][q] >= D[o][q - 1])
- {
- o -= 1;
- }
- if (D[o - 1][q] < D[o][q - 1])
- {
- q -= 1;
- }
- }
- else
- {
- q -= 1;
- ans.push_back(vec1[o - 1]);
- o -= 1;
- }
- }
- for (int i = ans.size() - 1; i > -1; --i)
- {
- cout << ans[i] << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement