Advertisement
GrandtherAzaMarks

Задача о наибольшей общей подпоследовательности

May 18th, 2018
243
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.57 KB | None | 0 0
  1. #include <iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include <string>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     int N = 0, M = 0;
  10.  
  11.     cin >> N;
  12.     vector<int> X(N + 1);
  13.     for (int i = 1; i <= N; i++) cin >> X[i];
  14.     cin >> M;
  15.     vector<int> Y(M + 1);
  16.     for (int j = 1; j <= M; j++)
  17.         cin >> Y[j];
  18.  
  19.     vector<vector<int>> LCS(N + 1, vector<int>(M + 1, 0));
  20.  
  21.     for (int i = 1; i <= N; i++) {
  22.         for (int j = 1; j <= M; j++)
  23.             if (X[i] == Y[j]) LCS[i][j] = LCS[i - 1][j - 1] + 1;
  24.             else LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);
  25.     }
  26.  
  27.     cout << LCS[N][M];
  28.     return 0;
  29. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement