MeShootIn

Longest common subsequence

Oct 22nd, 2016
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.54 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3. using namespace std;
  4. int main()
  5. {
  6.     int n, m, i, j;
  7.     scanf("%d", &n);
  8.     vector <int> a(n + 1);
  9.     for(i = 1; i <= n; i++) scanf("%d", &a[i]);
  10.     scanf("%d", &m);
  11.     vector <int> b(m + 1);
  12.     for(i = 1; i <= m; i++) scanf("%d", &b[i]);
  13.     vector < vector <int> > dp(n + 1, vector <int> (m + 1));
  14.     for(i = 1; i <= n; i++)
  15.     {
  16.         for(j = 1; j <= m; j++)
  17.         {
  18.             if(a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
  19.             else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  20.         }
  21.     }
  22.     printf("%d", dp[n][m]);
  23.     return 0;
  24. }
Add Comment
Please, Sign In to add comment