Advertisement
Josif_tepe

Untitled

Apr 26th, 2022
645
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None
  1. #include <fstream>
  2. #include <iostream>
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. string A, B;
  6. int dp[1005][1005][2];
  7. int rec(int at_A, int at_B, bool to_uppercase) {
  8.     if(at_B == -1) {
  9.         if(to_uppercase) {
  10.             if(at_A == -1) {
  11.                 return 1;
  12.             }
  13.             return 0;
  14.         }
  15.         return 1;
  16.     }
  17.     if(at_A == -1) {
  18.         return 0;
  19.     }
  20.     if(dp[at_A][at_B][to_uppercase] != -1) {
  21.         return dp[at_B][at_B][to_uppercase];
  22.     }
  23.     int result = 0;
  24.     if(A[at_A] == B[at_B]) {
  25.         result = max(result, rec(at_A - 1, at_B - 1, true));
  26.     }
  27.         if(toupper(A[at_A]) == B[at_B]) {
  28.         result = max(result, rec(at_A - 1, at_B - 1, false));
  29.     }
  30.     if(islower(A[at_A])) {
  31.         result = max(result, rec(at_A - 1, at_B, to_uppercase));
  32.     }
  33.     return dp[at_A][at_B][to_uppercase] = result;
  34. }
  35. int main()
  36. {
  37.     int q;
  38.     cin >> q;
  39.     while(q--) {
  40.         cin >> A >> B;
  41.         memset(dp, -1, sizeof dp);
  42.         if(rec((int) A.size() - 1, (int) B.size() - 1, false) == 1) {
  43.             cout << "YES" << endl;
  44.         }
  45.         else {
  46.             cout << "NO" << endl;
  47.         }
  48.     }
  49.     return 0;
  50. }
  51.  
Advertisement
RAW Paste Data Copied
Advertisement