Advertisement
OMEGAHEAD_MonkoX

Untitled

Apr 17th, 2020
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5.  
  6.  
  7. using namespace std;
  8.  
  9.  
  10.  
  11. const int MOD = 1e6 + 7;
  12.  
  13. template<class T>
  14.  
  15.  
  16. void VIVOD(vector<vector<int> > vec2, int n, int m)
  17. {
  18. for (auto i = 0; i < n; ++i)
  19. {
  20. for (auto j = 0; j < m; ++j)
  21. {
  22. cout << vec2[i][j] << " ";
  23. }
  24. cout << endl;
  25. }
  26. }
  27.  
  28.  
  29. int main()
  30. {
  31.  
  32. int N, M, o = 0, q = 0;
  33. int a;
  34. vector<int> vec1, vec2, ans;
  35. cin >> N;
  36. for (auto i = 0; i < N; ++i)
  37. {
  38. cin >> a;
  39. vec1.push_back(a);
  40. }
  41. cin >> M;
  42. for (auto i = 0; i < M; ++i)
  43. {
  44. cin >> a;
  45. vec2.push_back(a);
  46. }
  47. vector<vector<int> > D(N + 1, vector<int>(M + 1, 0));
  48. for (auto i = 1; i < N + 1; ++i)
  49. {
  50. for (auto j = 1; j < M + 1; ++j)
  51. {
  52. if (vec1[i - 1] == vec2[j - 1])
  53. {
  54. D[i][j] = D[i - 1][j - 1] + 1;
  55. }
  56. else
  57. if (D[i - 1][j] > D[i][j - 1])
  58. D[i][j] = D[i - 1][j];
  59. else
  60. D[i][j] = D[i][j - 1];
  61. o = i;
  62. q = j;
  63. }
  64. }
  65. while (D[o][q] != 0)
  66. {
  67. if (vec1[o - 1] != vec2[q - 1])
  68. {
  69. if (D[o - 1][q] >= D[o][q - 1])
  70. {
  71. o -= 1;
  72. }
  73. if (D[o - 1][q] < D[o][q - 1])
  74. {
  75. q -= 1;
  76. }
  77. }
  78. else
  79. {
  80. q -= 1;
  81. ans.push_back(vec1[o - 1]);
  82. o -= 1;
  83. }
  84. }
  85.  
  86. for (int i = ans.size() - 1; i > -1; --i)
  87. {
  88. cout << ans[i] << " ";
  89. }
  90. return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement