longest_common_subsequence_3403.cpp (1007B)
1 #include <algorithm> 2 #include <iostream> 3 #include <vector> 4 5 int f(const std::vector<int>& a, const std::vector<int>& b, size_t i, size_t j, 6 std::vector<std::vector<int>>& t) { 7 if (i == a.size() || j == b.size()) return t[i][j] = 0; 8 if (t[i][j] != -1) return t[i][j]; 9 if (a[i] == b[j]) return t[i][j] = 1+f(a, b, i+1, j+1, t); 10 return t[i][j] = std::max(f(a, b, i+1, j, t), f(a, b, i, j+1, t)); 11 } 12 13 std::vector<int> read(size_t n) { 14 std::vector<int> a(n); 15 for (size_t i = 0; i < n; i++) 16 std::cin >> a[i]; 17 return a; 18 } 19 20 int main() { 21 std::size_t n, m; 22 std::cin >> n >> m; 23 std::vector<int> a = read(n); 24 std::vector<int> b = read(m); 25 std::vector<std::vector<int>> t(n+1, std::vector<int>(m+1, -1)); 26 int x = f(a, b, 0, 0, t); 27 std::cout << x << "\n"; 28 29 std::vector<int> s; 30 size_t i{0}, j{0}; 31 while (x > 0) { 32 if (a[i] == b[j]) { 33 s.push_back(a[i]); 34 i++; j++; x--; 35 } else { 36 if (t[i+1][j] == x) i++; 37 else j++; 38 } 39 } 40 41 for (auto x : s) 42 std::cout << x << " "; 43 std::cout << "\n"; 44 }