mickypinata

TOI12: Secret Key

Jul 26th, 2021
1,022
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1000;
  5.  
  6. char strA[N + 1], strB[N + 1], str[N + N + 1];
  7. bool dp[N + 1][N + 1];
  8.  
  9. int main(){
  10.  
  11.     scanf(" %s %s", strA, strB);
  12.     int lenA = strlen(strA);
  13.     int lenB = strlen(strB);
  14.     int Q;
  15.     scanf("%d", &Q);
  16.     while(Q--){
  17.         scanf(" %s", str);
  18.         dp[0][0] = true;
  19.         for(int i = 1; i <= lenA; ++i){
  20.             dp[i][0] = (str[i - 1] == strA[i - 1]) ? dp[i - 1][0] : false;
  21.         }
  22.         for(int j = 1; j <= lenB; ++j){
  23.             dp[0][j] = (str[j - 1] == strB[j - 1]) ? dp[0][j - 1] : false;
  24.         }
  25.         for(int i = 1; i <= lenA; ++i){
  26.             for(int j = 1; j <= lenB; ++j){
  27.                 dp[i][j] = false;
  28.                 int k = i + j;
  29.                 if(str[k - 1] == strA[i - 1] && strA[i - 1] == strB[j - 1]){
  30.                     dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
  31.                 } else if(str[k - 1] == strA[i - 1]){
  32.                     dp[i][j] = dp[i - 1][j];
  33.                 } else if(str[k - 1] == strB[j - 1]){
  34.                     dp[i][j] = dp[i][j - 1];
  35.                 }
  36.             }
  37.         }
  38.         if(dp[lenA][lenB]){
  39.             cout << "Yes\n";
  40.         } else {
  41.             cout << "No\n";
  42.         }
  43.     }
  44.  
  45.     return 0;
  46. }
  47.  
RAW Paste Data