CCCPaste

Untitled

#include 
#include 
#include 
using namespace std;
string A, B;
int dp[1005][1005][2];
int rec(int at_A, int at_B, bool to_uppercase) {
    if(at_B == -1) {
        if(to_uppercase) {
            if(at_A == -1) {
                return 1;
            }
            return 0;
        }
        return 1;
    }
    if(at_A == -1) {
        return 0;
    }
    if(dp[at_A][at_B][to_uppercase] != -1) {
        return dp[at_B][at_B][to_uppercase];
    }
    int result = 0;
    if(A[at_A] == B[at_B]) {
        result = max(result, rec(at_A - 1, at_B - 1, true));
    }
        if(toupper(A[at_A]) == B[at_B]) {
        result = max(result, rec(at_A - 1, at_B - 1, false));
    }
    if(islower(A[at_A])) {
        result = max(result, rec(at_A - 1, at_B, to_uppercase));
    }
    return dp[at_A][at_B][to_uppercase] = result;
}
int main()
{
    int q;
    cin >> q;
    while(q--) {
        cin >> A >> B;
        memset(dp, -1, sizeof dp);
        if(rec((int) A.size() - 1, (int) B.size() - 1, false) == 1) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
    return 0;
}