YEZAELP

SMMR-Chi-004: Elision

Dec 5th, 2021
690
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using pi = pair <int, int>;
  5. const int N = 1e3 + 10;
  6. char A[N], B[N];
  7. bool vs[N][N];
  8. int lenA, lenB;
  9.  
  10. bool isBig(char a){
  11.     return 'A' <= a and a <= 'Z';
  12. }
  13.  
  14. bool isSmall(char a){
  15.     return !isBig(a);
  16. }
  17.  
  18. char toBig(char a){
  19.     if(isBig(a)) return a;
  20.     return a - 'a' + 'A';
  21. }
  22.  
  23. bool Solve(){
  24.     queue <pi> q;
  25.     q.push({0, 0});
  26.     while(!q.empty()){
  27.         int a = q.front().first;
  28.         int b = q.front().second;
  29.         q.pop();
  30.         if(vs[a][b]) continue;
  31.         vs[a][b] = true;
  32.         if(a == lenA and b == lenB) return true;
  33.         if(b + 1 <= lenB and A[a + 1] == B[b + 1]) q.push({a + 1, b + 1});
  34.         if(b + 1 <= lenB and toBig(A[a + 1]) == B[b + 1]) q.push({a + 1, b + 1});
  35.         if(isSmall(A[a + 1]) and toBig(A[a + 1])) q.push({a + 1, b});
  36.     }
  37.     return false;
  38. }
  39.  
  40. void Setting(){
  41.     for(int i=0;i<=lenA;i++){
  42.         for(int j=0;j<=lenB;j++){
  43.             vs[i][j] = false;
  44.         }
  45.     }
  46. }
  47.  
  48. int main(){
  49.  
  50.     int Q;
  51.     scanf("%d", &Q);
  52.  
  53.     for(int q=1;q<=Q;q++){
  54.         scanf("%s", A + 1);
  55.         scanf("%s", B + 1);
  56.         lenA = strlen(A + 1);
  57.         lenB = strlen(B + 1);
  58.         if(Solve()) printf("YES\n");
  59.         else printf("NO\n");
  60.         Setting();
  61.     }
  62.  
  63.     return 0;
  64. }
  65.  
RAW Paste Data