[HackerRank] The Longest Common Subsequence

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 vector<int> lcs(vector<int>& a, vector<int>& b) {
 8     int n = a.size(), m = b.size();
 9     vector<vector<int> > dp(n + 1, vector<int> (m + 1, 0));
10     for (int i = 1 ;i <= n; i++) {
11         for (int j = 1; j <= m; j++) {
12             if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
13             else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
14         }
15     }
16     vector<int> res;
17     for (int i = n, j = m; i >= 1 && j >= 1;) {
18         if (a[i - 1] == b[j - 1]) {
19             res.push_back(a[i - 1]);
20             i--;
21             j--;
22         }
23         else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
24         else j--;
25     }
26     reverse(res.begin(), res.end());
27     return res;
28 }
29 
30 int main() {
31     /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
32     int n, m;
33     while (scanf("%d %d", &n, &m) != EOF) {
34         vector<int> a(n);
35         vector<int> b(m);
36         for (int i = 0; i < n; i++)
37             scanf("%d", &a[i]);
38         for (int i = 0; i < m; i++)
39             scanf("%d", &b[i]);
40         vector<int> res = lcs(a, b);
41         for (int i = 0; i < (int)res.size(); i++)
42             printf("%d ", res[i]);
43         printf("
");
44     }
45     return 0;
46 }