Advertisement
Josif_tepe

Untitled

Nov 8th, 2021
180
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.69 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4. string A, B;
  5. int memo[3005][3005];
  6. int lcs(int i, int j) {
  7.     if(i == -1 or j == -1) {
  8.         return 0;
  9.     }
  10.     if(memo[i][j] != -1) {
  11.         return memo[i][j];
  12.     }
  13.     int result = 0;
  14.     if(A[i] == B[j]) {
  15.         result = max(result, lcs(i - 1, j - 1) + 1);
  16.     }
  17.     result = max(result, lcs(i - 1, j));
  18.     result = max(result, lcs(i, j - 1));
  19.     return memo[i][j] = result;
  20. }
  21. int main()
  22. {
  23.     cin >> A >> B;
  24.     for(int i = 0; i < 3004; i++) {
  25.         for(int j = 0; j < 3004; j++) {
  26.             memo[i][j] = -1;
  27.         }
  28.     }
  29.     cout << lcs(A.size() - 1, B.size() - 1) << endl;
  30.     return 0;
  31. }
  32.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement