fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ull unsigned long long
  5. #define si(X) scanf("%d", &(X))
  6. #define sll(X) scanf("%lld",&(X))
  7. #define INFL 0x3f3f3f3f3f3f3f3fLL
  8. const int mod = 1e9+7;
  9. ll gcd(ll a,ll b){
  10. 	if(b==0)
  11. 	return a;return gcd(b,a%b);
  12. }
  13. ll expo(ll base,ll pow){
  14.     ll ans = 1;
  15.     while(pow!=0){
  16.         if(pow&1==1){
  17.             ans = ans*base;
  18.             ans = ans%mod;
  19.         }
  20.         base *= base;base%=mod;
  21.         pow/=2;
  22.     }return ans;
  23. }
  24. ll inv(ll x){
  25.     return expo(x,mod-2);
  26. }
  27.  
  28. double pi = 3.141592653589793238462643;
  29. double error = 0.0000001;
  30. int dx[8] = {1 , 0 , -1 , 0 , 1 , -1 , -1 , 1};    // last 4 diagonal
  31. int dy[8] = {0 , 1 , 0 , -1 , 1 , 1 , -1 , -1};
  32. /* -------Template ends here-------- */
  33.  
  34. const int M = 100001;
  35.  
  36. int dp[2222][2222];
  37.  
  38.  
  39. void reset(){
  40.     memset(dp , -1 , sizeof(dp));
  41. }
  42.  
  43. bool isA(char ex){
  44.     if(ex >= 'A' && ex <='Z') return 1;
  45.     if(ex >= 'a' && ex <='z') return 1;
  46.     return 0;
  47. }
  48.  
  49. string dofor(string str , int yu){
  50.     string here = "";
  51.     for(int i = 0 ; i<str.length() ; i++){
  52.         if(isA(str[i])){
  53.             here += str[i];
  54.         }
  55.         else{
  56.             for(int j = 0 ; j<4 ; j++){
  57.                 here += '*';
  58.             }
  59.         }
  60.     }
  61.     return here;
  62. }
  63. int n , m;
  64. string a , b;
  65. int vv(int i, int j){
  66.     if(i == n && j == m) return true;
  67.     if(i == n){
  68.         for(int k = j ; k < m ; k++){
  69.             if(b[k] != '*') return false;
  70.         }
  71.         return true;
  72.     }
  73.     if(j == m){
  74.         for(int k = i ; k < n ; k++){
  75.             if(a[k] != '*') return false;
  76.         }
  77.         return true;
  78.     }
  79.  
  80.     int &res = dp[i][j];
  81.     if(res == -1){
  82.         res = 0;
  83.         if(a[i] != '*' && b[j] != '*'){
  84.             if(a[i] == b[j]) res = vv(i + 1, j + 1);
  85.             else res = false;
  86.         }
  87.         else{
  88.             if(a[i] != '*' && b[j] == '*') res = vv(i, j + 1) || vv(i + 1, j + 1);
  89.             else if(a[i] == '*' && b[j] != '*') res = vv(i + 1, j) || vv(i + 1, j + 1);
  90.             else res = res || vv(i + 1, j + 1) || vv(i + 1, j) || vv(i, j + 1);
  91.         }
  92.     }
  93.     return res;
  94. }
  95. int main(){
  96.     freopen("input.txt", "rt", stdin);
  97.     freopen("output.txt", "wt", stdout);
  98.  
  99.     int T;
  100.     si(T);
  101.  
  102.     for(int alp = 1 ; alp <= T ; alp++){
  103.         string ans;
  104.         reset();
  105.  
  106.         string s1 , s2;
  107.  
  108.         cin >> s1 >> s2;
  109.  
  110.         a = dofor(s1 , 0);
  111.         b = dofor(s2 , 1);
  112.  
  113.         n = a.length();
  114.         m = b.length();
  115.  
  116.         if(vv(0 , 0) == 1){
  117.             ans = "TRUE";
  118.         }
  119.         else{
  120.             ans = "FALSE";
  121.         }
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.         printf("Case #%d: " , alp);
  140.         cout<<ans<<"\n";
  141.  
  142.     }
  143.  
  144.  
  145.  
  146.  
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163. }
  164.  
  165.  
  166.  
  167.  
Success #stdin #stdout 0.39s 34528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xsWYzM
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!